首页 25考研 在职考研 0元畅学 26考研

新东方在线 > 考研 > 计算机 > 考研计算机资料 > 正文

扫码加入训练营

牢记核心词

学习得礼盒

计算机考研：数据结构常用算法精析(6)

2013-12-11 14:35:35来源：新东方在线编辑

　　二叉树的线索化

　　线索化分成，前序线索化和中序线索化后序线索化，他们的区别在于每个结点的前驱和后继的不同，各种不同的遍历得到不同的前驱和后继。如果考手画线索化二叉树，则三种都有可能，如果考算法描述，那么就只能考中序线索化二叉树了(其它两个的比较繁琐)。

　　LchildLtagdataRtagRchild

　　我们讨论建立中序线索二叉树。

　　算法思路：利用中序递归遍历算法，即：

　　1线索化根的左子树 2 线索化当前结点 3 线索化根的右子树。

　　其中pre为外部指针(初值=NULL)，在算法运行中，pre为当前搜索结点的前驱指针。

　　算法描述：

　　typedef struct Bnode

　　{ int Ltag,Rtag; //左右特征位//

　　datatype data;

　　struct Bnode *Lchild,*Rchild ;

　　}BTnode , *BTptr;

　　总控函数:中序线索化二叉树另外加了一个结点(相当于循环链表的头结点)。

　　Status InorderTheaing(BinThrtree& Thrt,BiThrTree T)

　　{

　　if(!(Thr=(BinThrTree)malloc(sizeof(BiThrNode)))) exit(OVERFLOW);

　　Thrt->LTag=Link;Thrt->RTag=Threak;

　　Thrt->rchild=Thrt;//相当于空的循环链表，先将尾指针指向头结点。

　　if(!T) Thrt->lchild=Thrt;//空树那么整个也是空的了，只有一个附加的头结点了

　　else

　　{

　　Thrt->lchild=T;

　　pre=Thrt;//因为pre始终是当前结点的前驱结点，那么初始值就应该是头结点

　　Inthreadbt(T);将整个树线索化

　　pre->RTag=Thread;//当整个树都线索化了那么，pre肯定指向最后一个结点了

　　pre->rchhild=Thrt;//所以pre的后继应该是头结点

　　}

　　return OK;

　　}

　　void Inthreadbt (BTptr T) //中序线索二叉树//

　　{

　　if (T)

　　{

　　Inthreadbt(T->Lchild);//线索化左子树//

　　visit(T); 改成 if(T->Lchild==NULL)

　　{

　　T->Ltag=Thread;

　　T->Lchild=pre;

　　}

　　if(pre ->rchild= =NULL)

　　{ pre->RTag=Thread;

　　pre->Rchild=T;

　　}

　　pre=T;

　　Inthreadbt(T->Rchild); //线索化右子树//

　　}

　　}

考研公开课小程序

本文关键字: 计算机 考研 数据结构

上一页 1.. 6 7 8 9 10 11 12 13 14 ..17 下一页

考研英语核心词汇营

背词+听课+练习+督学，学习得礼盒

更多资料

添加班主任领资料

添加考研班主任
免费领取考研历年真题等复习干货资料

  • 1.打开手机微信【扫一扫】，识别上方二维码；
  • 2.添加班主任，可领取学习资料。
更多>>
更多内容
25考研 在职研 AI择校 去测评 领资料

关注新东方在线考研服务号

获得21考研真题及答案解析

1. 打开手机微信【扫一扫】，识别上方二维码；
2.点击【关注公众号】，获取资料大礼包。

考研资料大礼包

历年考研真题及答案解析下载

英语一 英语二 政治 数学一 数学二 数学三 西医综合 教育综合 心理学综合
立即下载
近10年考研真题及答案免费下载
更多>>
更多公开课>>
更多>>
更多资料
我要
反馈 返回
首页
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10