文档章节

数据结构(C语言版)第五章:树

fzyz_sb
 fzyz_sb
发布于 2013/12/07 18:15
字数 1281
阅读 296
收藏 14
点赞 0
评论 2

5.2 二叉树

我们写一个二叉树,它支持树的插入,删除,查询和遍历,而且左子树的数据都小于右子树的数据(PS:树实际上很难的,想深入了解的话,可以去看看<算法导论>,什么红黑树啊,B树啊什么的,反正我没看懂就是了--估计是我太菜了^_^):

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct TREE{
	int						data;
	struct TREE			*leftChild;
	struct TREE			*rightChild;
}Tree;

void insertTree( Tree *tree, int data );
void deleteTree( Tree *tree, int data );
int searchTree( Tree *tree, int data );
void showTree( Tree *tree );

int main( void )
{
	Tree *tree = ( Tree * )malloc( sizeof( Tree ) );
	tree->leftChild = tree->rightChild = NULL;

	insertTree( tree, 5 );
	insertTree( tree, 3 );
	insertTree( tree, 2 );
	insertTree( tree, 4 );
	insertTree( tree, 8 );
	insertTree( tree, 7 );
	insertTree( tree, 9 );
	insertTree( tree, 6 );

	showTree( tree->leftChild );

	deleteTree( tree, 3 );
	deleteTree( tree, 5 );
	deleteTree( tree, 6 );

	printf("\n");
	showTree( tree->leftChild );

	printf("\n");
	if ( searchTree( tree, 8 ) ){
		printf("8 in the tree\n");
	}
	else{
		printf("8 not in the tree\n");
	}

	if ( searchTree( tree, 13 ) ){
		printf("13 in the tree\n");
	}
	else{
		printf("13 not in the tree\n");
	}

	return 0;
}

void insertTree( Tree *tree, int data )
{
	Tree *newTree = ( Tree * )malloc( sizeof( Tree ) );
	newTree->leftChild = newTree->rightChild = NULL;
	newTree->data = data;

	if ( ( NULL == tree->leftChild ) && ( NULL == tree->rightChild ) ){
		tree->leftChild = newTree;
	}
	else{
		tree = tree->leftChild;
		while ( NULL != tree ){
			if ( data == tree->data ){
				return;	
			}
			else if ( data < tree->data ){
				if ( NULL == tree->leftChild ){
					tree->leftChild = newTree;
					return;
				}
				tree = tree->leftChild;
			}
			else{
				if ( NULL == tree->rightChild ){
					tree->rightChild = newTree;
					return;
				}
				tree = tree->rightChild;
			}
		}
	}
}

/*
找到被删除节点的右子树的最小节点,删除最小节点并且将其值赋给被删除的节点
*/
void deleteTree( Tree *tree, int data )
{
	Tree *prevTree = ( Tree * )malloc( sizeof( Tree ) );		//指向删除节点的前一个节点
	Tree *tempTree = ( Tree * )malloc( sizeof( Tree ) );		//处理被删除的节点拥有左右树的特殊情况
	prevTree = tree;
	tree = tree->leftChild;

	while ( tree ){
		if ( data < tree->data ){
			prevTree = tree;
			tree = tree->leftChild;
		}
		else if ( data > tree->data ){
			prevTree = tree;
			tree = tree->rightChild;
		}
		else{
			//删除节点的左子树为空,则直接用右子树替换该节点
			if ( NULL == tree->leftChild ){
				if ( data == prevTree->leftChild->data ){
					prevTree->leftChild = prevTree->leftChild->rightChild;
				}
				else{
					prevTree->rightChild = prevTree->rightChild->rightChild;
				}
			}
			else if ( NULL == tree->rightChild ){		//删除节点的右子树为空,则直接用左子树替换该节点
				if ( data == prevTree->leftChild->data ){
					prevTree->leftChild = prevTree->leftChild->leftChild;
				}
				else{
					prevTree->rightChild = prevTree->rightChild->leftChild;
				}
			}
			else{
				tempTree = tree;		//保存右子树中最小节点的前节点
				tree = tree->rightChild;
				while ( tree->leftChild ){			//找到最小节点
					tempTree = tree;
					tree = tree->leftChild;
				}
				//替换数据
				if ( data == prevTree->leftChild->data ){
					prevTree->leftChild->data = tree->data;
				}
				else{
					prevTree->rightChild->data = tree->data;
				}

				//删除最小节点
				if ( tempTree->leftChild->data == tree->data ){
					tempTree->leftChild = tree->rightChild;
				}
				else{
					tempTree->rightChild = tree->rightChild;
				}
			}
			break;
		}
	}
}
int searchTree( Tree *tree, int data )
{
	tree = tree->leftChild;
	while ( tree ){
		if ( data == tree->data ){
			return 1;
		}
		else if ( data < tree->data ){
			tree = tree->leftChild;
		}
		else{
			tree = tree->rightChild;
		}
	}

	return 0;
}
void showTree( Tree *tree )
{
	if ( tree ){
		printf("%d ", tree->data );
		showTree( tree->leftChild );
		showTree( tree->rightChild );
	}
}



