855学习记录数据结构树(3)线索二叉树与森林——炎泽汐$de$ Blog

文章目录[隐藏]

• 线索二叉树
• 森林

定义

---

      二叉树虽然是非线性结构,但二叉树的遍历却为二叉树的结点集导出了一个线性序列因而，二叉树的结点存在关于这个线性序列的前驱和后继。对应于前序、中序、后序遍历,除了相应序列的第一个和最后一个，二又树的每个结点都存在前序前驱/后继、中序前驱/后继、后序前驱/后继。

      利用上述几种遍历方式对二叉树进行遍历后,可将树中所有结点都按照某种次序排列在一个线性有序(前序、中序和后序)的序列中。这样,从某个结点出发可以很容易地找到它在某种次序下的前驱和后继。

      指示前驱与后继的指针叫做“线索”,加上了线索的二叉树叫做线索二叉树。对应二叉链表叫做线索二叉链表。在线索二叉树中,由于有了线索,无需遍历二叉树就可得到任一结点的前驱与后继结点的地址。

struct ThreadTreeNode {
	int val, ltag, rtag;
	ThreadTreeNode *left;
	ThreadTreeNode *right;
	ThreadTreeNode() : val(0), left(nullptr), right(nullptr), ltag(0), rtag(0) {}
	ThreadTreeNode(int x) : val(x), left(nullptr), right(nullptr), ltag(0), rtag(0) {}
 	ThreadTreeNode(int x, ThreadTreeNode *left, ThreadTreeNode *right) : val(x), left(left), right(right), ltag(0), rtag(0) {}
};

中序线索二叉树的建立

---

      利用中序遍历线索化二叉树：

ThreadTreeNode* pre = new ThreadTreeNode();
void CreatThread(ThreadTreeNode* root, ThreadTreeNode* pre){
	if(root == nullptr){
		return;
	}
	CreatThread(root -> left, pre);
	if(!root -> left){
		root -> left = pre;
		root -> ltag = 1;
	}
	if(pre && !root -> right){
		pre -> right = root;
		pre -> rtag = 1;
	}
	pre = root;
	CreatThread(root -> right, pre);
}
pre -> right = nullptr;
pre -> rtag = 1;

存储表示

---

遍历

---