?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("%d\n", 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);