数据结构之线索二叉树的前序,中序和后序遍历
BinaryTree线索化二叉树&
二叉树是一种非线性结构，在之前实现的二叉树遍历中不管是递归还是非递归用二叉树作为存储结构时只能取到该结点的左孩子和右孩子，不能得到该结点的前驱和后继。为了保存这种在遍历中需要的信息，同时也为了充分利用结点中的空指针域，我们利用二叉树中指向左右子树的空指针来存放结点的前驱和后继.同时在有n个结点的二叉链表中必定存在n+1个空链域.
那仫问题来了如何充分的利用这些空链域来实现线索化呢？
假设做如下规定：若结点有左子树则其左孩子域指向该结点的左孩子，否则另左孩子指向其前驱;若结点有右子树则其右孩子域指向该结点的右孩子，否则另右孩子域指向其后继.为了实现这种构想我们需要增加两个标志域_leftTag,_rightTag.
一.线索化及中序遍历一棵树
要线索化一颗二叉树，最重要的就是在访问了当前结点并确定当前结点的左孩子域或者右孩子域为空后如何找到当前结点的前一个结点也就是它的前驱，和当前结点的后继.在这里我们用到了一个_prev指针用来保存你访问结点的前一个结点--如果当前结点的左子树域为空则使当前结点的左孩子域指向_prev所指向的结点也就是当前结点的前驱；我们知道中序是按照左-根-右的顺序遍历的，如果当前结点的左访问过了，根也访问过了按照中序遍历的顺序接下来就应该访问右了-_prev指针指向的是当前结点的前一个结点要访问右则只需判断_prev的右孩子域是否为空就可以了，如果为空则使_prev的右孩子域指向它的后继.
void _InOrderThread(Node *root)
if(root == NULL)
_InOrderThread(root-&_left);
if (root-&_left == NULL)
root-&_leftTag=THREAD;
root-&_left=_
&& _prev-&_right == NULL)
_prev-&_rightTag=THREAD;
_prev-&_right=
_InOrderThread(root-&_right);
中序线索化一颗二叉树后如何遍历呢？和之前非递归的方法类似，使得cur指针指向该树的左路结点，如果该结点有右子树则访问右子树，如果没有右子树则继续修改cur的值，使其指向当前结点的后继.
void _InOrder(Node *root)
if(root == NULL)
Node *cur=
while (cur)
//一路向左找到最左的结点.
while (cur-&_leftTag == LINK)
cur=cur-&_
cout&_data&&& &;
while (cur && cur-&_rightTag == THREAD)
cur=cur-&_
cout&_data&&& &;
//没有后继有右子树
cur=cur-&_
二.线索化及前序遍历一棵树&
前序遍历的线索化类似中序遍历的线索化，但是因为前序的顺序是根-左-右，会因为递归太深导致栈溢出的问题，所以在递归线索化左子树和右子树的时候需要判断当前结点的左右标志是否为LINK类型-是才递归线索化左子树和右子树.
void _PrevOrderThread(Node *root)
if(root == NULL)
if (root-&_left == NULL)
root-&_leftTag=THREAD;
root-&_left=_
if (_prev && _prev-&_right == NULL)
_prev-&_rightTag=THREAD;
_prev-&_right=
if(root-&_leftTag == LINK)
//防止栈溢出
_PrevOrderThread(root-&_left);
if(root-&_rightTag == LINK)
_PrevOrderThread(root-&_right);
void _PrevOrder(Node *root)
if(root == NULL)
Node *cur=
while (cur)
while (cur && cur-&_leftTag == LINK)
cout&_data&&& &;
cur=cur-&_
cout&_data&&& &;
//将该树的后继当成子树来访问
cur=cur-&_
//while (cur && cur-&_rightTag == THREAD)
// cur=cur-&_
// cout&_data&&& &;
//cur=cur-&_
三.线索化及后序遍历一棵树&
在后序线索树中找一个结点的前驱很容易直接用_prev就可以找到，那仫如何找一个结点的后继呢？这时就比较棘手了
也就是说，在后序线索化树上找后继时需要知道结点双亲，此时我们可以使用三叉链表做存储结构找到其双亲结点,其实还有一种思路就是逆向思维的方式----我们知道在后序遍历线索二叉树时有的时候是不容易找到一个结点的后继的，如果我们按照根-右-左的顺序逆序遍历一颗线索二叉树就会变的非常简单了.
在实现中我只实现第二种思路即倒着访问一颗后序线索化的二叉树.
程序源代码&
BinaryTreeThd.h
#pragma once
enum PointerTag
struct BinaryTreeThdNode
BinaryTreeThdNode(const T& x=T())
,_left(NULL)
,_right(NULL)
,_leftTag(LINK)
,_rightTag(LINK)
BinaryTreeThdNode *_
BinaryTreeThdNode *_
PointerTag _leftT
//左孩子线索化标志
PointerTag _rightT
//右孩子线索化标志
class BinaryTreeThd
typedef BinaryTreeThdNode N
BinaryTreeThd(const T *a,size_t size,const T& invalid)
:_root(NULL)
,_prev(NULL)
size_t index=0;
_root=_CreatTreeThd(a,size,index,invalid);
void PrevOrderThread()
//前序线索化二叉树
_PrevOrderThread(_root);
void PrevOrder()
//前序遍历二叉树
_PrevOrder(_root);
cout&_left=_CreatTreeThd(a,size,++index,invalid);
root-&_right=_CreatTreeThd(a,size,++index,invalid);
protected:
void _PrevOrderThread(Node *root)
if(root == NULL)
if (root-&_left == NULL)
root-&_leftTag=THREAD;
root-&_left=_
if (_prev && _prev-&_right == NULL)
_prev-&_rightTag=THREAD;
_prev-&_right=
if(root-&_leftTag == LINK)
//防止栈溢出
_PrevOrderThread(root-&_left);
if(root-&_rightTag == LINK)
_PrevOrderThread(root-&_right);
void _InOrderThread(Node *root)
if(root == NULL)
_InOrderThread(root-&_left);
if (root-&_left == NULL)
root-&_leftTag=THREAD;
root-&_left=_
&& _prev-&_right == NULL)
_prev-&_rightTag=THREAD;
_prev-&_right=
_InOrderThread(root-&_right);
void _PostOrderThread(Node *root)
if(root == NULL)
_PostOrderThread(root-&_left);
_PostOrderThread(root-&_right);
if (root-&_left == NULL)
root-&_leftTag=THREAD;
root-&_left=_
if (_prev && _prev-&_right == NULL)
_prev-&_rightTag=THREAD;
_prev-&_right=
void _PrevOrder(Node *root)
if(root == NULL)
Node *cur=
while (cur)
while (cur && cur-&_leftTag == LINK)
cout&_data&&& &;
cur=cur-&_
cout&_data&&& &;
//将该树的后继当成子树来访问
cur=cur-&_
//while (cur && cur-&_rightTag == THREAD)
// cur=cur-&_
// cout&_data&&& &;
//cur=cur-&_
void _InOrder(Node *root)
if(root == NULL)
Node *cur=
while (cur)
//一路向左找到最左的结点.
while (cur && cur-&_leftTag == LINK)
cur=cur-&_
cout&_data&&& &;
while (cur && cur-&_rightTag == THREAD)
cur=cur-&_
cout&_data&&& &;
//没有后继有右子树
cur=cur-&_
//倒着遍历后序线索化二叉树
//根-右-左
void _PostOrder(Node *root)
if(root == NULL)
Node *cur=
while (cur)
while (cur && cur-&_rightTag == LINK)
cout&_data&&& &;
cur=cur-&_
cout&_data&&& &;
while (cur-&_left && cur-&_leftTag == THREAD)
cur=cur-&_
cout&_data&&& &;
//有左子树
cur=cur-&_
protected:
//保存当前结点的前一个结点
void testBinaryTreeThd()
int array[15] = {1,2,'#',3,'#','#',4,5,'#',6,'#',7,'#','#',8};
size_t size=sizeof(array)/sizeof(array[0]);
BinaryTreeThd bt1(array,size,'#');
cout&&&线索化中序遍历&&;
bt1.InOrderThread();
bt1.InOrder();
BinaryTreeThd bt2(array,size,'#');
cout&&&线索化前序遍历&&;
bt2.PrevOrderThread();
bt2.PrevOrder();
BinaryTreeThd bt3(array,size,'#');
cout&&&线索化后序遍历&&;
bt3.PostOrderThread();
bt3.PostOrder();中序线索化二叉树数据结构_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
中序线索化二叉树数据结构
阅读已结束，下载文档到电脑
想免费下载本文？
定制HR最喜欢的简历
下载文档到电脑，方便使用
还剩19页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢安全检查中...
请打开浏览器的javascript，然后刷新浏览器
< 浏览器安全检查中...
还剩 5 秒&> 问题详情
写出对图所示二叉树进行先序、中序、后序遍历的结点序列，并画出该二叉树的先序线索二叉树。
悬赏：0&答案豆
提问人：匿名网友
发布时间：
写出对图所示二叉树进行先序、中序、后序遍历的结点序列，并画出该二叉树的先序线索二叉树。&
您可能感兴趣的试题
1已知一棵二叉树的中序遍历序列为ABCDEFG，后序遍历序列为BDCAFGE，写出该二叉树的先序遍历序列。2将图所示的森林转换成二叉树。&&3给定权值7,14,3,32,5,12，构造相应的哈夫曼树。4编写一算法求中序线索二叉树中某一结点p的前驱结点。
我有更好的答案
相关考试课程
请先输入下方的验证码查看最佳答案
图形验证：
验证码提交中……
找答案会员
享三项特权
找答案会员
享三项特权
找答案会员
享三项特权
选择支付方式：
支付宝付款
郑重提醒：支付后，系统自动为您完成注册
请使用微信扫码支付(元)
支付后，系统自动为您完成注册
遇到问题请联系在线客服QQ：
请您不要关闭此页面,支付完成后点击支付完成按钮
遇到问题请联系在线客服QQ：
恭喜您！升级VIP会员成功
常用邮箱：
用于找回密码
确认密码：}