平衡二叉树最全代码
#include<stdio.h>
#include<stdlib.h>
typedef struct Node
{
int val;
int height;
struct Node *left;
struct Node *right;
}Node;
//创建新结点
Node* newNode(int val)
{
Node *node = (Node*)malloc(sizeof(Node));
node->val = val;
node->height = 1;
node->left = node->right = NULL;
return node;
}
//获取结点高度
int getHeight(Node *node)
{
return node ? node->height : 0;
}
int max(int a,int b)
{
return a>b?a:b;
}
//左旋操作
Node* leftRotate(Node* root)
{
Node *newRoot = root->right;
Node *T2 = newRoot->left;
newRoot->left = root;
root->right = T2;
root->height = max(getHeight(root->left),getHeight(root->right)) + 1;
newRoot->height = max(getHeight(newRoot->left),getHeight(newRoot->right)) + 1;
return newRoot;
}
//右旋操作
Node* rightRotate(Node* root)
{
Node *newRoot = root->left;
Node *T2 = newRoot->right;
newRoot->right = root;
root->height = max(getHeight(root->left),getHeight(root->right)) + 1;
root->height = max(getHeight(newRoot->left),getHeight(newRoot->right)) + 1;
return newRoot;
}
//获取平衡因子(BF)
int getBalance(Node *node)
{
return getHeight(node->left) - getHeight(node->right);
}
//插入结点
Node* insert(Node* node,int key)
{
if(!node)
return newNode(key);
if(key < node->val)
node->left = insert(node->left,key);
else if(key > node->val)
node->right = insert(node->right,key);
else
return node;
node->height = 1 + max(getHeight(node->left),getHeight(node->right));
int balance = getBalance(node);
// 左左情况
if(balance > 1 && getBalance(node->left) > 0)
return rightRotate(node);
//右右情况
if(balance < -1 && getBalance(node->right) < 0)
return leftRotate(node);
//左右情况
if(balance > 1 && getBalance(node->left) < 0)
{
node->left = leftRotate(node->left);
return rightRotate(node);
}
//右左情况
if(balance < -1 && getBalance(node->right) > 0)
{
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
//删除结点
Node* deleteNode(Node* root,int key)
{
if(!root)
return root;
if(key<root->val)
root->left = deleteNode(root->left,key);
else if(key>root->val)
root->right = deleteNode(root->right,key);
else
{
if(root->left == NULL || root->right == NULL)
{
Node *temp = root->left ? root->left : root->right;
if(temp == NULL)
{
temp = root;
root = NULL;
}
else
{
*root = *temp;
}
free(temp);
}
else
{
Node *temp = root->right;
while(temp && temp->left != NULL)
temp = temp->left;
root->val = temp->val;
root->right = deleteNode(root->right,temp->val);
}
}
if(root == NULL)
return root;
root->height = 1 + max(getHeight(root->left),getHeight(root->right));
int balance =getBalance(root);
if(balance > 1 && getBalance(root->left) >= 0)
return rightRotate(root);
if(balance > 1 && getBalance(root->left) < 0)
{
root->left = leftRotate(root->left);
return rightRotate(root);
}
if(balance < -1 && getBalance(root->right) <= 0)
return leftRotate(root);
if(balance < -1 && getBalance(root->right) > 0)
{
root->right = rightRotate(root->right);
return leftRotate(root);
}
return root;
}
// 修改节点值
Node* modifyNode(Node* root, int oldVal, int newVal) {
// 先删除节点
root = deleteNode(root, oldVal);
// 然后插入新的值
root = insert(root, newVal);
return root; // 返回修改后的树的根
}
void preOrder(Node *root)
{
if(root)
{
printf("%d ",root->val);
preOrder(root->left);
preOrder(root->right);
}
}
void inOrder(Node *root)
{
if(root)
{
inOrder(root->left);
printf("%d ",root->val);
inOrder(root->right);
}
}
Node *find(Node *root,int key)
{
if(root == NULL || root->val)
return root;
if(key < root->val)
return find(root->left,key);
else
return find(root->right,key);
}
void test()
{
// 插入节点
Node *root = NULL;
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
root = insert(root, 50);
root = insert(root, 60);
root = insert(root, 70);
root = insert(root, 80);
printf("-----先序遍历-----\n");
preOrder(root);
printf("\n");
printf("-----中序遍历-----\n");
inOrder(root);
printf("\n");
// 修改节点
printf("修改节点 30 为 35:\n");
root = modifyNode(root, 30, 35);
printf("-----先序遍历-----\n");
preOrder(root);
printf("\n");
printf("删除节点35:\n");
root = deleteNode(root, 35);
preOrder(root);
printf("\n");
}
int main()
{
test();
return 0;
}