二叉树是一种非线性结构，遍历二叉树需要通过递归或者用栈辅助实现非递归的遍历。
创新互联公司坚持“要么做到，要么别承诺”的工作理念，服务领域包括：成都网站制作、网站设计、企业官网、英文网站、手机端网站、网站推广等服务，满足客户于互联网时代的
盱眙网站设计、移动媒体设计的需求，帮助企业找到有效的互联网解决方案。努力成为您成熟可靠的网络建设合作伙伴！
用二叉树作为压缩存储结构时，取到一个结点，只能获取节点的左孩子和右孩子，不能直接得到结点的任一遍历序列的前驱或者后继。为了实现这种遍历，偶们利用二叉树中指向左右子树的空指针来存放结点的前驱和后继。
线索化二叉树思路：
当某一结点的左结点或结右点存在NULL时，则该结点的为空的子结点需要线索化。
在进行线索化时，结点的前驱指向前一个访问过的结点，故定义一个指针prev来保存前一个结点；结点的后继偶们并不知道，则对于未来的事情并不知道，偶们可以在未来对该结点的后继进行线索化，使prev的后继指向cur。
前序遍历二叉树------根->左->右（1,2,3,4,5,6）
template
void BinaryTreeThd::PrevOrderThreading()//前序线索化二叉树
{
Node* prev = NULL;
_PrevOrderThreading(_root, prev);
}
template
void BinaryTreeThd::_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
void BinaryTreeThd::InOrderThreading()//中序线索化二叉树
{
//递归实现中序线索化
Node* prev = NULL;//线索化的前一个结点
_InOrederThreading(_root, prev);
}
template
void BinaryTreeThd::_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
void BinaryTreeThd::InOrderThreading_NonR()//中序线索化二叉树--非递归
{
//栈实现中序线索化
stack 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
void BinaryTreeThd::PastOrderThreading()//后序线索化二叉树
{
Node* prev = NULL;
_PastOrderThreading(_root, prev);
}
template
void BinaryTreeThd::_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;
}
创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。
分享名称：二叉树的前序、中序和后序线索化-创新互联
文章位置：
http://bzwzjz.com/article/cspiee.html
