スレッド化された二分木を実装するためのC++プログラム

スレッド化されたバイナリツリーは、特定の順序でツリーをトラバースする機能を提供するバイナリツリーです。

これにより、順序のないトラバーサルが高速になり、スタックや再帰なしで実行できます。スレッド化された二分木には2つのタイプがあります。

シングルスレッド 各ノードは、左または右のいずれかにスレッド化されます。つまり、先行または後続が順番に並んでいます。ここで、すべての右nullポインターは、順序の後続を指すか、すべての左nullポインターは、順序の先行を指します。

ダブルスレッド 各ノードは、左右どちらかにスレッド化されます。つまり、先行および後続が順番に並んでいます。ここで、すべての右nullポインターは順序の後続を指し、すべての左nullポインターは順序の先行を指します。

これは、スレッド化されたバイナリツリーを実装するためのC++プログラムです。

関数と擬似コード

関数insert（）

Insert node as root if tree is completely empty.
Otherwise, if newnode < current node then
   Go to left thread and set the newnode as left child.
else
   Go to right thread and set the newnode as right child.

関数search（）

If search key < root then
   Go to left thread
else
   Go to right thread

関数delete（）

ノードとその親を検索します。ノードを削除する場合、3つのケースがあります-

• 2つの子を持つノード。
• 子供が残っているだけです。
• 正しい子供しかいません。

例

#include <iostream>
#include <cstdlib>
#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 makeEmpty() { //clear tree
      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;
      }
   }
   bool search(int key) {
      N *temp = root->l;
      for (;;) {
      if (temp->k < key) { //search in left thread
      if (temp->rightTh)
            return false;
         temp = temp->r;
      } else if (temp->k > key) { //search in right thread
         if (temp->leftTh)
            return false;
         temp = temp->l;
      } else {
         return true;
      }
   }
}
void Delete(int key) {
   N *dest = root->l, *p = root;
   for (;;) { //find Node and its parent.
      if (dest->k < key) {
         if (dest->rightTh)
            return;
         p = dest;
         dest = dest->r;
      } else if (dest->k > key) {
         if (dest->leftTh)
            return;
         p = dest;
         dest = dest->l;
      } else {
         break;
      }
   }
   N *target = dest;
   if (!dest->rightTh && !dest->leftTh) {
      p = dest;  //has two children
      target = dest->l;   //largest node at left child
      while (!target->rightTh) {
         p = target;
         target = target->r;
      }
      dest->k= target->k; //replace mode
   }
   if (p->k >= target->k) { //only left child
      if (target->rightTh && target->leftTh) {
         p->l = target->l;
         p->leftTh = true;
      } else if (target->rightTh) {
         N*largest = target->l;
         while (!largest->rightTh) {
            largest = largest->r;
         }
         largest->r = p;
         p->l= target->l;
      } else {
         N *smallest = target->r;
         while (!smallest->leftTh) {
            smallest = smallest->l;
         }
         smallest->l = target->l;
         p->l = target->r;
      }
   } else {//only right child
      if (target->rightTh && target->leftTh) {
         p->r= target->r;
         p->rightTh = true;
      } else if (target->rightTh) {
         N *largest = target->l;
         while (!largest->rightTh) {
            largest = largest->r;
         }
         largest->r= target->r;
         p->r = target->l;
      } else {
         N *smallest = target->r;
         while (!smallest->leftTh) {
            smallest = smallest->l;
         }
         smallest->l= p;
         p->r= target->r;
      }
   }
}
void displayTree() { //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<<"ThreadedBinaryTree\n";
   char ch;
   int c, v;  
   while(1) {
      cout<<"1. Insert "<<endl;
      cout<<"2. Delete"<<endl;
      cout<<"3. Search"<<endl;
      cout<<"4. Clear"<<endl;
      cout<<"5. Display"<<endl;
      cout<<"6. Exit"<<endl;
      cout<<"Enter Your Choice: ";
      cin>>c;
      //perform switch operation
      switch (c) {
         case 1 :
            cout<<"Enter integer element to insert: ";
            cin>>v;
            tbt.insert(v);
            break;
         case 2 :
            cout<<"Enter integer element to delete: ";
            cin>>v;
            tbt.Delete(v);
            break;
         case 3 :
            cout<<"Enter integer element to search: ";
            cin>>v;
            if (tbt.search(v) == true)
               cout<<"Element "<<v<<" found in the tree"<<endl;
            else
               cout<<"Element "<<v<<" not found in the tree"<<endl;
            break;
         case 4 :
            cout<<"\nTree Cleared\n";
            tbt.makeEmpty();
            break;
         case 5:
            cout<<"Display tree: \n ";
            tbt.displayTree();
            break;
         case 6:
            exit(1);
         default:
            cout<<"\nInvalid type! \n";
      }
   }
   cout<<"\n";
   return 0;
}

出力

ThreadedBinaryTree
1. Insert
2. Delete
3. Search
4. Clear
5. Display
6. Exit
Enter Your Choice: 1
Enter integer element to insert: 10
1. Insert
2. Delete
3. Search
4. Clear
5. Display
6. Exit
Enter Your Choice: 1
Enter integer element to insert: 7
1. Insert
2. Delete
3. Search
4. Clear
5. Display
6. Exit
Enter Your Choice: 1
Enter integer element to insert: 6
1. Insert
2. Delete
3. Search
4. Clear
5. Display
6. Exit
Enter Your Choice: 1
Enter integer element to insert: 4
1. Insert
2. Delete
3. Search
4. Clear
5. Display
6. Exit
Enter Your Choice: 1
Enter integer element to insert: 5
1. Insert
2. Delete
3. Search
4. Clear
5. Display
6. Exit
Enter Your Choice: 1
Enter integer element to insert: 3
1. Insert
2. Delete
3. Search
4. Clear
5. Display
6. Exit
Enter Your Choice: 5
Display tree
3 4 5 6 7 10
1. Insert
2. Delete
3. Search
4. Clear
5. Display
6. Exit
Enter Your Choice: 3
Enter integer element to search: 7
Element 7 found in the tree
1. Insert
2. Delete
3. Search
4. Clear
5. Display
6. Exit
Enter Your Choice: 3
Enter integer element to search: 1
Element 1 not found in the tree
1. Insert
2. Delete
3. Search
4. Clear
5. Display
6. Exit
Enter Your Choice: 2
Enter integer element to delete: 3
1. Insert
2. Delete
3. Search
4. Clear
5. Display
6. Exit
Enter Your Choice: 5
Display tree
4 5 6 7 10
1. Insert
2. Delete
3. Search
4. Clear
5. Display
6. Exit
Enter Your Choice: 4

Tree Cleared
1. Insert
2. Delete
3. Search
4. Clear
5. Display
6. Exit
Enter Your Choice: 5
Display tree

1. Insert
2. Delete
3. Search
4. Clear
5. Display
6. Exit
Enter Your Choice: 6