数据结构(C语言版)第五章:树
博客专区 > fzyz_sb 的博客 > 博客详情
数据结构(C语言版)第五章:树
fzyz_sb 发表于4年前
数据结构(C语言版)第五章:树
  • 发表于 4年前
  • 阅读 291
  • 收藏 14
  • 点赞 0
  • 评论 2

移动开发云端新模式探索实践 >>>   

摘要: 书籍<数据结构(C语言版)>,对基础的数据结构进行学习,通过C语言实现

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 二叉搜索树

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


标签: 数据结构 C
  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 400
博文 209
码字总数 447144
评论 (2)
湖心亭看雪
这位大神,请问你懂极大极小算法吗?最近再搞一个棋类游戏,一直搞不懂
fzyz_sb

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

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

抱歉,没了解过这个算法,所以不懂1
×
fzyz_sb
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: