이진 트리를 스레드된 이진 트리로 변환 | C++에서 1(대기열 사용) 설정

이 튜토리얼에서는 큐 데이터 구조를 사용하여 이진 트리를 스레드된 이진 트리로 변환하는 프로그램에 대해 설명합니다.

이를 위해 바이너리 트리가 제공됩니다. 우리의 임무는 대기열 데이터 구조의 도움으로 더 빠른 순회 순회를 위해 추가 경로를 추가하여 특정 이진 트리를 스레드된 이진 트리로 변환하는 것입니다.

예시

#include <iostream>
#include <queue>
using namespace std;
//node structure for threaded tree
struct Node {
   int key;
   Node *left, *right;
   bool isThreaded;
};
//putting the inorder pattern into a queue
void convert_queue(Node* root, std::queue<Node*>* q){
   if (root == NULL)
      return;
   if (root->left)
      convert_queue(root->left, q);
   q->push(root);
   if (root->right)
      convert_queue(root->right, q);
}
//traversing the queue and making threaded tree
void create_threadedtree(Node* root, std::queue<Node*>* q){
   if (root == NULL)
      return;
   if (root->left)
      create_threadedtree(root->left, q);
   q->pop();
   if (root->right)
      create_threadedtree(root->right, q);
   //if right pointer in NUll, point it to
   //inorder successor
   else {
      root->right = q->front();
      root->isThreaded = true;
   }
}
//finally taking the tree and converting it into threaded
void createThreaded(Node* root){
   std::queue<Node*> q;
   convert_queue(root, &q);
   create_threadedtree(root, &q);
}
Node* leftMost(Node* root){
   while (root != NULL && root->left != NULL)
      root = root->left;
      return root;
   }
   //performing inorder traversal of threaded tree
   void inOrder(Node* root){
      if (root == NULL)
         return;
      Node* cur = leftMost(root);
      while (cur != NULL) {
         cout << cur->key << " ";
         //if threaded node, move to inorder successor
         if (cur->isThreaded)
            cur = cur->right;
         else
            cur = leftMost(cur->right);
      }
   }
   Node* newNode(int key){
      Node* temp = new Node;
      temp->left = temp->right = NULL;
      temp->key = key;
      return temp;
}
int main(){
   Node* root = newNode(1);
   root->left = newNode(2);
   root->right = newNode(3);
   root->left->left = newNode(4);
   root->left->right = newNode(5);
   root->right->left = newNode(6);
   root->right->right = newNode(7);
   createThreaded(root);
   cout << "Traversing threaded tree :\n";
   inOrder(root);
   return 0;
}

출력

Traversing threaded tree :
4 2 5 1 6 3 7