在C ++中将常规BST转换为平衡BST
在本教程中，我们将讨论将常规二进制搜索树转换为平衡二进制搜索树的程序。
为此，我们将向左或向右提供倾斜的二进制搜索树。我们的任务是按照一组特定规则将其转换为平衡的二进制搜索树。
示例
#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