//LL型失衡 右旋
//RR型失衡 左旋
//RL型失衡 先右旋 再左旋
//LR型失衡 先左旋 再右旋
#include "stdio.h"
#include "stdlib.h"typedef int ElemType;
typedef struct node {ElemType data;int height;struct node *left;struct node *right;
} Node;Node *create_node(ElemType value) {Node *node = (Node *) malloc(sizeof(Node));if (node == NULL) {exit(-1);}node->data = value;node->height = 1;node->left = NULL;node->right = NULL;return node;
}//获取树的高度
int getHeight(Node *node) {if (node == NULL) {return 0;}return node->height;
}int max(int a, int b) {return a > b ? a : b;
}int getTreeHeight(Node *node) {if (node == NULL) {return 0;}return max(getTreeHeight(node->left), getTreeHeight(node->right)) + 1;
}//左旋转
Node *leftRotate(Node *root) {Node *newroot = root->right;//当前结点的右子节点作为新的树根root->right = newroot->left;//将新树根的左子树作为原根的右子树newroot->left = root;//将原根作为新根的左子树root->height = 1 + max(getHeight(root->left), getHeight(root->right));newroot->height = 1 + max(getHeight(newroot->left), getHeight(newroot->right));return newroot;
}//右旋转
Node *rightRotate(Node *root) {Node *newroot = root->left;//当前结点的左节点作为新的树根root->left = newroot->right;//将新节点右边的子树作为原根结点的左子树newroot->right = root;//新节点的右子树为原根结点root->height = 1 + max(getHeight(root->left), getHeight(root->right));newroot->height = 1 + max(getHeight(newroot->left), getHeight(newroot->right));return newroot;
}//获取平衡因子
int getBalance(Node *node) {return getHeight(node->left) - getHeight(node->right);
}//插入
Node *insert_node(Node *node, ElemType value) {if (node == NULL) {return create_node(value);}if (node->data > value) {node->left = insert_node(node->left, value);} else if (node->data < value) {node->right = insert_node(node->right, value);} else {return node;}//更新树高node->height = 1 + max(getHeight(node->left), getHeight(node->right));// 获取平衡因子int balance = getBalance(node);//LL型失衡if (balance > 1 && getBalance(node->left) > 0) {return rightRotate(node);}//LR型失衡if (balance > 1 && getBalance(node->left) < 0) {node->left = leftRotate(node->left);return rightRotate(node);}//RR型失衡if (balance < -1 && getBalance(node->right) < 0) {return leftRotate(node);}//RL型失衡if (balance < -1 && getBalance(node->right) > 0) {node->right = rightRotate(node->right);return leftRotate(node);}return node;
}void preOrder(Node *node) {if (node == NULL) {return;}printf("%d ", node->data);preOrder(node->left);preOrder(node->right);
}void inOrder(Node *node) {if (node == NULL) {return;}inOrder(node->left);printf("%d ", node->data);inOrder(node->right);
}Node *find(Node *node, ElemType value, int *counter) {Node *current = node;while (current != NULL) {if (current->data > value) {current = current->left;(*counter)++;} else if (current->data < value) {current = current->right;(*counter)++;} else {(*counter)++;return current;}}return NULL;
}//删除节点恢复平衡
/** 前半部分 二叉搜索树的删除* 后半部分 插入节点导致失衡的修改,稍作调整* */
Node *delete_node(Node *node, int value) {if (node == NULL) {return NULL;}if (node->data > value) {node->left = delete_node(node->left, value);} else if (node->data < value) {node->right = delete_node(node->right, value);} else if (node->data == value) {//情况一 要删除的节点就是叶子结点if (node->left == NULL && node->right == NULL) {Node *temp = node;node = NULL;free(temp);} else if (node->left == NULL && node->right != NULL) {//情况二 只有一个方向有节点 直接用有节点的数据进行替换就可以了Node *temp = node;node = node->right;free(temp);} else if (node->left != NULL && node->right == NULL) {//情况二 只有一个方向有节点Node *temp = node;node = node->left;free(temp);} else if (node->left != NULL && node->right != NULL) {//情况三 要删除的节点有左孩子也有右孩子Node *current = node->right;while (current->left != NULL) {current = current->left;}node->data = current->data;node->right = delete_node(node->right, current->data);}}//删除完成 下面开始调整if (node == NULL) {return node;}//更新树高node->height = 1 + max(getHeight(node->left), getHeight(node->right));// 获取平衡因子int balance = getBalance(node);//LL型失衡if (balance > 1 && getBalance(node->left) >= 0) {return rightRotate(node);}//LR型失衡if (balance > 1 && getBalance(node->left) < 0) {node->left = leftRotate(node->left);return rightRotate(node);}//RR型失衡if (balance < -1 && getBalance(node->right) <= 0) {return leftRotate(node);}//RL型失衡if (balance < -1 && getBalance(node->right) > 0) {node->right = rightRotate(node->right);return leftRotate(node);}return node;
}void test() {Node *root = insert_node(NULL, 1);root = insert_node(root, 2);root = insert_node(root, 3);root = insert_node(root, 4);root = insert_node(root, 5);root = insert_node(root, 6);root = insert_node(root, 7);root = insert_node(root, 8);root = insert_node(root, 9);root = insert_node(root, 10);int counter = 0;Node *result = find(root, 6, &counter);if (result) {printf("找了%d次", counter);}printf("\n前序遍历\n");preOrder(root);printf("\n中序遍历\n");inOrder(root);//    root = delete_node(root, 1);
//    root = delete_node(root, 2);
//    root = delete_node(root, 7);//    printf("\n前序遍历\n");
//    preOrder(root);
//    printf("\n中序遍历\n");
//    inOrder(root);printf("\n树高为%d", getTreeHeight(root));
}int main() {test();return 0;
}

运行效果