文档章节

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

fzyz_sb
 fzyz_sb
发布于 2013/12/07 18:15
字数 1281
阅读 296
收藏 14

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
数据结构(C语言版)第九章:堆结构

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

fzyz_sb
2013/12/16
0
0
windows程序设计自学笔记(一)

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

赵西元
2012/12/13
0
0
业余爱好者的C程序设计学习之路

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

四彩
2016/02/04
107
2
做游戏,学编程(C语言) 网易云课堂MOOC视频

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

童晶
2017/11/07
0
0

没有更多内容

加载失败,请刷新页面

加载更多

一步步编写自己的PHP爬取代理IP项目(二)

这一章节我们正式开展我们的爬虫项目,首先我们先要知道哪个网站能获取到免费代理IP,目前比较火的有西刺代理,快代理等,这里我们拿西刺代理作为例子。 这里就是一个个免费的IP地址以及各自...

NateHuang
27分钟前
1
0
11-利用思维导图梳理JavaSE-Java的反射机制

11-利用思维导图梳理JavaSE-Java的反射机制 主要内容 1.反射与Class类 1.1.反射概念 1.2.Class类 1.3.实例化Class类 1.4.反射的作用 1.5.Class对象的作用 2.反射的深入应用 2.1.调用无参的成...

飞鱼说编程
34分钟前
1
0
How to serve the world from home computer?

最近在开发web应用,很想知道,通过公网来访问,效果会不会好。今天在做家务的时候,突然想到,如果我自己写一个ip转发的工具,不就可以实现了吗?但是转过头一想,这么大众的想法,怎么会没...

pearma
50分钟前
1
0
今天在码云遇到一个很有意思的人 for Per.js

今天在码云遇到一个很有意思的人,他在我的Per.js项目下面评论了一句,大意为“你试试这句代码,看看速度到底是你快还是Vue快”【当然,这个评论被我手残不小心删掉了...】。 然后我就试了,...

Skyogo
今天
50
0
Java -------- 首字母相关排序总结

Java 字符串数组首字母排序 字符串数组按首字母排序:(区分大小写) String[] strings = new String[]{"ba","aa","CC","Ba","DD","ee","dd"}; Arrays.sort(strings); for (int i ...

切切歆语
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部