数据结构实验报告-线索二叉树的遍历

2024年2月7日发(作者：)

线索二叉树的遍历

--《数据结构实验报告》

1. 基本思想

对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域，利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。线索二叉树的建立就是在二叉树的基础上进行线索化。本次实验建立了前序线索二叉树，中序线索二叉树，和后序线索二叉树，并分别对前中序线索二叉树进行了前序，中序，后序遍历，对后序线索二叉树进行了后序遍历。

2. 用到的数据结构

定义节点元素：

Left, right为普通二叉树的左右孩子，value为该节点元素的值，Ltag, Rtag为左右线索化指向节点。

在某些遍历中会用到栈结构，用来存储当前可以路过，但是在以后却访问不到的点。

3. 基本操作实现

1. 前，中，后序二叉树的线索化：线索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索，前驱和后继的信息是在遍历过程中才能得到，故线索化的过程即为在遍历过程中修改空指针的过程。前，中，序线索化的过程相似，只是修改NULL和递归遍历左右孩子的顺序导致产生不同。

2. 前序线索二叉树的前序遍历：因为前序线索二叉树建立的过程就是按照前序遍历的思想线索化的，所以按照一直向左走，直到左边的指向为线索时停止，开始向右指(不管是线索还是树枝)，依次递归得到答案。

3. 前序线索二叉树的中序遍历：根据前序线索化的二叉树在中序遍历时如果按照前序遍历的方式会出现上面的一些点永远无法被访问到，所以，增加一个数据结构—栈。在一直向左遍历的时候，将这些节点入栈，在回访时，依次取出这些点，在进入到取出点的右孩子，实现中序遍历。

4. 前序线索二叉树的后序遍历：思想和中序遍历差不多，但是是将栈中元素的右孩子遍历完成后在输出该元素的值，实现后序遍历。

5. 中序线索二叉树的前序遍历：中序的前序遍历比较简单，和前序线索的前序遍历很像，但是在判断左右孩子是否是线索时，需进行循环遍历判断，不是简单的if。

6. 中序线索二叉树的中序遍历：同前序线索二叉树的前序遍历一样，中序线索化的过程就是根据中序遍历，只需找到最左下的节点，依次向右遍历即可。

7. 中序线索二叉树的后序遍历：与之前一样，存在向上时不会遍历到的元素，需要借助栈来实现后序遍历，过程不太好叙述，直接见代码吧。

8. 后续线索二叉树的后序遍历：后续线索二叉树的后序遍历比较复杂，先找到左下的元素，parent记录当前访问元素的父节点，如果父节点的右孩子是线索或者当前访问节点是父节点的右孩子，则遍历节点变为父节点，其他情况，当父节点的右孩子是树枝时，进入到右孩子，然后一直进入到最左的孩子，进行后序的遍历。

4. 测试数据及测试结果

前序线索二叉树：

中序线索二叉树：

后序线索二叉树：