在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
热门推荐
10 到场文案祝福语大全简短
11 虎年生女孩 祝福语简短
12 生日祝福语短语励志简短
13 适合结婚新人祝福语简短
14 创意花束结婚祝福语简短
15 工作转正红包祝福语简短
16 车队生日条幅祝福语简短
17 高考祝福语歌词文案简短
18 侄子得了冠军祝福语简短