程序输出:

发现效率有点低@_@

二叉树有四种遍历方式:前序遍历,中序遍历,后序遍历,层序遍历.其中,层序遍历比较难.所以尝试写下代码看看:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 100
typedef struct TREE{
	int						data;
	struct TREE			*leftChild;
	struct TREE			*rightChild;
}Tree;

Tree *stack[ MAX_SIZE ];
int top = 0;
int rear = 0;

void insertTree( Tree *tree, int data );
void showTree( Tree *tree );

int main( void )
{
	Tree *tree = ( Tree * )malloc( sizeof( Tree ) );
	tree->leftChild = tree->rightChild = NULL;

	insertTree( tree, 5 );
	insertTree( tree, 3 );
	insertTree( tree, 2 );
	insertTree( tree, 4 );
	insertTree( tree, 8 );
	insertTree( tree, 7 );
	insertTree( tree, 9 );
	insertTree( tree, 6 );

	showTree( tree->leftChild );

	

	return 0;
}

void insertTree( Tree *tree, int data )
{
	Tree *newTree = ( Tree * )malloc( sizeof( Tree ) );
	newTree->leftChild = newTree->rightChild = NULL;
	newTree->data = data;

	if ( ( NULL == tree->leftChild ) && ( NULL == tree->rightChild ) ){
		tree->leftChild = newTree;
	}
	else{
		tree = tree->leftChild;
		while ( NULL != tree ){
			if ( data == tree->data ){
				return;	
			}
			else if ( data < tree->data ){
				if ( NULL == tree->leftChild ){
					tree->leftChild = newTree;
					return;
				}
				tree = tree->leftChild;
			}
			else{
				if ( NULL == tree->rightChild ){
					tree->rightChild = newTree;
					return;
				}
				tree = tree->rightChild;
			}
		}
	}
}

void showTree( Tree *tree )
{
	stack[ rear++ ] = tree;
	while ( 1 ){
		tree = stack[ top++ ];
		if ( tree ){
			printf("%d ", tree->data );
			if ( tree->leftChild ){
				stack[ rear++ ] = tree->leftChild;
			}
			if ( tree->rightChild ){
				stack[ rear++ ] = tree->rightChild;
			}
		}
		else{
			break;
		}
	}
}



实际上用到的是队列的思想,而不是堆栈的思想.程序输出:


5.4 二叉树的其他操作

1. 二叉树的复制

直接将头指针赋值即可.

2. 判断二叉树的等价性

需要用到递归,代码类似如下:

int equal(tree_pointer first, tree_pointer second )
{
    return ((!first && !second)||(first && second && 
              (first->data == second->data)) && 
               equal(first->left_child, second->left_child) &&
               equal(first->right_child, second->right_child))
}



3. 交换左右子树
void swapLeftRight( Tree *tree )
{
	if ( tree ){
		Tree *tempTree = ( Tree * )malloc( sizeof( Tree ) );
		tempTree = tree->leftChild;
		tree->leftChild = tree->rightChild;
		tree->rightChild = tempTree;
		swapLeftRight( tree->leftChild );
		swapLeftRight( tree->rightChild );
	}
}


