首页澳门新葡亰官方网站 › 二叉树遍历【很好的稿子】

二叉树遍历【很好的稿子】

/************************************************************************/
/*
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_xpj娱乐平台,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语言和数据结构,先是写了排序二叉树,觉得平衡二叉树作为一个经典...

1 #include <iostream>
  2
  3 #define MAXN  100
  4 using namespace stbd;
  5
  6
  7 struct BTNode
  8 {
  9     char tag;
10     BTNode *left;
11     BTNode *right;
12 };
13
14 class BTree
15 {
16 private:
17     BTNode **root;
18     void BuildBTree(BTNode **root);
19
20 public:
21     /*递归版本*/
22     void PreVisit(BTNode *root);
23     void InVisit(BTNode *root);
24     void PostVisit(BTNode *root);
25
26     /*非递归版本*/
27     void NR_PreVisit(BTNode *root);
28     void NR_InVisit(BTNode *root);
29     void NR_PostVisit(BTNode *root);
30
31     BTree(BTNode **r);
32     BTree();
33 };
34
35 BTree::BTree()
36 {
37
38 }
39
40 BTree::BTree(BTNode **r)
41 {
42     root = r;
43     /*
44 *root = new BTNode; 45     (*root)->left = NULL;
46 (*root)->right = NULL; 47     */
48     BuildBTree(root);
49 }
50
51 /*先序方式插入结点*/
52 void BTree::BuildBTree(BTNode **root)
53 {
54     char c;
55    
56     c = getchar();
57     if(c == '#')
58         *root=NULL;
59     else{
60         *root = new BTNode;
61         (*root)->tag = c;
62         BuildBTree(&(*root)->left);
63         BuildBTree(&(*root)->right);
64     }
65 }
66
67 void BTree::PreVisit(BTNode *root)
68 {
69     if(root!=NULL)
70     {
71         printf("%c ", root->tag );
72         PreVisit(root->left);
73         PreVisit(root->right);
74     }
75 }
76
77 void BTree::InVisit(BTNode *root)
78 {
79     if(root!=NULL)
80     {
81         InVisit(root->left);
82         printf("%c ", root->tag );
83         InVisit(root->right);
84     }
85 }
86
87 void BTree::PostVisit(BTNode *root)
88 {
89     if(root!=NULL)
90     {
91         PostVisit(root->left);
92         PostVisit(root->right);
93         printf("%c ", root->tag );
94     }
95 }
96
97 void BTree::NR_PreVisit(BTNode *root)
98 {
99     BTNode *s[MAXN];
100     int top=0;
101
102     while(top!=0 || root!=NULL)
103     {
104         while(root!=NULL)
105         {
106             s[top] = root;
107             printf("%c ", s[top++]->tag);
108             root = root->left;
109         }
110         if(top>0)
111         {
112             root = s[--top];
113             root = root->right;
114         }
115     }
116 }
117
118 void BTree::NR_InVisit(BTNode *root)
119 {
120     BTNode *s[MAXN];
121     int top=0;
122    
123     while(top!=0 || root!=NULL)
124     {
125         while(root!=NULL)
126         {
127             s[top++]=root;
128             root = root->left;
129         }
130         if(top>0)
131         {
132             root = s[--top];
133             printf("%c ", root->tag);
134             root = root->right;
135         }
136     }
137 }
138
139 void BTree::NR_PostVisit(BTNode *root)
140 {
141     BTNode *s[MAXN], *tmp=NULL;
142     int top=0;
143
144     while(top!=0 || root!=NULL)
145     {
146         while(root!=NULL)
147         {
148             s[top++]=root;
149             root=root->left;
150         }
151         if(top>0)
152         {
153             root = s[--top];
154
155             /*右孩子不存在或者已经访问过,root出栈并访问*/
156             if( (root->right == NULL) || (root->right == tmp)

157             {
158                 printf("%c ", root->tag);
159                 tmp = root;        //保存root指针
160                 root=NULL;         //当前指针置空,防止再次入栈
161             }
162
163             /*不出栈,继续访问右孩子*/
164             else
165             {
166                 top++;             //与root=s[--top]保持平衡
167                 root = root->right;
168             }
169         }
170     }
171 }
172
173 int main()
174 {
175     BTNode *root=NULL;
176     BTree bt(&root);  //头指针的地址
177    
178     bt.NR_PreVisit(root);
179     printf("n");
180     bt.NR_InVisit(root);
181     printf("n");
182     bt.NR_PostVisit(root);
183     printf("n");
184     return 0;
185 }

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

#include

先上代码,tb带NR(Non-recursive)的表示非递归遍历。

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;

124#8##5##369###7##

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);//递归调用,前序遍历右子树

}

用windows自带的画图画的,的确是粗糙了点。。。

//后序遍历的算法程序

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;

}

}

}

1 2 4 8 5 3 6 9 7
4 8 2 5 1 9 6 3 7
8 4 5 2 9 6 7 3 1

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;

}

}

}

 

转载本站文章请注明出处:澳门新葡亰官方网站 http://www.radioritmo-bl.com/?p=1249

上一篇:

下一篇:

相关文章