二叉树遍历【很好的文章】

by admin on 2020年1月20日

/************************************************************************/
/*
coder:huifeng00                                                      */
/* 时间:2010-5-12 下午
9点                                             */
/*
实现:多叉树的后序遍历,先序遍历,及其释放操作                      
*/
/* 语言:C      
工具:VC++6.0                                          */
/************************************************************************/
#include <stdlib.h>
#include <memory.h>
#include <stdio.h>

平衡二叉树(AVL)的实现,附可运行C语言代码

最近几月一直在自学C语言和数据结构,先是写了排序二叉树,觉得平衡二叉树作为一个经典数据结构,有必要实现一下。

 

网上看了些资料,在AVL和红黑树之间考虑,最后个人还是倾向于AVL。

 

不同于标准AVL的是,笔者没有使用平衡因子,直接根据左右孩子的高度差值判断是否平衡。整个平衡二叉树是在普通二叉查找树的基础上修改得到的,对于学习数据结构的同学来说,这样逐步提高难度,写起来挑战性没那么大。

 

代码经测试是可以运行,并实现插入、删除、修改节点时都可以保持平衡。相对于普通二叉查找树,AVL在查找时效率高耗时短,但为了保持高度平衡,必须牺牲插入和删除操作的复杂度。本文将分步讲解如何编写平衡二叉树,全文最后附有完整代码。

 

当左右子树的高度差超过1时(即≥2,在实际处理时,等于2即为不平衡,进行调整操作,所以不会出现大于2的情况),整棵树失去平衡。写代码之前先了解AVL是如何使二叉树保持平衡,这里涉及到对节点的旋转操作,分四种情况,左左,右右,左右,右左。下面分别解释:

 

一、左左单旋转

 

在节点x的左孩子插入节点b

 

①x无右孩子,旋转节点a即可达到平衡

 

②x有右孩子c,旋转节点a后,根据a>c>x,需将节点c移动到a的左子树

 

 

 

函数代码如下:

 

复制代码

 1 static BTNode *singleRotateLL(BTree *BT, BTNode *phead)

 2 {//不平衡情况为左左的单旋转操作

 3     BTNode *temp;

 4 

 5     if(phead == NULL)

澳门新葡亰信誉平台游戏, 6         return 0;

 7 

 8     temp = phead->lchild;

 9     

10     if(temp->rchild != NULL){

11         phead->lchild = temp->rchild;

12         phead->lchild->height = tree_node_height(BT,
phead->lchild);

13     }

14     else

15         phead->lchild = NULL;

16 

17     temp->rchild = phead;

18     if(temp->rchild->data == BT->phead->data){

19         BT->phead = temp;

20     }

21     phead = temp;

22     temp->rchild->height = tree_node_height(BT,
temp->rchild);

23     temp->height = tree_node_height(BT, temp);

24     phead->height = tree_node_height(BT, phead);

25     

26     return phead;

27 }

复制代码

二、右右单旋转

 

在节点x的右孩子插入节点b

 

①x无左孩子,旋转节点a即可达到平衡

 

②x有左孩子c,旋转节点a后,根据x>c>a,需将节点c移动到a的右子树

 

 

 

函数代码如下:

 

复制代码

 1 static BTNode *singleRotateRR(BTree *BT, BTNode *phead)

 2 {//不平衡情况为右右的单旋转操作

 3     BTNode *temp;

 4 

 5     if(phead == NULL)

 6         return 0;

 7 

 8     temp = phead->rchild;

 9 

10     if(temp->lchild != NULL){

11         phead->rchild = temp->lchild;

12         phead->rchild->height = tree_node_height(BT,
phead->rchild);

13     }

14     else

15         phead->rchild = NULL;

16 

17     temp->lchild = phead;

18     if(temp->lchild->data == BT->phead->data){

19         BT->phead = temp;

20     }

21     phead = temp;

22     temp->lchild->height = tree_node_height(BT,
temp->lchild);

23     temp->height = tree_node_height(BT, temp);

24     phead->height = tree_node_height(BT, phead);

25 

26     return phead;

27 }

复制代码

注:需要注意的是节点旋转后,节点赋值和高度的更新,初学者很容易忽略或是弄错赋值顺序

 

三、左右双旋转

 

在节点x的右孩子插入节点b

 

①x无左孩子,②x有左孩子c,这两种情况的处理相同,首先对x节点进行右右单旋转操作,然后对a节点进行左左单旋转操作

 

 

 

函数代码如下:

 

复制代码

 1 static BTNode *doubleRotateLR(BTree *BT, BTNode *phead)

 2 {//不平衡情况为左右的双旋转操作

 3     BTNode *temp;

 4 

 5     if(phead == NULL)

 6         return 0;

 7 

 8     temp = phead->lchild;    

 9     phead->lchild = singleRotateRR(BT, temp);

10     temp = phead;

11     phead = singleRotateLL(BT, temp);

12 

13     return phead;

14 }

复制代码

四、右左双旋转

 

在节点x的右孩子插入节点b

 

①x无右孩子,②x有右孩子c,这两种情况的处理相同,首先对x节点进行左左单旋转操作,然后对a节点进行右右单旋转操作

 

 

 

函数代码如下:

 

复制代码

 1 static BTNode *doubleRotateRL(BTree *BT, BTNode *phead)

 2 {//不平衡情况为右左的双旋转操作

 3     BTNode *temp;

 4 

 5     if(phead == NULL)

 6         return 0;

 7 

 8     temp = phead->rchild;

 9     phead->rchild = singleRotateLL(BT, temp);

10     temp = phead;

11     phead = singleRotateRR(BT, temp);

12 

13     return phead;

14 }

复制代码

 

 

弄清楚了怎样通过旋转达到平衡状态,接下来一步一步构造平衡二叉树。

 

第一步,我们要在二叉树的节点中加一个属性:高度,在后面的插入和删除函数中将会用到。

 

