把一棵树的叶子结点从左至右链接成单链表

王道课后习题:设计一个算法将二叉树的叶结点按从左到右的顺序连成一个单链表,表头指针为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. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性