用于实现线程二叉树的C ++程序
线程二叉树是提供以特定顺序遍历树的工具的二叉树。
它使顺序遍历更快，并且无需堆栈也无需递归。有两种类型的线程二叉树。
单线程每个节点都向左或向右线程，表示顺序的前任或后继。在这里，所有正确的空指针将指向有序的后继者，或者所有剩余的空指针将指向有序的前任。
双线程每个节点都向左和向右线程，这意味着顺序的前任和后继。在这里，所有正确的空指针将指向有序的后继者，所有剩余的空指针将指向有序的前任。
这是一个用于实现线程二叉树的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 thenGo to left thread
else
Go to right thread
功能 delete()
查找节点及其父级。对于删除节点，有三种情况-
有两个孩子的节点。
独生子。
有唯一的孩子。
示例
#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;
//执行开关操作
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;
}
输出结果
ThreadedBinaryTree1. 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
以上是 用于实现线程二叉树的C ++程序 的全部内容， 来源链接： utcz.com/z/321780.html