结构体代码如下:

 

1 typedef struct _BTNode{

2     TYPE data;

3     int height;         

4     struct _BTNode *lchild;

5     struct _BTNode *rchild;

6 }BTNode;

 

 

第二步,需要添加三个辅助函数,一是求节点的高度,而是遍历求树中每个节点的高度(在删除函数中会用到),三是求两个高度的最大值。

 

复制代码

 1 static int tree_node_height(BTree *BT, BTNode *phead)

 2
{//求节点的高度,写成函数解决指针为空的情况,默认空节点的高度为-1,只有一个根节点的节点的高度为0,每多一层高度加1

 3     if(phead != NULL){

 4         if(phead->lchild == NULL && phead->rchild == NULL){

 5             return 0;

 6         }

 7         else{

 8             return phead->height =
max_height(tree_node_height(BT, phead->lchild),
tree_node_height(BT, phead->rchild)) + 1;

 9         }

10     }

11     else{

12         return -1;

13     }

14 }

15 

16 static void tree_height(BTree *BT, BTNode *phead)

17 {//遍历求树中每个节点的高度

18     if(phead == NULL)

19         return;

20 

21     tree_node_height(BT, phead);

22     if(phead->lchild != NULL)

23         tree_node_height(BT, phead->lchild);

24     if(phead->rchild != NULL)

25         tree_node_height(BT, phead->rchild);

26 }

27 

28 static int max_height(int height1, int height2)

29 {//求两个高度的最大值

30     if(height1 > height2)

31         return height1;

32     else

33         return height2;

34 }

复制代码

 第三步,插入

 

 插入操作与二叉查找树的操作基本相同,只是在插入后需判断是否平衡,如果不平衡,进行旋转调整。因为BTNode没有使用父节点属性,所以需要用变量存储插入位置,以便调整后可以接回到二叉树上。树顶的根节点需特殊处理

 

复制代码

 1 static BOOL tree_add(BTree *BT, BTNode *phead, TYPE value)

 2 {//按序插入结点

 3     if(phead == NULL)

 4         return 0;

 5 

 6     if(phead->data == value)

 7         return 0;

 8 

 9     else{

10         if(phead->data > value){

11             if(phead->lchild == NULL){

12                 BTNode *newnode = (BTNode*)calloc(1,
sizeof(BTNode));

13                 newnode->data = value;

14                 newnode->lchild = newnode->rchild = NULL;

15                 phead->lchild = newnode;

16             }

17             else{

18                 tree_add(BT, phead->lchild, value);

19 

20                 //判断插入节点后是否平衡,并调整

21                 BTNode *root;

22                 if(phead = BT->phead)

23                     root = phead;

24                 else

25                     root = phead->lchild;

26             

27                 if(tree_node_height(BT, root->lchild) –
tree_node_height(BT, root->rchild) == 2){

28                     if(root->lchild->data > value){

29                         root = singleRotateLL(BT, root);

30                     }

31                     else{

32                         root = doubleRotateLR(BT, root);

33                     }

34                 }

35                 phead = root;

36             }

37         }

38         else{

39             if(phead->rchild == NULL){

40                 BTNode *newnode = (BTNode*)calloc(1,
sizeof(BTNode));

41                 newnode->data = value;

42                 newnode->lchild = newnode->rchild = NULL;

43                 phead->rchild = newnode;                    

44             }

45             else{

46                 tree_add(BT, phead->rchild, value);

47                 

48                 //判断插入节点后是否平衡,并调整

49                 BTNode *root;

50                 if(phead = BT->phead)

51                     root = phead;

52                 else

53                     root = phead->rchild;

54                     

55                 if(tree_node_height(BT, root->rchild) –
tree_node_height(BT, root->lchild) == 2){

56                     if(root->rchild->data < value){

57                         root = singleRotateRR(BT, root);

58                     }

59                     else{

60                         root = doubleRotateRL(BT, root);

61                     }

62                 }

63                 phead = root;

64             }            

65         }

66             phead->height = tree_node_height(BT, phead);

67             return 1;

68     }

69 

70     return 0;

71 }

复制代码

第四步,删除

 

平衡二叉树的删除操作比插入更复杂,因为删除后会引起一系列节点高度的改变,删除后将剩余子树接回二叉树时,要分三种情况处理,被删除节点是:顶部根节点、底部叶子(无子树)、普通节点。

 

