实验八 线索二叉树

实验目的和要求

1. 掌握线索二叉树的特点和性质
2. 掌握将二叉树线索化的方法
3. 掌握遍历线索二叉树的方法

实验环境

1. Visual Studio 2017 Community
2. Windows 10 Pro

实验内容

1. 利用给定数据构造二叉树，并将其后序线索化
2. 遍历后序线索化的二叉树

实验过程

任务一

设计

可以将二叉树节点中的空指针改为指向其在后序遍历中的前驱和后继，所以只需在后序递归遍历二叉树时，将访问节点的操作更改为设置左右线索即可。同时，为了区分左右孩子指针和前后线索指针可以设置 tag 标记来区分。

在后序线索树中找结点后继较复杂些，可分3种情况：

1. 若结点 x 是二叉树的根，则其后继为空
2. 若结点又是其双亲的右孩子或是其双亲的左孩子且其双亲没有右子树，则其后继即为双亲结点
3. 若结点 x 是其双亲的左孩子，且其双亲有右子树，则其后继为双亲的右子树上按后序遍历列出的第一个结点

编码实现

编码实现，通过 C++ 来实现以上分析过程。

测试

实验收获

通过本次实验，掌握了构造线索二叉树的方法。