5.5 线索二叉树

线索二叉树通过增加数据结构而简化遍历,这种想法是否可取得进一步讨论.


5.6 堆

1. 最大树是指在树中,一个结点有儿子结点,其关键字都不小于儿子结点的关键字值.最大堆是一棵完全二叉树,也是一棵最大树.

2. 最小数是指在树中,一个结点有儿子结点,其关键字都不大于儿子结点的关键字值.最小堆是一棵完全二叉树,也是一棵最小数.

http://my.oschina.net/voler/blog/167320

之前学习算法导论的时候,堆排序做了很详细的笔记.所以这里就不再重复了(不过有点忘记了.还是得找段时间好好研究一下算法导论).

5.7 二叉搜索树

这篇文章刚开始的时候就用一个程序开头,就是二叉搜索树的增删查.故不再重复.


© 著作权归作者所有

共有 人打赏支持
fzyz_sb
粉丝 408
博文 209
码字总数 447144
作品 0
武汉
程序员
加载中

评论(2)

fzyz_sb
fzyz_sb

引用来自“湖心亭看雪”的评论

这位大神,请问你懂极大极小算法吗?最近再搞一个棋类游戏,一直搞不懂

抱歉,没了解过这个算法,所以不懂1
湖心亭看雪
湖心亭看雪
这位大神,请问你懂极大极小算法吗?最近再搞一个棋类游戏,一直搞不懂
微软面试、经典算法、编程艺术、红黑树4大系列总结

无私分享,造福天下 以下是本blog内的微软面试100题系列,经典算法研究系列,程序员编程艺术系列,红黑树系列4大经典原创系列作品与一些重要文章的集锦。 一、微软面试100题系列 横空出世,席...

长平狐
2013/01/06
262
0
windows程序设计自学笔记(一)