复制代码

 1 static BOOL tree_del(BTree *BT, BTNode **phead, TYPE value)

 2 {//删除结点

 3     BTNode *temp;

 4     BTNode *root;

 5     int flag;      
 //flag标记被删除的节点,默认顶部节点flag为0,左边节点flag为-1,右边节点flag为1

 6 

 7     if(*phead == NULL)

 8         return 0;

 9         

10     if(*phead == BT->phead){

11         flag = 0;

12         root = *phead;

13     }

14 

15     else if((*phead)->lchild != NULL){

16         flag = -1;

17         root = (*phead)->lchild;

18     }

19 

20     else if((*phead)->rchild != NULL){

21         flag = 1;

22         root = (*phead)->rchild;

23     }

24     else if((*phead)->lchild == NULL && (*phead)->rchild ==
NULL)

25         root = *phead;

26     

27     if(root->data == value){

28         if(root->lchild != NULL){

29             temp = BT->search_max(BT, &root->lchild, 1);

30             temp->lchild = root->lchild;

31              temp->rchild = root->rchild;

32             free(root);

33             root = temp;

34             if(flag == 0)

35                 BT->phead = root;

36             else

37                 (*phead)->lchild = root;

38         }

39         else if(root->rchild != NULL){

40             temp = BT->search_min(BT, &root->rchild, 1);   

41             temp->lchild = root->lchild;

42             temp->rchild = root->rchild;

43             free(root);

44             root = temp;

45             if(flag == 0)

46                 BT->phead = root;

47             else

48                 (*phead)->rchild = root;

49         }

50         else{

51             if(flag == 0)

52                 free(*phead);

53             else if(flag = -1){

54                 free((*phead)->lchild);

55                 (*phead)->lchild = NULL;

56             }

57             else if(flag = 1){

58                 free((*phead)->rchild);

59                 (*phead)->rchild = NULL;

60             }

61         }

62          

63         tree_height(BT, BT->phead);  
 //删除节点后,求每个节点的新高度

64 

65         if(flag == 0)

66             return 1;

67         if(flag == -1){

68             if(tree_node_height(BT, (*phead)->rchild) –
tree_node_height(BT, (*phead)->lchild) == 2){

69                 if((*phead)->rchild->rchild != NULL){

70                     root = singleRotateRR(BT, *phead);

71                 }

72                 else{

73                     root = doubleRotateRL(BT, *phead);

74                 }

75             }

76         }

77         else{

78             if(tree_node_height(BT, (*phead)->lchild) –
tree_node_height(BT, (*phead)->rchild) == 2){

79                 if((*phead)->lchild->lchild != NULL){

80                     root = singleRotateLL(BT, *phead);

81                 }

82                 else{

83                     root = doubleRotateLR(BT, *phead);

84                 }

85             }

86         }

87             

88         return 1;

89     }

90     else if(root->data > value)

91         return BT->del(BT, &root->lchild, value);

92     else

93         return BT->del(BT, &root->rchild, value);

94 

95     return 0;

96 }

除了插入和删除操作,其他操作均与普通二叉查找树一样。

 

如果读者发现错误或有更好的处理方法,请指出,以便修改完善。 

 

 

 

头文件binary.h代码:

 

 

复制代码

 1 #ifndef BINARY_H

 2 #define BINARY_H

 3 

 4 typedef int TYPE;

 5 typedef int BOOL;

 6 

 7 typedef struct _BTNode{

 8     TYPE data;

 9     int height;         

10     struct _BTNode *lchild;

11     struct _BTNode *rchild;

12 }BTNode;

13 

14 typedef struct _BTree{

15     BTNode *phead;    

16 

17     void(*init)(struct _BTree *BT, TYPE head_value);

18     void(*exit)(struct _BTree *BT);

19     void(*print)(struct _BTree *BT, BTNode *phead);

20 

21     BOOL(*add)(struct _BTree *BT, BTNode *phead, TYPE value);

22     BOOL(*del)(struct _BTree *BT, BTNode **phead, TYPE value);

23     BOOL(*del_tree)(struct _BTree *BT, BTNode **phead);

24     BOOL(*alter)(struct _BTree *BT, BTNode *phead, TYPE value,
TYPE new_value);

25     BTNode *(*search)(struct _BTree *BT, BTNode *phead, TYPE
value);

26 

27     BTNode *(*search_min)(struct _BTree *BT, BTNode **phead,
int flag);

28     BTNode *(*search_max)(struct _BTree *BT, BTNode **phead,
int flag);    

29 

30     void(*pre_traverse)(struct _BTree *BT, BTNode *phead);

31     void(*mid_traverse)(struct _BTree *BT, BTNode *phead);

32     void(*last_traverse)(struct _BTree *BT, BTNode *phead);

33 

34     //以下为实现AVL所需函数

35     int (*node_height)(_BTree *BT, BTNode *phead);

36     void (*height)(_BTree *BT, BTNode *phead);

37     int (*max_height)(int height1, int height2);

38     BTNode *(*singleRotateLL)(_BTree *BT, BTNode *phead);

39     BTNode *(*singleRotateRR)(_BTree *BT, BTNode *phead);

40     BTNode *(*doubleRotateLR)(_BTree *BT, BTNode *phead);

41     BTNode *(*doubleRotateRL)(_BTree *BT, BTNode *phead);

42 }BTree;

43 

44 void tree_init(BTree *BT, TYPE value);

45 void tree_exit(BTree *BT);

46 

47 #endif

复制代码

源文件binary.cpp代码:

 

 

