스레드 이진 트리는 특정 순서로 트리를 순회하는 기능을 제공하는 이진 트리입니다.
그것은 중위 순회를 더 빠르게 만들고 스택과 재귀 없이 수행합니다. 스레드 이진 트리에는 두 가지 유형이 있습니다.
단일 스레드 각 노드는 왼쪽 또는 오른쪽으로 스레드되어 순서대로 선행 또는 후속 작업을 의미합니다. 여기에서 모든 오른쪽 널 포인터는 중위 계승자를 가리키거나 모든 왼쪽 널 포인터는 중위 선행자를 가리킵니다.
이중 스레드 각 노드는 왼쪽과 오른쪽으로 스레드되어 순서대로 선행 작업과 후속 작업을 의미합니다. 여기에서 모든 오른쪽 널 포인터는 중위 계승자를 가리키고 모든 왼쪽 널 포인터는 중위 선행자를 가리킵니다.
Threaded Binary Tree를 구현하기 위한 C++ 프로그램입니다.
함수 및 의사코드
함수 삽입()
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.
함수 검색()
If search key < root then Go to left thread else Go to right thread
함수 삭제()
노드와 그 부모를 찾습니다. 노드 삭제에는 세 가지 경우가 있습니다 -
- 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