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