复制代码

  1 #include <stdio.h>

  2 #include <string.h>

  3 #include <stdlib.h>

  4 

  5 #include “binary.h”

  6 

  7 void tree_init(BTree *BT, TYPE head_value);

  8 void tree_exit(BTree *BT);

  9 void tree_print(BTree *BT, BTNode *phead);

 10 static BOOL tree_add(BTree *BT, BTNode *phead, TYPE value);

 11 static BOOL tree_del(BTree *BT, BTNode **phead, TYPE value);

 12 static BOOL tree_del_tree(BTree *BT, BTNode **phead);

 13 static BOOL tree_alter(BTree *BT, BTNode *phead, TYPE value, TYPE
new_value);

 14 static BTNode *tree_search(BTree *BT, BTNode *phead, TYPE
value);

 15 static BTNode *tree_search_min(BTree *BT, BTNode **phead, int
flag);

 16 static BTNode *tree_search_max(BTree *BT, BTNode **phead, int
flag);

 17 static void tree_pre_traverse(BTree *BT, BTNode *phead);

 18 static void tree_mid_traverse(BTree *BT, BTNode *phead);

 19 static void tree_last_traverse(BTree *BT, BTNode *phead);

 20 

 21 //以下为实现AVL所需函数

 22 static int tree_node_height(BTree *BT, BTNode *phead);

 23 static void tree_height(BTree *BT, BTNode *phead);

 24 static int max_height(int height1, int height2);

 25 static BTNode *singleRotateLL(BTree *BT, BTNode *phead);

 26 static BTNode *singleRotateRR(BTree *BT, BTNode *phead);

 27 static BTNode *doubleRotateLR(BTree *BT, BTNode *phead);

 28 static BTNode *doubleRotateRL(BTree *BT, BTNode *phead);

 29 

 30 

 31 void tree_init(BTree *BT, TYPE head_value)

 32 {//初始化

 33     BT->phead = (BTNode*)calloc(1, sizeof(BTNode));

 34     BT->phead->data = head_value;

 35     

 36     BT->phead->lchild = BT->phead->rchild = NULL;

 37 

 38     BT->add = tree_add;

 39     BT->del = tree_del;

 40     BT->print = tree_print;

 41     BT->del_tree = tree_del_tree;

 42     BT->alter = tree_alter;

 43     BT->search = tree_search;

 44     BT->search_min = tree_search_min;

 45     BT->search_max = tree_search_max;

 46     BT->pre_traverse = tree_pre_traverse;

 47     BT->mid_traverse = tree_mid_traverse;

 48     BT->last_traverse = tree_last_traverse;

 49     BT->exit = tree_exit;

 50 

 51     BT->node_height = tree_node_height;

 52     BT->height = tree_height;

 53     BT->max_height = max_height;

 54     BT->singleRotateLL = singleRotateLL;

 55     BT->singleRotateRR = singleRotateRR;

 56     BT->doubleRotateLR = doubleRotateLR;

 57     BT->doubleRotateRL = doubleRotateRL;

 58 }

 59 

 60 void tree_exit(BTree *BT)

 61 {//结束操作

 62     if(BT != NULL)

 63         BT->del_tree(BT, &BT->phead);

 64 }

 65 

 66 void tree_print(BTree *BT, BTNode *phead)

 67 {//打印结点

 68     if(phead != NULL)

 69         printf(“%dn”, phead->data);

 70 }

 71 

 72 static BOOL tree_add(BTree *BT, BTNode *phead, TYPE value)

 73 {//按序插入结点

 74     if(phead == NULL)

 75         return 0;

 76 

 77     if(phead->data == value)

 78         return 0;

 79 

 80     else{

 81         if(phead->data > value){

 82             if(phead->lchild == NULL){

 83                 BTNode *newnode = (BTNode*)calloc(1,
sizeof(BTNode));

 84                 newnode->data = value;

 85                 newnode->lchild = newnode->rchild = NULL;

 86                 phead->lchild = newnode;

 87             }

 88             else{

 89                 tree_add(BT, phead->lchild, value);

 90 

 91                 //判断插入节点后是否平衡,并调整

 92                 BTNode *root;

 93                 if(phead = BT->phead)

 94                     root = phead;

 95                 else

 96                     root = phead->lchild;

 97             

 98                 if(tree_node_height(BT, root->lchild) –
tree_node_height(BT, root->rchild) == 2){

 99                     if(root->lchild->data > value){

100                         root = singleRotateLL(BT, root);

101                     }

102                     else{

103                         root = doubleRotateLR(BT, root);

104                     }

105                 }

106                 phead = root;

107             }

108         }

109         else{

110             if(phead->rchild == NULL){

111                 BTNode *newnode = (BTNode*)calloc(1,
sizeof(BTNode));

112                 newnode->data = value;

113                 newnode->lchild = newnode->rchild = NULL;

114                 phead->rchild = newnode;                    

115             }

116             else{

117                 tree_add(BT, phead->rchild, value);

118                 

119                 //判断插入节点后是否平衡,并调整

120                 BTNode *root;

121                 if(phead = BT->phead)

122                     root = phead;

123                 else

124                     root = phead->rchild;

125                     

126                 if(tree_node_height(BT, root->rchild) –
tree_node_height(BT, root->lchild) == 2){

127                     if(root->rchild->data < value){

128                         root = singleRotateRR(BT, root);

129                     }

130                     else{

131                         root = doubleRotateRL(BT, root);

132                     }

133                 }

134                 phead = root;

135             }            

136         }

137             phead->height = tree_node_height(BT, phead);

138             return 1;

139     }

140 

141     return 0;

142 }

143 

144 static BOOL tree_del(BTree *BT, BTNode **phead, TYPE value)

145 {//删除结点

146     BTNode *temp;

147     BTNode *root;

148     int flag;      
 //flag标记被删除的节点,默认顶部节点flag为0,左边节点flag为-1,右边节点flag为1

149 

150     if(*phead == NULL)

151         return 0;

152         

153     if(*phead == BT->phead){

154         flag = 0;

155         root = *phead;

156     }

157 

158     else if((*phead)->lchild != NULL){

159         flag = -1;

160         root = (*phead)->lchild;

161     }

162 

163     else if((*phead)->rchild != NULL){

164         flag = 1;

165         root = (*phead)->rchild;

166     }

167     else if((*phead)->lchild == NULL && (*phead)->rchild ==
NULL)

168         root = *phead;

169     

170     if(root->data == value){

171         if(root->lchild != NULL){

172             temp = BT->search_max(BT, &root->lchild, 1);

173             temp->lchild = root->lchild;

174              temp->rchild = root->rchild;

175             free(root);

176             root = temp;

177             if(flag == 0)

178                 BT->phead = root;

179             else

180                 (*phead)->lchild = root;

181         }

182         else if(root->rchild != NULL){

183             temp = BT->search_min(BT, &root->rchild, 1);   

184             temp->lchild = root->lchild;

185             temp->rchild = root->rchild;

186             free(root);

187             root = temp;

188             if(flag == 0)

189                 BT->phead = root;

190             else

191                 (*phead)->rchild = root;

192         }

193         else{

194             if(flag == 0)

195                 free(*phead);

196             else if(flag = -1){

197                 free((*phead)->lchild);

198                 (*phead)->lchild = NULL;

199             }

200             else if(flag = 1){

201                 free((*phead)->rchild);

202                 (*phead)->rchild = NULL;

203             }

204         }

205          

206         tree_height(BT, BT->phead);  
 //删除节点后,求每个节点的新高度

207 

208         if(flag == 0)

209             return 1;

210         if(flag == -1){

211             if(tree_node_height(BT, (*phead)->rchild) –
tree_node_height(BT, (*phead)->lchild) == 2){

212                 if((*phead)->rchild->rchild != NULL){

213                     root = singleRotateRR(BT, *phead);

214                 }

215                 else{

216                     root = doubleRotateRL(BT, *phead);

217                 }

218             }

219         }

220         else{

221             if(tree_node_height(BT, (*phead)->lchild) –
tree_node_height(BT, (*phead)->rchild) == 2){

222                 if((*phead)->lchild->lchild != NULL){

223                     root = singleRotateLL(BT, *phead);

224                 }

225                 else{

226                     root = doubleRotateLR(BT, *phead);

227                 }

228             }

229         }

230             

231         return 1;

232     }

233     else if(root->data > value)

234         return BT->del(BT, &root->lchild, value);

235     else

236         return BT->del(BT, &root->rchild, value);

237 

238     return 0;

239 }

