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