本周开始自学windows编程,选的教材是《windows程序设计第五版》(珍藏版),没钱买书,只能下了pdf的书籍来看。 《windows程序设计第五版》(珍藏版)共分3个大部分,分别是:1)基础知识[...

赵西元
2012/12/13
0
0
数据结构(C语言版)第九章:堆结构

9.1 最小-最大堆 双端优先队列是一种支持如下操作的数据结构: 1. 插入一个具有任意关键字值的元素. 2. 删除关键字值最大的元素. 3. 删除关键字值最小的元素. 当仅支持插入和其中的一种删除操...

fzyz_sb
2013/12/16
0
0
业余爱好者的C程序设计学习之路

我学习和工作的方向都是化工,和 IT 专业一点边都不搭,属于程序设计爱好者一类。坚持了很多年了,谈谈我的认识。 一、为什么是C 汇编太难,直接下手会吓死宝宝的。 basic 不能考虑,因为“对...

四彩
2016/02/04
107
2
OpenJWeb 1.6 快速开发平台功能介绍

因本文的图片比较多,所以大家可以搜索我的资源文件,名为,下面是OpenJWeb1.6版本的功能目录: 第一章 OpenJWeb (v1.6)介绍... 4 第二章 功能详细介绍... 5 2.1 表结构定义工具... 5 2.1.1 表结...

迷途d书童
2012/03/09
73
0
做游戏,学编程(C语言) 网易云课堂MOOC视频

应一些同学的要求,把这学期上C语言编程课的讲课视频录制剪辑,上传到网易云课堂,感兴趣的朋友可以在线观看,欢迎多提宝贵意见。 MOOC视频链接:http://study.163.com/course/introduction....

童晶
2017/11/07
0
0
Linux C编程如何使用联机帮助来解决编程问题?

1.背景 多次学习C语言一直无法踏入C语言的大门,每次都是在学习C语言中的那些系统调用库函数等望而却只,linux下的系统调用需要我们去记忆一些没有规律的结构体和一些大写的宏定义并且还有一...

Jeff_Linux
2014/07/06
0
0
一个超前的C语言/C++老司机工程师说如何学习C语言/C++

每次一谈及到C语言C++,我想C语言C++功能强大都应该知道、应用广泛,一旦掌握了后,你就可以理直气壮地对他人说“我是电脑高手!”,而且以后若是再自学其他语言就显得轻而易举了。忧虑的是,...

小辰带你看世界
2017/12/31
0
0
推荐阅读的多核编程技术书籍

多核编程技术好书推荐 多核程序设计技术——通过软件多线程提升性能 , 作 者: (孟加拉)阿克特(Akhter,S.),(美)罗伯茨(Roberts,J.) 著,李宝峰,富弘毅,李韬 译 本书从原理、技术...

晨曦之光
2012/03/09
318
1
《程序员面试宝典》精华 编程语言部分

《程序员面试宝典》精华 编程语言部分 正所谓取其精华,去其糟粕。本文谨记录下《程序员面试宝典》一些关键的知识点、易错点,对于一些虽然重要但书中没有解释清楚的地方不做记录。当然这里的...

modernizr
2014/08/11
410
2

没有更多内容

加载失败,请刷新页面

加载更多

下一页

TensorFlow 作用域与操作符的受限范围

variable_scope 影响变量和操作符 name_scope 只影响操作符 with tf.name_scope(""),使用空字符串将作用域返回到顶层 tf.variable_scope("") 相当于添加一个空层 import tensorflow as tf...

阿豪boy
2分钟前
0
0
Java面试基础篇——第六篇:常见Map类的区别

常见的map类有: HashMap, ConcurrentHashMap (Jdk1.8) , LinkedHashMap, TreeMap, Hashtable。 其中我们最常用的莫过于HashMap, 和并发情况下使用的ConcurrentHashMap了,它们的主要区别就在...

developlee的潇洒人生
4分钟前
0
0
崛起于Springboot2.X之前端模版freemaker(23)

1、配置文件 spring: freemarker: allow-request-override: false cache: true check-template-location: true charset: UTF-8 content-type: text/html ......

木九天
20分钟前
1
0
spring-boot:run启动时,指定spring.profiles.active

Maven启动指定Profile通过-P,如mvn spring-boot:run -Ptest,但这是Maven的Profile。 如果要指定spring-boot的spring.profiles.active,则必须使用mvn spring-boot:run -Drun.profiles=test......

夜黑人模糊灬
22分钟前
0
0
大数据分析挖掘技术学习:Python文本分类

引言 文本分类作为自然语言处理任务之一,被广泛应用于解决各种商业领域的问题。文本分类的目的是将 文本/文档 自动地归类为一种或多种预定义的类别。常见的文本分类应用如下: • 理解社交媒...

加米谷大数据
27分钟前
0
0
istio-0.8 指标监控,prometheus,grafana

配置: https://istio.io/docs/tasks/telemetry/metrics-logs/ https://istio.io/docs/tasks/telemetry/tcp-metrics/ envoy拦截请求>上报mixer>对接prometheus>grafana 效果截图: promethe......

xiaomin0322
28分钟前
0
0
公众号推荐

阿里技术 书籍:《不止代码》

courtzjl
31分钟前
0
0
关于改进工作效率

1.给不同的业务线建立需求群,所有的数据需求都在群里面提。 2.对于特别难搞定的事情,到对应的技术哪去做,有问题随时沟通。 3.定期给工作总结形成方法论。 4.学习新的技术,尝试用新的方法...

Avner
38分钟前
0
0
关于thinkphp 框架开启路径重写,无法获取Authorization Header

今天遇到在thinkphp框架中获取不到header头里边的 Authorization ,后来在.htaccess里面加多一项解决,记录下: <IfModule mod_rewrite.c> Options +FollowSymlinks -Multiviews Rewrite......

殘留回憶
42分钟前
0
0
centos 使用yum安装nginx后如何添加模块 10

centos 使用yum安装nginx后如何添加模块 10 centos6.2版本,使用yum来安装了nginx,但是最近需要重新添加模块,所以就傻了,询问下有人知道怎么重新添加模块吗? PS:俺是新手,需要高手救助...

linjin200
45分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部