240 

241 static BOOL tree_del_tree(BTree *BT, BTNode **phead)

242 {//删除二叉树

243     if(*phead == NULL)

244         return 0;

245     

246     if((*phead)->lchild != NULL)

247         BT->del_tree(BT, &(*phead)->lchild);

248     if((*phead)->rchild != NULL)

249         BT->del_tree(BT, &(*phead)->rchild);

250 

251     free(*phead);

252     *phead = NULL;

253 

254     return 1;

255 }

256 

257 static BOOL tree_alter(BTree *BT, BTNode *phead, TYPE value, TYPE
new_value)

258 {//更改结点的值(先删除,后插入)

259     if(phead == NULL)

260         return 0;

261 

262     if(value == new_value)

263         return 1;

264 

265     if(BT->del(BT, &phead, value) != 0){

266         if(BT->add(BT, phead, new_value) != 0)

267             return 1;

268         else

269             return 0;

270     }

271     else

272         return 0;

273 }

274 

275 static BTNode *tree_search(BTree *BT, BTNode *phead, TYPE value)

276 {//查找结点

277     BTNode *temp;

278 

279     if(phead == NULL)

280         return NULL;

281 

282     if(phead->data == value)

283         return phead;

284     if(phead->lchild != NULL){

285         temp = BT->search(BT, phead->lchild, value);

286         if(temp != NULL)

287             return temp;

288     }

289     if(phead->rchild != NULL){

290         temp = BT->search(BT, phead->rchild, value);

291         if(temp != NULL)

292             return temp;

293     }

294 

295     return NULL;

296 }

297 

298 static BTNode *tree_search_min(BTree *BT, BTNode **phead, int
flag)

299 {//查找最小结点

300     BTNode *temp;

301 

302     if(*phead == NULL)

303         return NULL;

304 

305     if((*phead)->lchild == NULL){

306         temp = *phead;

307         if(flag == 1)

308             *phead = (*phead)->rchild;

309         return temp;

310     }

311     else

312         return BT->search_min(BT, &(*phead)->lchild, flag);

313 }

314 

315 static BTNode *tree_search_max(BTree *BT, BTNode **phead, int
flag)

316 {//查找最大结点

317     BTNode *temp;

318 

319     if(*phead == NULL)

320         return NULL;

321 

322     if((*phead)->rchild == NULL){

323         temp = *phead;

324         if(flag == 1)

325             *phead = (*phead)->lchild;

326         return temp;

327     }

328     else

329         return BT->search_max(BT, &(*phead)->rchild, flag);

330 }

331 

332 static void tree_pre_traverse(BTree *BT, BTNode *phead)

333 {//先序遍历二叉树

334     if(phead == NULL)

335         return;

336 

337     BT->print(BT, phead);

338     if(phead->lchild != NULL)

339         BT->pre_traverse(BT, phead->lchild);

340     if(phead->rchild != NULL)

341         BT->pre_traverse(BT, phead->rchild);

342 }

343 

344 static void tree_mid_traverse(BTree *BT, BTNode *phead)

345 {//中序遍历二叉树

346     if(phead == NULL)

347         return;

348 

349     if(phead->lchild != NULL)

350         BT->mid_traverse(BT, phead->lchild);

351     BT->print(BT, phead);

352     if(phead->rchild != NULL)

353         BT->mid_traverse(BT, phead->rchild);

354 }

355 

356 static void tree_last_traverse(BTree *BT, BTNode *phead)

357 {//后序遍历二叉树

358     if(phead == NULL)

359         return;

360 

361     if(phead->lchild != NULL)

362         BT->last_traverse(BT, phead->lchild);

363     if(phead->rchild != NULL)

364         BT->last_traverse(BT, phead->rchild);

365     BT->print(BT, phead);

366 }

367 

368 static int tree_node_height(BTree *BT, BTNode *phead)

369
{//求节点的高度,写成函数解决指针为空的情况,默认空节点的高度为-1,只有一个根节点的节点的高度为0,每多一层高度加1

370     if(phead != NULL){

371         if(phead->lchild == NULL && phead->rchild == NULL){

372             return 0;

373         }

374         else{

375             return phead->height =
max_height(tree_node_height(BT, phead->lchild),
tree_node_height(BT, phead->rchild)) + 1;

376         }

377     }

378     else{

379         return -1;

380     }

381 }

382 

383 static void tree_height(BTree *BT, BTNode *phead)

384 {//遍历求树中每个节点的高度

385     if(phead == NULL)

386         return;

387 

388     tree_node_height(BT, phead);

389     if(phead->lchild != NULL)

390         tree_node_height(BT, phead->lchild);

391     if(phead->rchild != NULL)

392         tree_node_height(BT, phead->rchild);

393 }

394 

395 static int max_height(int height1, int height2)

396 {//求两个高度的最大值

397     if(height1 > height2)

398         return height1;

399     else

400         return height2;

401 }

402 

403 static BTNode *singleRotateLL(BTree *BT, BTNode *phead)

