二叉树的基本操作 - 遍历

二叉树的基本操作 - 遍历

二叉树的遍历是非常重要的,因为我们一般对树做的很多操作基本上都是要建立在遍历的基础上的。
常件的遍历方法方式有:

  • 先序遍历:先根、左子树、右子树
  • 中序遍历:左子树、根、右子树
  • 后序遍历:左子树、右子树、根
  • 层次遍历:从上到下、从左到右

各种遍历的java实现在我的github上可以查看


例子:

  1. 输出二叉树中的叶子节点:

在遍历二叉树的算法中增加监测结点的“左右子树是否都为null”

void printLeaves(Node root){
    if(root != null){
          if(root.left != null  && root.right != null)
                      println(root.val);
          printLeaves(root.left);
          printLeaves(root.right);
     } 
}
  1. 求二叉树的高度

我们只需要分别求出左右子树的高度,然后取最高的。递归这个过程:

int getTreeHeight (Node root){
      int leftH ,rightH, maxH;
       if(root != null){
          printLeaves(root.left);
          printLeaves(root.right);
          maxH = (leftH>rightH)?leftH:rightH;
          return (maxH + 1);
     }
}
  1. 由两种遍历序列确定一个二叉树:
    我们必须要通过前序遍历或后序遍历,结合着中序遍历来确定一个二叉树。如果前序遍历和后序遍历在一起我们无法确定根节点在哪。
Paste_Image.png

代码在我的gitHub上可以查看。

最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容