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){