데이터 구조의 이진 탐색 트리

이진 검색 트리는 몇 가지 속성이 있는 이진 트리입니다. 이러한 속성은 다음과 같습니다 -

• 모든 이진 검색 트리는 이진 트리입니다.
• 모든 왼쪽 자식은 루트보다 낮은 값을 갖습니다.
• 모든 올바른 자식은 루트보다 더 큰 가치를 가질 것입니다.
• 이상적인 이진 검색 트리는 동일한 값을 두 번 유지하지 않습니다.

다음과 같은 트리가 하나 있다고 가정해 보겠습니다. -

이 트리는 하나의 이진 검색 트리입니다. 언급된 모든 속성을 따릅니다. 요소를 중위 순회 모드로 순회하면 5, 8, 10, 15, 16, 20, 23을 얻을 수 있습니다. C++ 코드에서 이것을 구현하는 방법을 이해하기 위해 하나의 코드를 보겠습니다.

예시

#include<iostream>
using namespace std;
class node{
   public:
      int h_left, h_right, bf, value;
      node *left, *right;
};
class tree{
   private:
      node *get_node(int key);
   public:
      node *root;
      tree(){
         root = NULL; //set root as NULL at the beginning
      }
      void inorder_traversal(node *r);
      node *insert_node(node *root, int key);
};
node *tree::get_node(int key){
   node *new_node;
   new_node = new node; //create a new node dynamically
   new_node->h_left = 0; new_node->h_right = 0;
   new_node->bf = 0;
   new_node->value = key; //store the value from given key
   new_node->left = NULL; new_node->right = NULL;
   return new_node;
}
void tree::inorder_traversal(node *r){
   if(r != NULL){ //When root is present, visit left - root - right
      inorder_traversal(r->left);
      cout << r->value << " ";
      inorder_traversal(r->right);
   }
}
node *tree::insert_node(node *root, int key){
   if(root == NULL){
      return (get_node(key)); //when tree is empty, create a node as root
   }
   if(key < root->value){ //when key is smaller than root value, go to the left
      root->left = insert_node(root->left, key);
   }else if(key > root->value){ //when key is greater than root value, go to the right
      root->right = insert_node(root->right, key);
   }
   return root; //when key is already present, do not insert it again
}
main(){
   node *root;
   tree my_tree;
   //Insert some keys into the tree.
   my_tree.root = my_tree.insert_node(my_tree.root, 10);
   my_tree.root = my_tree.insert_node(my_tree.root, 5);
   my_tree.root = my_tree.insert_node(my_tree.root, 16);
   my_tree.root = my_tree.insert_node(my_tree.root, 20);
   my_tree.root = my_tree.insert_node(my_tree.root, 15);
   my_tree.root = my_tree.insert_node(my_tree.root, 8);
   my_tree.root = my_tree.insert_node(my_tree.root, 23);
   cout << "In-Order Traversal: ";
   my_tree.inorder_traversal(my_tree.root);
}

출력

In-Order Traversal: 5 8 10 15 16 20 23