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

fzyz_sb

5.2 二叉树

``````#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. 最小数是指在树中,一个结点有儿子结点,其关键字都不大于儿子结点的关键字值.最小堆是一棵完全二叉树,也是一棵最小数.

5.7 二叉搜索树

### 评论(2)

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

2013/01/06
262
0

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

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

2012/12/13
0
0

2016/02/04
107
2

2017/11/07
0
0

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?

pearma
50分钟前
1
0

Skyogo

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

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

4
0