404 {//不平衡情况为左左的单旋转操作

405     BTNode *temp;

406 

407     if(phead == NULL)

408         return 0;

409 

410     temp = phead->lchild;

411     

412     if(temp->rchild != NULL){

413         phead->lchild = temp->rchild;

414         phead->lchild->height = tree_node_height(BT,
phead->lchild);

415     }

416     else

417         phead->lchild = NULL;

418 

419     temp->rchild = phead;

420     if(temp->rchild->data == BT->phead->data){

421         BT->phead = temp;

422     }

423     phead = temp;

424     temp->rchild->height = tree_node_height(BT,
temp->rchild);

425     temp->height = tree_node_height(BT, temp);

426     phead->height = tree_node_height(BT, phead);

427     

428     return phead;

429 }

430 

431 static BTNode *singleRotateRR(BTree *BT, BTNode *phead)

432 {//不平衡情况为右右的单旋转操作

433     BTNode *temp;

434 

435     if(phead == NULL)

436         return 0;

437 

438     temp = phead->rchild;

439 

440     if(temp->lchild != NULL){

441         phead->rchild = temp->lchild;

442         phead->rchild->height = tree_node_height(BT,
phead->rchild);

443     }

444     else

445         phead->rchild = NULL;

446 

447     temp->lchild = phead;

448     if(temp->lchild->data == BT->phead->data){

449         BT->phead = temp;

450     }

451     phead = temp;

452     temp->lchild->height = tree_node_height(BT,
temp->lchild);

453     temp->height = tree_node_height(BT, temp);

454     phead->height = tree_node_height(BT, phead);

455 

456     return phead;

457 }

458 static BTNode *doubleRotateLR(BTree *BT, BTNode *phead)

459 {//不平衡情况为左右的双旋转操作

460     BTNode *temp;

461 

462     if(phead == NULL)

463         return 0;

464 

465     temp = phead->lchild;    

466     phead->lchild = singleRotateRR(BT, temp);

467     temp = phead;

468     phead = singleRotateLL(BT, temp);

469 

470     return phead;

471 }

472 

473 static BTNode *doubleRotateRL(BTree *BT, BTNode *phead)

474 {//不平衡情况为右左的双旋转操作

475     BTNode *temp;

476 

477     if(phead == NULL)

478         return 0;

479 

480     temp = phead->rchild;

481     phead->rchild = singleRotateLL(BT, temp);

482     temp = phead;

483     phead = singleRotateRR(BT, temp);

484 

485     return phead;

486 }

487 

488 int main(int argc, char* argv[])

489 {//测试

490     BTree testtree;

491     testtree.init = tree_init;

492     testtree.init(&testtree, 9);

493 

494     testtree.add(&testtree, testtree.phead, 4);

495     testtree.add(&testtree, testtree.phead, 5);

496     testtree.add(&testtree, testtree.phead, 6);

497     testtree.add(&testtree, testtree.phead, 1);

498     testtree.add(&testtree, testtree.phead, 7);

499     testtree.add(&testtree, testtree.phead, 8);

500     testtree.add(&testtree, testtree.phead, 11);

501     testtree.add(&testtree, testtree.phead, 10);

502 

503     testtree.pre_traverse(&testtree, testtree.phead);

504     printf(“n”);

505     testtree.mid_traverse(&testtree, testtree.phead);

506     printf(“n”);

507     testtree.last_traverse(&testtree, testtree.phead);

508     printf(“n”);

509 

510     printf(“%dn”, (testtree.search(&testtree, testtree.phead,
8))->data);

511     printf(“n”);

512 

513     testtree.del(&testtree, &testtree.phead, 4);

514     testtree.del(&testtree, &testtree.phead, 1);

515     testtree.del(&testtree, &testtree.phead, 6);

516     testtree.alter(&testtree, testtree.phead, 9, 2);

517 

518     testtree.pre_traverse(&testtree, testtree.phead);

519     printf(“n”);

520     testtree.mid_traverse(&testtree, testtree.phead);

521     printf(“n”);

522     testtree.last_traverse(&testtree, testtree.phead);

523     printf(“n”);

524 

525     return 0;

526 }

最近几月一直在自学C语言和数据结构,先是写了排序二叉树,觉得平衡二叉树作为一个经典…

//转载请标明出处,原文地址:

#define MAXSIZE 5//这是多叉树最多可以的分支数
typedef struct _TREENODE
{
    int data;
    int cnChild;
    struct _TREENODE
*parent;
    struct _TREENODE
*child[MAXSIZE];
} TREENODE, *PTREENODE;

#include

PTREENODE InsertNode(PTREENODE *ppNode,int data)//向一个多叉树节点插入一个孩子节点
{
    int cnChild =
(*ppNode)->cnChild;
    PTREENODE temp = (PTREENODE)malloc(sizeof(TREENODE));
    temp->data = data;
    temp->cnChild =0;
    temp->parent = *ppNode;
    memset(temp->child,0,MAXSIZE);
    
    (*ppNode)->child[cnChild] = temp;
    (*ppNode)->cnChild++;
    return temp;
}

#include

void PrintTree(PTREENODE
root)//递归格式化先序打印多叉树
{
    static depth = 0;
    int i;
    if (root == NULL)
    {
        return;
    }
    for (i=0;i<depth;i++)
    {
        printf(” “);
    }
    printf(“%dn”,root->data);
    for (i=0;i<root->cnChild;i++)
    {
        depth++;
        PrintTree((root->child)[i]);
        depth–;
    }
}

#include

