C++의 이진 트리 수준 순서 탐색

바이너리 트리가 있다고 가정합니다. 레벨 순서 순회 방식을 사용하여 이 트리를 순회해야 합니다. 트리가 다음과 같다면

순회 시퀀스는 다음과 같습니다. - [10, 5, 16, 8, 15, 20, 23]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 노드를 저장할 대기열 대기열 정의
• 루트를 쿼리에 삽입합니다.
• que가 비어 있지 않은 동안 do
  • item :=대기열의 맨 앞에 있는 항목
  • 항목 값 인쇄
  • 항목의 왼쪽이 null이 아니면 왼쪽 항목을 que에 삽입
  • 항목의 오른쪽이 null이 아니면 항목의 오른쪽을 que에 삽입
  • que에서 앞 요소 삭제

예(C++)

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#include<iostream>
#include<queue>
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 levelorder_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::levelorder_traversal(node *root){
   queue <node*> que;
   node *item;
   que.push(root); //insert the root at first
   while(!que.empty()){
      item = que.front(); //get the element from the front end
      cout << item->value << " ";
      if(item->left != NULL) //When left child is present, insert into queue
         que.push(item->left);
      if(item->right != NULL) //When right child is present, insert into queue
         que.push(item->right);
      que.pop(); //remove the item from queue
   }
}
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 << "Level-Order Traversal: ";
   my_tree.levelorder_traversal(my_tree.root);
}

입력

[10,5,16,null,8,15,20,null,null,null,null,null,null,null,23]

출력

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