C++에서 이진 트리에서 이진 검색 트리로 변환

이진 트리 트리의 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 특수한 유형의 트리입니다. 이 자식 노드를 오른쪽 자식과 왼쪽 자식이라고 합니다.

간단한 이진 트리는 -

이진 검색 트리(BST) 다음 규칙을 따르는 특별한 유형의 트리입니다 -

• 왼쪽 자식 노드의 값은 항상 부모보다 작습니다. 참고

• 오른쪽 자식 노드는 부모 노드보다 더 큰 값을 가집니다.

• 모든 노드는 개별적으로 이진 검색 트리를 형성합니다.

이진 검색 트리(BST)의 예 -

검색, 최소값 및 최대값 찾기와 같은 작업의 복잡성을 줄이기 위해 이진 검색 트리가 생성됩니다.

여기에 이진 트리가 주어지고 이 이진 트리를 변환해야 합니다. (BT) 이진 검색 트리로 (BST) . 이 변환에서 바이너리 트리의 원래 구조는 변경되지 않아야 합니다.

BT를 BST로 변환하는 방법을 이해하기 위해 예를 들어보겠습니다. -

입력 -

출력 -

이진 트리를 이진 검색 트리로 변환하는 작업은 세 단계를 거쳐 이루어집니다. 그들은 -

1단계 - 배열 arr[]에 이진 트리를 순회하도록 데이터를 저장합니다. .

2단계 - 정렬 기술을 사용하여 배열 arr[]를 정렬합니다.

3단계 − 이제 트리를 inorder traversal하고 e 배열의 요소를 트리의 노드에 하나씩 복사합니다.

예시

#include<stdio.h>
#include<stdlib.h>
struct node{
   int data;
   struct node *left;
   struct node *right;
};
void Inordertraversal(struct node* node, int inorder[], int *index_ptr){
   if (node == NULL)
      return;
   Inordertraversal(node->left, inorder, index_ptr);
   inorder[*index_ptr] = node->data;
   (*index_ptr)++;
   Inordertraversal(node->right, inorder, index_ptr);
}
int countNodes(struct node* root){
   if (root == NULL)
      return 0;
   return countNodes (root->left) +
   countNodes (root->right) + 1;
}
int compare (const void * a, const void * b){
   return( *(int*)a - *(int*)b );
}
void arrayToBST (int *arr, struct node* root, int *index_ptr){
   if (root == NULL)
      return;
   arrayToBST (arr, root->left, index_ptr);
   root->data = arr[*index_ptr];
   (*index_ptr)++;
   arrayToBST (arr, root->right, index_ptr);
}
struct node* newNode (int data){
   struct node *temp = new struct node;
   temp->data = data;
   temp->left = NULL;
   temp->right = NULL;
   return temp;
}
void printInorder (struct node* node){
   if (node == NULL)
      return;
   printInorder (node->left);
   printf("%d ", node->data);
   printInorder (node->right);
}
int main(){
   struct node *root = NULL;
   root = newNode(17);
   root->left = newNode(14);
   root->right = newNode(2);
   root->left->left = newNode(11);
   root->right->right = newNode(7);
   printf("Inorder Traversal of the binary Tree: \n");
   printInorder (root);
   int n = countNodes(root);
   int *arr = new int[n];
   int i = 0;
   Inordertraversal(root, arr, &i);
   qsort(arr, n, sizeof(arr[0]), compare);
   i = 0;
   arrayToBST (arr, root, &i);
   delete [] arr;
   printf("\nInorder Traversal of the converted BST: \n");
   printInorder (root);
   return 0;
}

출력

Inorder Traversal of the binary Tree:
11 14 17 2 7
Inorder Traversal of the converted BST:
2 7 11 14 17