美文网首页
遍历二叉树的应用

遍历二叉树的应用

作者: 顶级工程师闯天涯 | 来源:发表于2017-11-11 00:34 被阅读156次

    1.输出二叉树的叶子结点

    这里,我们首先需要明白叶子结点的定义:左右子树是否都为空,接下来,用代码来实现就变得简单啦。即:我们只需要在二叉树的遍历算法中增加检测结点的"左右子树是否都为空"即可。具体代码如下:

        /**
        * 前序遍历二叉树操作 
        * 在每次遍历结点之前,首先判断其左子树和右子 树是否都为空
        */
    void preOrderPrintLeaves(BinTree BT){
        if(BT){
            if(!BT -> Left && ! BT -> Right){
                printf("%d",BT -> Data);
            }
    
            PreOrderPrintLeaves(BT -> Left);
            PreOrderPrintLeaves(BT -> Right);
        }
    }
    
    // 再次强调,这里的if(BT)  等价于 if(BT != NULL)
    

    2.求二叉树的高度

    二叉树是递归定义的,所以二叉树的高度也可以考虑用递归来实现。首先我们来分析一下:结点和其左右结点的关系。我们可以发现 :

    Height = max{LeftHeight,RightHeight}+1

    树的高度与其左右子树高度的关系

    很显然,我们要想知道二叉树的高度,必须要先知道其左右子树的高度。这样的话,我们显然应该采用后序遍历的基本逻辑来实现该功能。

    // 改造后序遍历
    int PostOrderGetHeight(BinTree BT){
        int HL; // 左子树高度
        int HR; // 右子树高度
        int MaxH; // 最大高度
        if(BT){
            HL = PostOrderGetHeight(BT -> Left);//递归求左子树的高度
            HR = PostOrderGetHeight(BT -> Right);//递归求右子树的高度
            MaxH = (HL > HR) ? HL : HR ;// 取两者的最大值
            return  (MaxH + 1); // 返回树的深度
        }
        return 0; // 空树的深度为 0
    }
    

    3. 二元运算表达式树及其遍历

    二元表达式

    观察上图可以知道:叶子结点都是操作数,而其他结点都是运算符号;

    采用三种遍历方式会得到三种不同的访问结果:

    1. 先序遍历 -> 前缀表达式:+ + a * b c * + * d g f e ;
    2. 中序遍历 -> 中缀表达式:a + b * c + d * e + f * g ;
    3. 后序遍历 -> 后缀表达式:a b c * + d e * f + g * + ;

    由中序遍历得到的中缀表达式会受到运算符优先级的影响

    如何解决中序遍历的中缀表达式不准的问题呢? 答案是:通过访问左子树之前加入左括号,而访问右子树之前添加右括号的形式来保证得到正确的中缀表达式。即:通过加括号的形式来保证运算符的优先级;

    4.由两种遍历序列确定二叉树

    问题描述:已知三种遍历中的任意两种遍历序列,能否唯一确定一颗二叉树呢?

    必须要中序遍历才可以。没有中序遍历序列,我们只能确定根节点,而无法确定左右子树的关系。

    先序和中序来确定一棵二叉树

    分析过程:

    1. 根据先序遍历序列的第一个结点确定根结点;
    2. 根据根结点中序遍历序列中分割出左右子两个子序列;
    3. 左子序列和右子序列分别递归使用相同的方法继续分割

    相关文章

      网友评论

          本文标题:遍历二叉树的应用

          本文链接:https://www.haomeiwen.com/subject/xzdkmxtx.html