Giao dịch Inorder của một cây nhị phân có luồng trong C ++

Ở đây chúng ta sẽ thấy cấu trúc dữ liệu cây nhị phân phân luồng. Chúng ta biết rằng các nút cây nhị phân có thể có nhiều nhất là hai nút con. Nhưng nếu họ chỉ có một phần tử con hoặc không có phần tử con nào, thì phần liên kết trong biểu diễn danh sách liên kết sẽ không có giá trị. Sử dụng biểu diễn cây nhị phân theo luồng, chúng ta có thể sử dụng lại các liên kết trống đó bằng cách tạo một số luồng.

Nếu một nút có một số vùng con bên trái hoặc bên phải còn trống, vùng đó sẽ được sử dụng làm luồng. Có hai loại cây nhị phân luồng. Cây luồng đơn hoặc cây nhị phân luồng hoàn toàn.

Đối với cây nhị phân hoàn toàn luồng, mỗi nút có năm trường. Ba trường giống như nút cây nhị phân bình thường, hai trường khác để lưu trữ giá trị Boolean để biểu thị liệu liên kết của phía đó là liên kết thực tế hay chuỗi.

Đây là cây nhị phân hoàn toàn theo luồng

Thuật toán

inorder():
Begin
   temp := root
   repeat infinitely, do
   p := temp
   temp = right of temp
   if right flag of p is false, then
      while left flag of temp is not null, do
         temp := left of temp
      done
   end if
   if temp and root are same, then
      break
   end if
      print key of temp
   done
End

Ví dụ

#include <iostream>
#define MAX_VALUE 65536
using namespace std;
class N { //node declaration
   public:
      int k;
      N *l, *r;
      bool leftTh, rightTh;
};
class ThreadedBinaryTree {
   private:
   N *root;
   public:
   ThreadedBinaryTree() { //constructor to initialize the variables
      root= new N();
      root->r= root->l= root;
      root->leftTh = true;
      root->k = MAX_VALUE;
   }
   void insert(int key) {
      N *p = root;
      for (;;) {
      if (p->k< key) { //move to right thread
         if (p->rightTh)
            break;
         p = p->r;
      }
      else if (p->k > key) { // move to left thread
         if (p->leftTh)
            break;
         p = p->l;
      }
      else {
         return;
      }
   }
   N *temp = new N();
   temp->k = key;
   temp->rightTh= temp->leftTh= true;
   if (p->k < key) {
      temp->r = p->r;
      temp->l= p;
      p->r = temp;
      p->rightTh= false;
   }
   else {
      temp->r = p;
      temp->l = p->l;
      p->l = temp;
      p->leftTh = false;
   }
}
void inorder() { //print the tree
   N *temp = root, *p;
   for (;;) {
      p = temp;
      temp = temp->r;
      if (!p->rightTh) {
         while (!temp->leftTh) {
            temp = temp->l;
         }
      }
      if (temp == root)
         break;
         cout<<temp->k<<" ";
      }
      cout<<endl;
   }
};
int main() {
   ThreadedBinaryTree tbt;
   cout<<"Threaded Binary Tree\n";
   tbt.insert(56);
   tbt.insert(23);
   tbt.insert(89);
   tbt.insert(85);
   tbt.insert(20);
   tbt.insert(30);
   tbt.insert(12);
   tbt.inorder();
   cout<<"\n";
}

Đầu ra

Threaded Binary Tree
12 20 23 30 56 85 89