data structure（10）
#ifndef _COMMON_H_
#define _COMMON_H_
#define TRUE
#define FALSE
#define OK
#define ERROR
#define INFEASIBLE
#define OVERFLOW
typedef int S
//Status Equal(int a, int b);
BiThrTree.h
#ifndef _BITHRTREE_H_
#define _BITHRTREE_H_
typedef char TElemT
//二叉树的二叉线索存储表示
//typedef enum PointerTag{Link, Thread}; //Link==0:指针， Thread==1:线索
typedef enum{Link, Thread} PointerT
//Link==0:指针， Thread==1:线索
typedef struct BiThrNode
struct BiThrNode *lchild, * //左右孩子指针
PointerTag
//左右标志
}BiThrNode, *BiThrT
Status CreateBiThrTree(BiThrTree *T);
void InThreading(BiThrTree p);
Status InOrderThreading(BiThrTree *Thrt, BiThrTree T);
Status InOrderTraverse_Thr(BiThrTree T, Status (* Visit)(TElemType e));
BiThrTree.c
#include &common.h&
#include &BiThrTree.h&
#include &stdio.h&
#include &stdlib.h&
//这个创建二叉树的函数是直接从“二叉树的二叉链表存储表示”复制过来的
Status CreateBiThrTree(BiThrTree *T)
scanf(&%c&,&ch);
if(ch == ' ')
*T = NULL;
if(!(*T = (BiThrTree)malloc(sizeof(BiThrNode))))
exit(OVERFLOW);
(*T)-&data =
(*T)-&LTag = L
(*T)-&RTag = L
CreateBiThrTree(&(*T)-&lchild);
//构造左子树
CreateBiThrTree(&(*T)-&rchild);
//构造右子树
return OK;
void InThreading(BiThrTree p)
InThreading(p-&lchild);
//左子树线索化
if(!p-&lchild)
//前驱线索
p-&LTag = T
p-&lchild =
if(!pre-&rchild)
//后继线索
pre-&RTag = T
pre-&rchild =
InThreading(p-&rchild);
Status InOrderThreading(BiThrTree *Thrt, BiThrTree T)
if(!(*Thrt = (BiThrTree)malloc(sizeof(BiThrNode))))
exit(OVERFLOW);
(*Thrt)-&LTag = L
(*Thrt)-&RTag = T //建头结点
(*Thrt)-&rchild = *T //右指针回指
//若二叉树空，则左指针回指
(*Thrt)-&lchild = *T
(*Thrt)-&lchild = T;
InThreading(T);
//中序遍历进行中序线索化
pre-&rchild = *T //最后一个结点线索化
pre-&RTag = T
(*Thrt)-&rchild =
return OK;
Status InOrderTraverse_Thr(BiThrTree T, Status (* Visit)(TElemType e))
while(p != T)
while(p-&LTag == Link)
if(!Visit(p-&data))
return ERROR;
while(p-&RTag==Thread && p-&rchild !=T)
Visit(p-&data);
//访问后继结点
return OK;
Status InOrder(BiTree T, Status (* Visit)(TElemType e))
BiTree p = T;
InitStack(&s);
while(p!=NULL || !StackEmpty(&s)) //若当前结点p不空 或者 栈s不空，则执行循环体
while(p!=NULL) //若当前结点p不空
Push(&s, *p); //当前结点p进栈
p = p-& //将p的左孩子置为当前结点p
if(!StackEmpty(&s)) //若栈s不空
//GetTop1(&s, &p); //这里没必要在调用GetTop来获得栈顶元素了，因为下面的Pop1就可以得到栈顶元素了。
Pop1(&s, &p); //进行出栈操作，获得栈顶元素并将其置为当前结点p
Visit(p-&data); //访问当前结点的data。
p = p-& //将p的右孩子置为当前结点p
return OK;
//程序暂时还没看懂
#include &common.h&
#include &BiThrTree.h&
#include &stdio.h&
#include &stdlib.h&
Status PrintElement(TElemType e)
printf(&%c &,e);
return OK;
int main()
BiThrNode *
BiThrTree *
CreateBiThrTree(&tree);
InOrderThreading(&thr, tree);
InOrderTraverse_Thr(tree, PrintElement);
return OK;
本工程编译无错有警告，警告内容如下：（第一个警告暂且可以忽略，但我不明白第2、3个警告是怎么回事）
但是本工程执行结果倒是正确的。
（最近有点忙，好久没看《数据结构》了，本工程的内容暂时还没看懂（等用到的时候再看吧），不过可以运行，执行结果是正确的）
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：20974次
排名：千里之外
原创：56篇
(5)(2)(4)(2)(2)(1)(18)(2)(1)(9)(9)(5)画出下图所示二叉树的中序线索链表的存储表示。_百度知道
画出下图所示二叉树的中序线索链表的存储表示。
//e.baidu.baidu.jpg" esrc="http://e.jpg" target="_blank" title="点击查看大图" class="ikqb_img_alink">&nbsp<a href="http.中序线索链表是什么东西.com/zhidao/pic/item//zhidao/wh%3D450%2C600/sign=/zhidao/wh%3D600%2C800/sign=11fd61325cf/aaf736ebc8caaf0a55b319ebc4136d.hiphotos://e;&nbsp？没概念啊~&nbsp
提问者采纳
D F C E K B A
你这个是中序遍历吧，这个我也会~~
其他类似问题
为您推荐：
链表的相关知识
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁中序线索化二叉树 - 博客频道 - CSDN.NET
Young卡卡的博客
在校渣渣大学生,但有一颗热爱程序的心
分类：其他
中序线索化二叉树
当用二叉树链表作为二叉树的存储结构时，因为每个结点中只有指向其左右孩子结点的指针
，所以从任一结点出发只能直接找到该结点的左，右孩子。在一般的情况下靠它无法直接的
找到该结点在某种遍历次序下的前驱和后继结点。如果在每个结点中增加指向其前驱和后继
结点的指针，将降低存储空间的效率。
与此同时，我们可以证明：在n个结点的二叉树链表中含有n+1个空指针。因为含n个结点的
二叉树链表中含有2n个指针，除了根节点，每个结点都一个从父结点指向该结点的指针，因此
一共使用了n-1个指针，所以在n个结点的二叉树链表中含有2n-（n-1）=n+1个空指针
因此，可以利用这些空指针，存放指向在某种遍历次序下的前驱和后继结点的指针。这种附加
的指针称为线索，加上线索的二叉树称为线索二叉树。为了区分一个结点的指针是指向其孩子的
指针，还是指向其前驱或者后继结点的线索，可在每个结点中增加两个线索标志。这样，线索
二叉树结点类型定义为
1.当ltag=0时，表示lchild指向该结点的左孩子；
2.ltag=1时，表示lchild指向该结点的线性前驱结点;
3.rtag=0时，表示rchild指向该结点的右孩子;
4.rtag=1时，表示rchild指向该节点的线性后继结点；
以二叉树链表结点数据结构所构成的二叉树作为二叉树的存储结构，叫做线性二叉树链表；指向结
点的线性前驱或者线性后继结点的指针叫做线索；加上线索的二叉树称为线索二叉树；对二叉树以
某种次序遍历将其变为线索二叉树的过程叫做线索化。
中序线索化是指用二叉树链表结点数据结构建立二叉树的二叉树链表，然后按照中序遍历的方法访
问结点时建立线索。
#include&stdio.h&
#include&stdlib.h&
typedef enum ptag {link,thread};
//枚举 link==0 指针
thread==1 线索
typedef struct bithrtree{
struct bithrtree *plchild,*
ptag ltag,
}BITHRTREE,* PBITHRTREE;
PBITHRTREE
//设置为全局变量 始终指向上一结点
PBITHRTREE init(void);
void inorderthreading(PBITHRTREE thrt,PBITHRTREE t);
void inordertraverse(PBITHRTREE t);
void inthread(PBITHRTREE t);
int main(void)
PBITHRTREE
inorderthreading(&phead,t);
inordertraverse(&phead);
PBITHRTREE init(void)
PBITHRTREE pa,pb,pc,pd,pe,
pa=(PBITHRTREE)malloc(sizeof(BITHRTREE));
pb=(PBITHRTREE)malloc(sizeof(BITHRTREE));
pc=(PBITHRTREE)malloc(sizeof(BITHRTREE));
pd=(PBITHRTREE)malloc(sizeof(BITHRTREE));
pe=(PBITHRTREE)malloc(sizeof(BITHRTREE));
pf=(PBITHRTREE)malloc(sizeof(BITHRTREE));
if(NULL==pa||NULL==pb||NULL==pc||NULL==pd||NULL==pe)
printf(&动态分配失败&);
pa-&data=&#39;A&#39;; pa-&ltag=pa-&rtag=
pb-&data=&#39;B&#39;; pb-&ltag=pb-&rtag=
pc-&data=&#39;C&#39;; pc-&ltag=pc-&rtag=
pd-&data=&#39;D&#39;; pd-&ltag=pd-&rtag=
pe-&data=&#39;E&#39;; pe-&ltag=pe-&rtag=
pf-&data=&#39;F&#39;; pf-&ltag=pf-&rtag=
pa-&plchild=
pa-&prchild=
pb-&plchild=NULL;
pb-&prchild=
pd-&plchild=pd-&prchild=NULL;
pc-&plchild=
pc-&prchild=NULL;
pe-&plchild=NULL;
pe-&prchild=
pf-&plchild=pf-&prchild=NULL;
void inorderthreading(PBITHRTREE thrt,PBITHRTREE t)
thrt-&ltag=
thrt-&rtag=
thrt-&prchild=
//右指针回指
if(NULL==t)
thrt-&plchild=
//若为空 左回指指针
thrt-&plchild=t;
inthread(t);
//中序线索化
pre-&prchild=
pre-&rtag=
//最后一个结点的线索化
thrt-&prchild=
void inthread(PBITHRTREE t)
PBITHRTREE p=t;
inthread(p-&plchild);
//左子树线索化
if(p-&plchild==NULL)
//前驱线索
p-&plchild=
if(pre-&prchild==NULL)
//后驱线索
pre-&rtag=
pre-&prchild=p;
inthread(p-&prchild);
//右子树线索化
void inordertraverse(PBITHRTREE t)
PBITHRTREE
while(p!=t)
//指针回指指向头结点时结束
while(p-&ltag==link)
//当左标志域为0 说明左指针是左孩子
//一直遍历到的左子树的最左的结点
printf(&%c&,p-&data);
while(p-&rtag==thread && p-&prchild!=t)
//当右标志为线索（找后继） 并且没有回指
printf(&%c&,p-&data);
//rtag 不为线索 指针指向右孩子
排名：千里之外
（19）（1）（6）（7）（4）【图文】二叉树的线索化-例题_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
二叉树的线索化-例题
上传于||文档简介
&&二&#8203;叉&#8203;树&#8203;的&#8203;线&#8203;索&#8203;化&#8203;-&#8203;例&#8203;题
大小：256.00KB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