将标准二叉搜索树转换成平衡二叉搜索树，用C++实现

在本教程中，我们将讨论一个将普通二叉搜索树转换为平衡二叉搜索树的程序。

为此，我们将提供一棵向左或向右倾斜的二叉搜索树。我们的任务是按照一定的规则将其转换为一颗平衡二叉搜索树。

示例

 现场演示

#include <bits/stdc++.h>
using namespace std;
//node structure of tree
struct Node{
   int data;
   Node* left, *right;
};
//traversing tree and storing node pointers
//in vector nodes
void store_nodes(Node* root, vector<Node*> &nodes){
   if (root==NULL)
      return;
   store_nodes(root->left, nodes);
   nodes.push_back(root);
   store_nodes(root->right, nodes);
}
//constructing binary tree
Node* construct_tree(vector<Node*> &nodes, int start,
int end){
   if (start > end)
      return NULL;
   //make the middle element to be the root
   int mid = (start + end)/2;
   Node *root = nodes[mid];
   root->left = construct_tree(nodes, start, mid-1);
   root->right = construct_tree(nodes, mid+1, end);
   return root;
}
//converting an unbalanced BST to a balanced BST
Node* buildTree(Node* root){
   //storing nodes of given BST in sorted order
   vector<Node *> nodes;
   store_nodes(root, nodes);
   int n = nodes.size();
   return construct_tree(nodes, 0, n-1);
}
//creation of new node
Node* newNode(int data){
   Node* node = new Node;
   node->data = data;
   node->left = node->right = NULL;
   return (node);
}
//performing preorder traversal
void preOrder(Node* node){
   if (node == NULL)
      return;
   printf("%d ", node->data);
   preOrder(node->left);
   preOrder(node->right);
}
int main(){
   Node* root = newNode(10);
   root->left = newNode(8);
   root->left->left = newNode(7);
   root->left->left->left = newNode(6);
   root->left->left->left->left = newNode(5);
   root = buildTree(root);
   printf("Preorder traversal of balanced BST : \n");
   preOrder(root);
   return 0;
}

输出

Preorder traversal of balanced BST :
7 5 6 8 10

更新于：2020 年 1 月 6 日

161 次浏览

开启你的职业生涯

完成课程获取认证

开始学习
广告