一、实验目的和要求
目的：熟悉后序线索二叉树并实现后序遍历
要求：
（1）创建二叉树。
（2）转换为后序线索二叉树。
（3）实现后序遍历的非递归算法。
二、实验环境
编译器：Vscode +DevC++
系统：Windows10
CPU：i5-8265U@1.60GHz
三、实验内容
（1）创建二叉树。
（2）转换为后序线索二叉树。
（3）实现后序遍历的非递归算法。
四、实验过程
4.1 任务定义和问题分析
1.创建二叉树
沿用之前使用二叉树创建模板；（若兼容后序线索二叉树的话）
或者重新创建二叉树类（后序线索二叉树需要其他辅助变量）
2.转换成后序线索二叉树
在转换时只需要按照后序遍历，（需要记录当前结点的前驱）逐个将空指针利用起来
3.实现后序遍历的非递归算法
需要经过多重循环，首先通过while找到最左结点，然后遍历后继……
4.2 数据结构的选择和概要设计
必是选择链式结构；
在创建树时，使用扩展先序序列创建；
详细设计
第一尝试：
首先将之前写的二叉树类扩展了，添加了rtag和ltag变量用于识别指针是否指向儿子；其次添加了一个全局结点指针变量，用于实现对前驱的记录
接着对后序遍历进行修改
然后就是添加函数 使其能够进行对后序非递归遍历
在编写此方面代码时就出现了问题
我的第一版函数是如下操作的
1.先找到第一个结点（最左的结点）
2.再遍历其后继
3.然后再找到当前结点的最左儿子
4.重复2，3操作直到结点为空
在实际面对下面二叉树时，就出现了预想不到的事情：
进入了死循环————CDBCDB
下面展示后序线索（绿色指向前驱，红色指向后继）：
不难看出再程序寻到B时对A的左子树操作就完成了，需要去操作A的右子树，然而对于非递归遍历来说，我们现在就是过了河的卒，无法回头，在执行到B时没有操作能够支持我们去操作A的右子树
故而 添加辅助空间：父亲指针；
并在创建树时，记录每个结点的父亲结点
在执行非递归后序遍历时，操作如下
找寻到以当前结点为根的树的后序遍历的起始节点
按次序找寻后继并输出数据
判断是否达到根结点（是：输出数据并结束遍历；否：进行下一步）
逐层向上返回，并输出数据，直到是从当前左子树返回为止
去访问右孩子
回到第一步
五、测试及结果分析
5.1 实验数据
5.2 结果及分析
正确实现了二叉树向后序线索树的转换
并实现了后序遍历的非递归输出
六、实验收获
熟悉了线索二叉树
七、参考文献
数据结构-线索二叉树（后序线索二叉树及遍历）
《大话数据结构》
八、附录（源代码）
/*
* @Descripttion:
* @version:
* @Author: Nice_try
* @Date: 2020-05-26 09:10:57
* @LastEditors: Nice_try
* @LastEditTime: 2020-05-26 17:59:12
*/
#include <iostream>
#include<cstdio>
#include<algorithm>
#include<typeinfo>
using namespace std;
#define Link 0 //表示该节点有非空孩子节点
#define Thread 1 //表示该节点有后续节点（对于右子树来说）
#define MAXSIZE 100
template <class T>
struct BT_Thread_Node
{
T Data;
BT_Thread_Node *Left_Child;
BT_Thread_Node *Right_Child;
BT_Thread_Node *Parent; //指向该节点的父母节点
int Ltag;
int Rtag;
};
template <class T>
class Thread_Binary_tree
{
private:
BT_Thread_Node<T> *Tree;
BT_Thread_Node<T> *Pre_Node;
BT_Thread_Node<T> *BT_Node_Stack[MAXSIZE];
int Top;
int Create_Thread_BTree(BT_Thread_Node<T> *&Tree, BT_Thread_Node<T> *Parent);
void PostOrder_Thread_Op(BT_Thread_Node<T> *&Tree);
void _PostOrder_Op(BT_Thread_Node<T> *&Tree);
public:
Thread_Binary_tree();
~Thread_Binary_tree();
void PostOrder_Thread();
void _PostOrder();
};
template <class T>
int Thread_Binary_tree<T>::Create_Thread_BTree(BT_Thread_Node<T> *&Tree, BT_Thread_Node<T> *Parent_Node)
{
T Data;
cin >> Data;
if(Data=='#'||Data==-1)
Tree = NULL;
else
{
Tree = new BT_Thread_Node<T>;
Tree->Parent = Parent_Node; //指向父母节点
Tree->Data = Data;
Tree->Ltag = Link;
Tree->Rtag = Link;
Create_Thread_BTree(Tree->Left_Child, Tree); //Tree是孩子的父母节点
Create_Thread_BTree(Tree->Right_Child, Tree);
}
return 1;
}
template <class T>
void Thread_Binary_tree<T>::PostOrder_Thread_Op(BT_Thread_Node<T> *&Tree)
{
if (Tree == NULL)
return;
PostOrder_Thread_Op(Tree->Left_Child); //左
PostOrder_Thread_Op(Tree->Right_Child); //右
if (Tree->Left_Child == NULL) //根
{
Tree->Left_Child = Pre_Node;
Tree->Ltag = Thread;
}
if (Pre_Node != NULL && Pre_Node->Right_Child == NULL)
{
Pre_Node->Right_Child = Tree;
Pre_Node->Rtag = Thread;
}
Pre_Node = Tree;
}
template <class T>
void Thread_Binary_tree<T>::_PostOrder_Op(BT_Thread_Node<T> *&Tree)
{
if (Tree == NULL)
return;
BT_Thread_Node<T> *Cur_Node = Tree;
Pre_Node = NULL;
while (Cur_Node != NULL)
{
while (Cur_Node->Left_Child != Pre_Node) //change,找到起始节点（在左树的最左边）
{
Cur_Node = Cur_Node->Left_Child;
}
while (Cur_Node != NULL && Cur_Node->Rtag == Thread) //按线索找到次树节点
{
BT_Node_Stack[++Top] = Cur_Node;
cout << Cur_Node->Data << " ";
Pre_Node = Cur_Node; //每次访问节点后，PreNode更新
Cur_Node = Cur_Node->Right_Child;
}
if (Cur_Node == Tree) //如果当前节点为根节点，说明遍历完成
{
BT_Node_Stack[++Top] = Cur_Node;
cout << Cur_Node->Data << " ";
return;
}
while (Cur_Node != NULL && Cur_Node->Right_Child == Pre_Node) //当前节点的右孩子节点刚好上次遍历，说明该袖珍树只差根就遍历完成
{
BT_Node_Stack[++Top] = Cur_Node;
cout << Cur_Node->Data << " ";
Pre_Node = Cur_Node;
Cur_Node = Cur_Node->Parent; //访问袖珍树后回到上一层
}
if (Cur_Node != NULL && Cur_Node->Rtag == Link) //回到上一层后，先访问右孩子
{
Cur_Node = Cur_Node->Right_Child;
}
}
}
template <class T>
Thread_Binary_tree<T>::Thread_Binary_tree() : Pre_Node(NULL), Top(-1)
{
Create_Thread_BTree(Tree, NULL);
}
template <class T>
Thread_Binary_tree<T>::~Thread_Binary_tree()
{
while (Top != -1)
{
delete BT_Node_Stack[Top];
Top--;
}
}
template <class T>
void Thread_Binary_tree<T>::PostOrder_Thread()
{
PostOrder_Thread_Op(Tree);
}
template <class T>
void Thread_Binary_tree<T>::_PostOrder()
{
_PostOrder_Op(Tree);
}
