二叉树是一种非线性结构，遍历二叉树需要通过递归或者用栈辅助实现非递归的遍历。
用二叉树作为压缩存储结构时，取到一个结点，只能获取节点的左孩子和右孩子，不能直接得到结点的任一遍历序列的前驱或者后继。为了实现这种遍历，偶们利用二叉树中指向左右子树的空指针来存放结点的前驱和后继。
线索化二叉树思路：
当某一结点的左结点或结右点存在NULL时，则该结点的为空的子结点需要线索化。
在进行线索化时，结点的前驱指向前一个访问过的结点，故定义一个指针prev来保存前一个结点；结点的后继偶们并不知道，则对于未来的事情并不知道，偶们可以在未来对该结点的后继进行线索化，使prev的后继指向cur。
前序遍历二叉树------根->左->右（1,2,3,4,5,6）
计算
安全
数据库
网络和加速
企业服务
template<class T>
void BinaryTreeThd<T>::PrevOrderThreading()//前序线索化二叉树
{
Node* prev = NULL;
_PrevOrderThreading(_root, prev);
}
template<class T>
void BinaryTreeThd<T>::_PrevOrderThreading(Node* cur, Node*& prev)//前序线索化二叉树
{
if (cur == NULL)
{
return;
}
if (cur->_left == NULL)
{
cur->_leftTag = THREAD;
cur->_left = prev;
}
if (prev && prev->_right == NULL)//到未来的结点进行先前结点后继的线索化
{
prev->_rightTag = THREAD;
prev->_right = cur;
}
prev = cur;
if (cur->_leftTag == LINK)//线索化左结点
{
_PrevOrderThreading(cur->_left, prev);
}
if (cur->_rightTag == LINK)//线索化右结点
{
_PrevOrderThreading(cur->_right, prev);
}
}中序遍历二叉树------左->根->右（3,2,4,1,6,5）
递归实现：
template<class T>
void BinaryTreeThd<T>::InOrderThreading()//中序线索化二叉树
{
//递归实现中序线索化
Node* prev = NULL;//线索化的前一个结点
_InOrederThreading(_root, prev);
}
template<class T>
void BinaryTreeThd<T>::_InOrederThreading(Node* cur,Node*& prev)//中序线索化二叉树
{
if (cur == NULL)
{
return;
}
_InOrederThreading(cur->_left, prev);//递归出cur->_left为空
if (cur->_left == NULL)
{
cur->_leftTag = THREAD;
cur->_left = prev;//当前结点的前驱指向前一个结点
}
//对先前的结点后继进行线索化，在cur指向下一个结点即后继时，将先前节点的后继指向cur
//到未来的结点进行先前结点后继的线索化
if (prev && prev->_right == NULL)
{
cur->_rightTag = THREAD;
prev->_right = cur;
}
prev = cur;
_InOrederThreading(cur->_right, prev);//递归出cur->_right为空
}非递归实现（利用栈）：
template<class T>
void BinaryTreeThd<T>::InOrderThreading_NonR()//中序线索化二叉树--非递归
{
//栈实现中序线索化
stack<Node*> s;
Node* prev = NULL;
Node* cur = _root;
if (cur == NULL)
{
return;
}
while (cur || !s.empty())
{
while(cur)//找到最左结点,入栈
{
s.push(cur);
cur = cur->_left;
}//cur不为空进栈，cur为空说明cur已经线索化了
cur = s.top();//循环进入使cur为栈顶元素并判断是否需要线索化
if (cur->_left == NULL)
{
cur->_leftTag = THREAD;
cur->_left = prev;
}
s.pop();//弹出栈顶元素，使栈顶保存需要线索化的cur的后继
prev = cur;
if (cur->_right == NULL && !s.empty())
{
cur->_rightTag = THREAD;
cur->_right = s.top();
cur = NULL;//设置cur为空，防止死循环（2）
}
else
{
cur = cur->_right;//线索化跳到右子树进行
}
}
}后序遍历二叉树------左->右->根（3,4,2,6,5,1）
template<class T>
void BinaryTreeThd<T>::PastOrderThreading()//后序线索化二叉树
{
Node* prev = NULL;
_PastOrderThreading(_root, prev);
}
template<class T>
void BinaryTreeThd<T>::_PastOrderThreading(Node* cur, Node*& prev)//后序线索化二叉树
{
if (cur == NULL)
{
return;
}
_PastOrderThreading(cur->_left, prev);//最左结点
_PastOrderThreading(cur->_right, prev);//最右结点
if (cur->_left == NULL)//线索化前驱
{
cur->_leftTag = THREAD;
cur->_left = prev;
}
if (prev && prev->_right == NULL)//线索化后继
{
prev->_rightTag = THREAD;
prev->_right = cur;
}
prev = cur;
}亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
