Chuyển đổi cây nhị phân sang cây nhị phân có luồng | Đặt 1 (Sử dụng Hàng đợi) trong C ++

Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để chuyển đổi một cây nhị phân sang một cây nhị phân có luồng bằng cách sử dụng cấu trúc dữ liệu hàng đợi.

Đối với điều này, chúng tôi sẽ được cung cấp một cây nhị phân. Nhiệm vụ của chúng tôi là chuyển đổi cây nhị phân cụ thể đó thành một cây nhị phân theo luồng bằng cách thêm các tuyến đường bổ sung để truyền qua inorder nhanh hơn với sự trợ giúp của cấu trúc dữ liệu hàng đợi.

Ví dụ

#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;
}

Đầu ra

Traversing threaded tree :
4 2 5 1 6 3 7