void PrintTreelast(PTREENODE
root)//递归格式化后序打印多叉树
{
    static depth = 0;
    int i;
    if (root == NULL)
    {
        return;
    }
    
    for (i=0;i<root->cnChild;i++)
    {
        depth++;
        PrintTreelast((root->child)[i]);
        depth–;
    }
    for (i=0;i<depth;i++)
    {
        printf(” “);
    }
    printf(“%dn”,root->data);
}
void destroyTree(PTREENODE
root)//释放多叉树节点所占内存
{
    int i;
    if (root == NULL)
    {
        return;
    }
    for (i=0;i<root->cnChild;i++)
    {
        destroyTree((root->child)[i]);
    }
    free(root);
}

usingnamespacestd;

int main()
{
    PTREENODE root = (PTREENODE)malloc(sizeof(TREENODE));//根节点
    PTREENODE temp1,temp2;
    root->data = 1;
    root->cnChild =0;
    root->parent = NULL;
    memset(root->child,0,MAXSIZE);
    
    
    //对根节点插入2个孩子
    temp1 = InsertNode(&root,11);
    temp2 = InsertNode(&root,12);
    
    //对第一个孩子节点插入3个孩子节点
    InsertNode(&temp1,111);
    InsertNode(&temp1,112);
    InsertNode(&temp1,113);
    
    //对第二个孩子节点插入3个孩子节点
    InsertNode(&temp2,121);
    InsertNode(&temp2,122);
    InsertNode(&temp2,123);
    
    PrintTree(root);//先序打印多叉树
    printf(“*****************n”);
    PrintTreelast(root);//后序打印多叉树
    destroyTree(root);//后序释放多叉树节点
    return 0;
}

//二叉树结点的描述

typedefstructBiTNode

{

chardata;

structBiTNode *lchild, *rchild;//左右孩子

}BiTNode,*BiTree;

 

//按先序遍历创建二叉树

//BiTree *CreateBiTree()     //返回结点指针类型

//void CreateBiTree(BiTree &root)      //引用类型的参数

voidCreateBiTree(BiTNode **root)//二级指针作为函数参数

