数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会科学
时装研究
法律研究C++ 中的线索二叉树的中序遍历
这里我们将了解线索二叉树数据结构。我们知道二叉树节点最多有两个子节点。但如果它们只有一个子节点或没有子节点，那么在链表表示中，链接部分将保持为 null。使用线索二叉树表示时，我们可以通过创建一些线程来重用这些空链接。
如果某个节点有一些空闲的左或右子节点区域，那将用作线程。线索二叉树有两种类型：单线索树或全线索二叉树。
对于全线索二叉树，每个节点都有五个字段。三个字段与正常二叉树节点类似，另外两个字段用于存储布尔值，以表示该侧的链接是实际链接还是线程。
| 左线程标志 | 左链接 | 数据 | 右链接 | 右线程标志 |
这是全线索二叉树
算法
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
更新于：10-8-2020
4K+ 浏览量
广告