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 }

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

?

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