把一棵树的叶子结点从左至右链接成单链表
王道课后习题:设计一个算法将二叉树的叶结点按从左到右的顺序连成一个单链表,表头指针为head。二叉树按链式方式存储,链接时用叶结点的右指针域来存放单链表指针。
算法思想:该算法需要以从左到右的顺序遍历二叉树的叶结点,而不管是先序中序还是后续,叶结点的访问顺序都是从左到右,所以都能实现,这里我们选用中序遍历。处理第一个叶结点时,让head指向他,处理之后的结点时只需让之前的叶结点的右指针域指向他即可,遍历完所有结点后让最后一个结点的右指针域指向空,在这期间用pre来标记之前的结点。
算法代码如下:
Linklist head,pre=NULL; //定义全局变量
Linklist InOrder(BiTree bt){
if(bt){
InOrder(bt->lchild);
if(bt->lchild==NULL&&bt->rchild==NULL) //叶结点
if(pre==NULL){ //处理第一个结点时让head指向他
head=bt;
pre=bt;
}
else{
pre->rchild=bt; //处理之后的结点只需让之前的结点右指针指向他
pre=bt; //更新pre指针
}
InOrder(bt->rchild);
pre->rchild=NULL; //设置链表尾
}
return head;
}
本题重要思想:通过先中后遍历的特性来按顺序寻找叶结点,也可以推广出通过“右根左”来遍历设置从右到左的链表。
原文地址:http://www.cnblogs.com/Auous/p/16791000.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性