基于遍历搜索二叉树中最长路径的算法研究
作者：王 敏 赵晓雷
来源：《现代电子技术》2010年第08期
        摘 要:在对二叉树存储结构进行分析的基础上,介绍二叉树遍历算法的一种应用,即基于求解二叉树深度算法设计实现的搜索二叉树中最长路径的算法。这里详细介绍了搜索二叉树中最长路径问题的分析解决思路,在对可能的预期结果进行分析的基础上,给出了算法的设计方案,同时给出了具体的C语言算法描述。
        关键词:二叉树; 二叉树遍历; 完全二叉树; 二叉树的最长路径; 二叉树深度
        中图分类号:TP311.12文献标识码:A
        文章编号:1004-373X(2010)08-0054-02
        Algorithm of Searching Longest Path in Binary Tree Based on Traverse
        WANG Min, ZJAO Xiao-lei
        (Weinan Teachers University, Weinan714000, China)
        Abstract:By analyzing the storage structure of binary tree, a kind ofapplication of binary tree traversal algorithm, that is,the algorithm ofsearching the longest path in binary tree, which is realized by solving the depth of binary tree, is introduced. The solution ideas of searching the longest path in binary tree are proposed in detail. The design scheme of the algorithm is given by analysing the expected results. The algorithm description in C language is presented.
        Keywords:binary tree; binary tree traverse; complete binary tree; longest path in binary tree; depth of binary tree
        0 引 言
        二叉树的逻辑结构为树型结构,结点间是一对多的层次关系。所谓二叉树的遍历是指按一定规律对二叉树中每个结点进行访问且仅访问一次[1-2]。“访问”的含义很广,可以是对结点作各种处理,如输出结点的信息等[2,3]。二叉树的遍历是二叉树中所有其他运算的基础。
        本文介绍了二叉树遍历在搜索二叉树中最长路径算法中的应用,重点分析算法的设计过程,并给出算法的C语言描述。
        1 二叉树的存储结构
        首先考虑二叉树的存储结构。接近完全二叉树形态的二叉树采用静态向量的存储方式比较好,此时结点的父子关系可根据完全二叉树的性质5 \(对一棵有 n个结点的完全二叉树的结点按层序从1开始编号,则对任一序号大于1的结点i,其双亲结点序号为\,若其左孩子序号小于n,则为2i,若其右孩子序号小于n,则为2i+1) 定位对应的下标结点,其存储结构可用C语言定义如下 \:
        #define MAX 1000
        typedef struct{
        DataType data[MAX];
        int datanum;
        } SeqTree;
        其中:data成员用于存储结点的元素值;datanum成员用于记录树中结点的总个数。
        对于非完全二叉树,一般采用二叉链表方式存储,其存储结构如图1所示。
        图1 二叉链表结点结构
        可用C语言定义如下 \:
        typedef struct node{
        DataType data;
        struct node *Lchild,*Rchild;
        } Node, *BTree;
        其中:data成员用于存储结点的元素值;Lchild和Rchild成员分别为指向该结点中左右孩子结点的指针。下面介绍采用二叉链表存储结构的算法。
        2 搜索二叉树中的最长路径
        所谓二叉树中的最长路径,一定是从根结点(位于第1层)到达树中所在层次最大(也即树的深度h层)的某个结点的一条路径,于是,搜索该最长路径的算法可以通过求解二叉树的深度得以解决。
        2.1 二叉树的遍历算法
        对二叉树进行遍历的方式分前序、中序、后序和层序,前三种均是以访问二叉树中根结点(root)的次序作为命名的依据,第四种是从二叉树的根开始逐层遍历。这里主要介绍并利用后序遍历算法,其递归算法设计思想如下:
        (1) 若二叉树为空,则遍历过程结束;
        (2) 否则;
        ① 后序遍历根结点的左子树;
        ② 后序遍历根结点的右子树;
        ③ 访问根结点,算法结束[1,3-4,6-9]。
        2.2 后序遍历求解二叉树的深度
        求解二叉树深度的递归算法思想可以描述为:
        (1) 若二叉树为空,则深度为0;
        (2) 否则其深度应为根结点中左右子树深度的最大值加1[1,10]。
        在求解二叉树深度的过程中,要对二叉树进行遍历。可以利用二叉树中后序遍历算法的设计思想实现这一过程。基于二叉链表存储结构(BTree)的C语言算法描述如下:
        int PostTreeDepth(BTree root)
        { int hl,hr,max;
完全二叉树算法        if(root)
        {hl=PostTreeDepth(root->Lchild);
        hr=PostTreeDepth(root->Rchild);
        max=hl>hr?hl:hr;
        return (max+1); }
        else
        return 0;
        }
        2.3 搜索二叉树中的最长路径
        搜索二叉树中的最长路径时,需要考虑以下因素:
        首先,当二叉树的最深层有两个以上结点时,其最长路径不止一条,此时只需要给出最先到的一条即可。
        其次,对于所求得的最长路径应该如何记录,这取决于问题的需求:
        (1) 最简单的需求是输出该最长路径。此时只需要在遍历时输出结点的值即可。
        (2) 若问题的解决需要记录该路径,则需考虑如何对求得的路径进行存储,可采用以下几种方案:
        方案一:另外申请一个顺序表结点空间用于存储该路径。
        此时顺序表中结点的结构可设计为如图2所示。
        图2 路径中的结点结构
        图2中data域用于存储结点的元素值;tag域用于标记后继结点是该结点的左孩子(设tag为0),还是右孩子(设tag为1)。遍历过程中,每确定路径中一个结点,即将结点值填入顺序表对应的位置,并设置其前驱结点的tag域。
        方案二:另外申请二叉链表的结点空间,构成仅含一条单支的二叉树。
        此时路径中结点的存储结构与前述二叉链表存储结构(BTree)相同。在二叉树中,每确定路径中一个结点后,需要进行以下步骤的操作:
        ① 为该结点申请新的结点空间;
        ② 将结点值填入新结点的data域,并设置新结点的Lchild和Rchild,指针为NULL;
        ③ 根据新结点是路径中前驱结点的左孩子或右孩子,将新结点插入前驱结点中Lchild或Rchild指针的后面。
        方案三:利用原二叉树的二叉链表作出标记进行记录。
        这种方案需要对原二叉树的二叉链表结构进行调整,在每个结点上增加一个tag域,用于标记该结点是否属于搜索到的最长路径。例如,若结点属于最长路径,则将该结点的tag域置1,否则为0。
        下面仅以输出所求得的最长路径为例,给出搜索最长路径的算法,该算法的递归设计思路如下:
        (1) 若二叉树为空,输出空序列,算法结束;
        (2) 否则,输出根结点元素值,并求根结点的左右子树深度,继续执行第(3)步;
        (3) 根据第(2)步求得的左右子树深度,选择深度大的一棵子树,从其根结点开始求最长路径。
        假设树中结点的元素值为字符型,即前述抽象数据类型DataType为char类型,则该递归算法中基于二叉链表存储结构(BTree)上的C语言描述如下:
        void SearchLongestPath(BTree root)
        { int hl,hr;//分别表示根结点左右子树的深度
        if(!root)
        printf("%c",′/0′);//树空则输出空串
        else {
        printf("%c",root->data);//输出根结点元素值
        hl=PostTreeDepth(root->Lchild);
        hr=PostTreeDepth(root->Rchild);
        //调用求树的深度的算法求根结点左右子树深度
        root=hl>=hr?root->Lchild:root->Rchild;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。