C++에서 스레드 이진 트리의 중위 순회

여기에서 스레드된 이진 트리 데이터 구조를 볼 수 있습니다. 우리는 이진 트리 노드가 최대 두 개의 자식을 가질 수 있다는 것을 알고 있습니다. 그러나 자식이 하나만 있거나 자식이 없는 경우 연결 목록 표현의 링크 부분은 null로 유지됩니다. 스레드 이진 트리 표현을 사용하여 스레드를 만들어 빈 링크를 재사용할 수 있습니다.

한 노드에 왼쪽 또는 오른쪽 자식 영역이 비어 있으면 스레드로 사용됩니다. 스레드 이진 트리에는 두 가지 유형이 있습니다. 단일 스레드 트리 또는 전체 스레드 이진 트리입니다.

완전 스레드 이진 트리의 경우 각 노드에는 5개의 필드가 있습니다. 일반 바이너리 트리 노드와 같은 3개의 필드, 해당 면의 링크가 실제 링크인지 스레드인지 여부를 나타내는 부울 값을 저장하는 또 다른 2개의 필드.

이것은 완전히 스레드된 바이너리 트리입니다.

알고리즘

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

예시

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

출력

Threaded Binary Tree
12 20 23 30 56 85 89