{

charch;//要插入的数据

scanf(“n%c”, &ch);

//cin>>ch;

if(ch==’#’)

*root = NULL;

else

{

*root = (BiTNode *)malloc(sizeof(BiTNode));

(*root)->data = ch;

printf(“请输入%c的左孩子:”,ch);

CreateBiTree(&((*root)->lchild));

printf(“请输入%c的右孩子:”,ch);

CreateBiTree(&((*root)->rchild));

}

}

//前序遍历的算法程序

voidPreOrder(BiTNode *root)

{

if(root==NULL)

return;

printf(“%c “, root->data);//输出数据

PreOrder(root->lchild);//递归调用,前序遍历左子树

PreOrder(root->rchild);//递归调用,前序遍历右子树

}

//中序遍历的算法程序

voidInOrder(BiTNode *root)

{

if(root==NULL)

return;

InOrder(root->lchild);//递归调用,前序遍历左子树

printf(“%c “, root->data);//输出数据

InOrder(root->rchild);//递归调用,前序遍历右子树

}

//后序遍历的算法程序

voidPostOrder(BiTNode *root)

{

if(root==NULL)

return;

PostOrder(root->lchild);//递归调用,前序遍历左子树

PostOrder(root->rchild);//递归调用,前序遍历右子树

printf(“%c “, root->data);//输出数据

}

/*

二叉树的非递归前序遍历,前序遍历思想:先让根进栈,只要栈不为空,就可以做弹出操作,

每次弹出一个结点,记得把它的左右结点都进栈,记得右子树先进栈,这样可以保证右子树在栈中总处于左子树的下面。

*/

voidPreOrder_Nonrecursive(BiTree T)//先序遍历的非递归

{

if(!T)

return;

stack s;

s.push(T);

while(!s.empty())

{

BiTree temp = s.top();

cout<data<<” “;

s.pop();

if(temp->rchild)

s.push(temp->rchild);

if(temp->lchild)

s.push(temp->lchild);

}

}

voidPreOrder_Nonrecursive1(BiTree T)//先序遍历的非递归

{

if(!T)

return;

stack s;

BiTree curr = T;

while(curr != NULL || !s.empty())

{

while(curr != NULL)

{

cout<data<<”  “;

s.push(curr);

curr = curr->lchild;

}

if(!s.empty())

{

curr = s.top();

s.pop();

curr = curr->rchild;

}

}

}

voidPreOrder_Nonrecursive2(BiTree T)//先序遍历的非递归

{

if(!T)

return;

stack s;

while(T)// 左子树上的节点全部压入到栈中

{

s.push(T);

cout<data<<”  “;

T = T->lchild;

}

while(!s.empty())

{

BiTree temp = s.top()->rchild;// 栈顶元素的右子树

s.pop();// 弹出栈顶元素

while(temp)// 栈顶元素存在右子树,则对右子树同样遍历到最下方

{

cout<data<<”  “;

s.push(temp);

temp = temp->lchild;

}

}

}

voidInOrderTraverse1(BiTree T)// 中序遍历的非递归

{

if(!T)

return;

BiTree curr = T;// 指向当前要检查的节点

stack s;

while(curr != NULL || !s.empty())

{

while(curr != NULL)

{

s.push(curr);

curr = curr->lchild;

}//while

if(!s.empty())

{

curr = s.top();

s.pop();

cout<data<<”  “;

curr = curr->rchild;

}

}

}

voidInOrderTraverse(BiTree T)// 中序遍历的非递归

{

if(!T)

return;

stack s;

BiTree curr = T->lchild;// 指向当前要检查的节点

s.push(T);

while(curr != NULL || !s.empty())

{

while(curr != NULL)// 一直向左走

{

s.push(curr);

curr = curr->lchild;

}

curr = s.top();

s.pop();

cout<data<<”  “;

curr = curr->rchild;

}

}

voidPostOrder_Nonrecursive1(BiTree T)// 后序遍历的非递归

{

stack S;

BiTree curr = T ;// 指向当前要检查的节点

BiTree previsited = NULL;// 指向前一个被访问的节点

while(curr != NULL || !S.empty())// 栈空时结束

{

while(curr != NULL)// 一直向左走直到为空

{

S.push(curr);

curr = curr->lchild;

}

curr = S.top();

// 当前节点的右孩子如果为空或者已经被访问,则访问当前节点

if(curr->rchild == NULL || curr->rchild == previsited)

{

cout<data<<”  “;

previsited = curr;

S.pop();

curr = NULL;

}

else

curr = curr->rchild;// 否则访问右孩子

}

}

voidPostOrder_Nonrecursive(BiTree T)// 后序遍历的非递归     双栈法

{

stack s1 , s2;

BiTree curr ;// 指向当前要检查的节点

s1.push(T);

while(!s1.empty())// 栈空时结束

{

curr = s1.top();

s1.pop();

s2.push(curr);

if(curr->lchild)

s1.push(curr->lchild);

if(curr->rchild)

s1.push(curr->rchild);

}

while(!s2.empty())

{

printf(“%c “, s2.top()->data);

s2.pop();

}

}

intvisit(BiTree T)

{

if(T)

{

printf(“%c “,T->data);

return1;

}

else

return0;

}

voidLeverTraverse(BiTree T)//方法一、非递归层次遍历二叉树

{

queue  Q;

BiTree p;

p = T;

if(visit(p)==1)

Q.push(p);

while(!Q.empty())

{

p = Q.front();

Q.pop();

if(visit(p->lchild) == 1)

Q.push(p->lchild);

if(visit(p->rchild) == 1)

Q.push(p->rchild);

}

}

voidLevelOrder(BiTree BT)//方法二、非递归层次遍历二叉树

{

BiTNode *queue[10];//定义队列有十个空间

if(BT==NULL)

return;

intfront,rear;

front=rear=0;

queue[rear++]=BT;

while(front!=rear)//如果队尾指针不等于对头指针时

{

cout<data<<”  “;//输出遍历结果

if(queue[front]->lchild!=NULL)//将队首结点的左孩子指针入队列

{

queue[rear]=queue[front]->lchild;

rear++;//队尾指针后移一位

}

if(queue[front]->rchild!=NULL)

{

queue[rear]=queue[front]->rchild;//将队首结点的右孩子指针入队列

rear++;//队尾指针后移一位

}

front++;//对头指针后移一位

}

}

intdepth(BiTNode *T)//树的深度

{

if(!T)

return0;

intd1,d2;

d1=depth(T->lchild);

d2=depth(T->rchild);

return(d1>d2?d1:d2)+1;

//return (depth(T->lchild)>depth(T->rchild)?depth(T->lchild):depth(T->rchild))+1;

}

intCountNode(BiTNode *T)

{

if(T == NULL)

return0;

return1+CountNode(T->lchild)+CountNode(T->rchild);

}

intmain(void)

{

BiTNode *root=NULL;//定义一个根结点

intflag=1,k;

printf(”                     本程序实现二叉树的基本操作。n”);

printf(“可以进行建立二叉树,递归先序、中序、后序遍历,非递归先序、中序遍历及非递归层序遍历等操作。n”);

while(flag)

{

printf(“n”);

printf(“|————————————————————–|n”);

printf(“|                    二叉树的基本操作如下:                     |n”);

printf(“|                        0.创建二叉树                          |n”);

printf(“|                        1.递归先序遍历                        |n”);

printf(“|                        2.递归中序遍历                        |n”);

printf(“|                        3.递归后序遍历                        |n”);

printf(“|                        4.非递归先序遍历                      |n”);

printf(“|                        5.非递归中序遍历                      |n”);

printf(“|                        6.非递归后序遍历                      |n”);

printf(“|                        7.非递归层序遍历                      |n”);

printf(“|                        8.二叉树的深度                        |n”);

printf(“|                        9.二叉树的结点个数                    |n”);

printf(“|                        10.退出程序                            |n”);

printf(“|————————————————————–|n”);

printf(”                        请选择功能:”);

scanf(“%d”,&k);

switch(k)

{

case0:

printf(“请建立二叉树并输入二叉树的根节点:”);

CreateBiTree(&root);

break;

case1:

if(root)

{

printf(“递归先序遍历二叉树的结果为:”);

PreOrder(root);

printf(“n”);

}

else

printf(”          二叉树为空!n”);

break;

case2:

if(root)

{

printf(“递归中序遍历二叉树的结果为:”);

InOrder(root);

printf(“n”);

}

else

printf(”          二叉树为空!n”);

break;

case3:

if(root)

{

printf(“递归后序遍历二叉树的结果为:”);

PostOrder(root);

printf(“n”);

}

else

printf(”          二叉树为空!n”);

break;

case4:

if(root)

{

printf(“非递归先序遍历二叉树:”);

PreOrder_Nonrecursive1(root);

printf(“n”);

}

else

printf(”          二叉树为空!n”);

break;

case5:

if(root)

{

printf(“非递归中序遍历二叉树:”);

InOrderTraverse1(root);

printf(“n”);

}

else

printf(”          二叉树为空!n”);

break;

case6:

if(root)

{

printf(“非递归后序遍历二叉树:”);

PostOrder_Nonrecursive(root);

printf(“n”);

}

else

printf(”          二叉树为空!n”);

break;

case7:

if(root)

{

printf(“非递归层序遍历二叉树:”);

//LeverTraverse(root);

LevelOrder(root);

printf(“n”);

}

else

printf(”          二叉树为空!n”);

break;

case8:

if(root)

printf(“这棵二叉树的深度为:%dn”,depth(root));

else

printf(”          二叉树为空!n”);

break;

case9:

if(root)

printf(“这棵二叉树的结点个数为:%dn”,CountNode(root));

else

printf(”          二叉树为空!n”);

break;

default:

flag=0;

printf(“程序运行结束,按任意键退出!n”);

}

}

system(“pause”);

return0;

}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图