6.3.6不平衡二叉搜索树.md

• 问题：给定一颗不平衡二叉搜索树，左子树中的节点数比右边更多，重新组织树结构以改善其平衡性，同时保持二叉搜索树的特性
  • 思路：
    • 对树做一个右旋转。

#include <iostream>
#include <algorithm>
using namespace std;

struct TreeNode{
    int value;
    TreeNode* lChild;
    TreeNode* rChild;
    TreeNode(int val) : value(val), lChild(nullptr), rChild(nullptr) {}
};

TreeNode* RotateRight(TreeNode* oldRoot){
    TreeNode* newRoot = oldRoot->lChild;
    oldRoot->lChild = newRoot->rChild;
    newRoot->rChild = oldRoot;
    return newRoot;
}

void PreorderTraversal(TreeNode* root){
    if(root == nullptr){
        return;
    }
    cout << root->value << " ";
    PreorderTraversal(root->lChild);
    PreorderTraversal(root->rChild);
}

TreeNode* GetTree4(){
    // 创建一个简单的二叉树
    TreeNode* root = new TreeNode(6);
    root->lChild = new TreeNode(4);
    root->rChild = new TreeNode(7);
    
    root->lChild->lChild = new TreeNode(2);
    root->lChild->rChild = new TreeNode(5);
    
    root->lChild->lChild->lChild = new TreeNode(1);
    root->lChild->lChild->rChild = new TreeNode(3);

    return root;
}

int main(){
    TreeNode* root = GetTree4();
    PreorderTraversal(root);
    cout << endl;
    
    TreeNode* newRoot = RotateRight(root);
    PreorderTraversal(newRoot);
    return 0;
}