C++ 程序实现线程二叉树
c++server side programmingprogramming更新于 2024/10/24 23:52:00
线程二叉树是一种二叉树，它提供了按特定顺序遍历树的功能。
它使中序遍历更快，并且无需堆栈和递归即可完成。有两种类型的线程二叉树。
单线程 每个节点都向左或向右线程化，这意味着按顺序的前任或后继。在这里，所有右空指针将指向中序的后继，或者所有左空指针将指向中序的前任。
双线程 每个节点都向左和向右线程化，这意味着按顺序的前任和后继。这里，所有右空指针将指向中序后继，所有左空指针将指向中序前驱。
这是一个实现线程二叉树的 C++ 程序。
函数和伪代码
function insert()
如果树完全为空，则将节点插入为根节点。 否则，如果新节点 < 当前节点则 转到左线程并将新节点设置为左子节点。 否则 转到右线程并将新节点设置为右子节点。
function search()
如果搜索键 < 根则 转到左线程 否则 转到正确的线程
function delete()
查找节点及其父节点。删除节点有三种情况 −
- 有两个子节点的节点。
- 只有左子节点。
- 只有右子节点。
示例
#include <iostream>
#include <cstdlib>
#define MAX_VALUE 65536
using namespace std;
class N { //节点声明
public:
int k;
N *l, *r;
bool leftTh, rightTh;
};
class ThreadedBinaryTree {
private:
N *root;
public:
ThreadedBinaryTree() { //构造函数初始化变量
root= new N();
root->r= root->l= root;
root->leftTh = true;
root->k = MAX_VALUE;
}
void makeEmpty() { //清除树
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) { //移动到右线程
if (p->rightTh)
break;
p = p->r;
} else if (p->k > key) { //移动到左线程
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) { //在左线程中搜索
if (temp->rightTh)
return false;
temp = temp->r;
} else if (temp->k > key) { //在右线程中搜索
if (temp->leftTh)
return false;
temp = temp->l;
} else {
return true;
}
}
}
void Delete(int key) {
N *dest = root->l, *p = root;
for (;;) { //查找 Node 及其父节点。
if (dest->k < key) {
如果 (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; //有两个子节点
target = dest->l; //左子节点最大节点
while (!target->rightTh) {
p = target;
target = target->r;
}
dest->k= target->k; //替换模式
}
if (p->k >= target->k) { //仅左子节点
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
