欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

超硬核!一篇文章彻底搞懂【二叉树】及的前序、中序、后序三种遍历

程序员文章站 2022-05-03 15:52:41
...

树的概念与特性

1 树的概念

  • 树是类似于链表的线性结构,但又是一种典型的非线性的结构;树具有很强的层级性,相比于线性结构,其时间复杂度更低,效率更高;读者可以联系,生活中看见的树;

2 树的术语

  • 先看一张树的图片如下,去除图中的箭头和相关术语,树就是一种非线性的层级结构

超硬核!一篇文章彻底搞懂【二叉树】及的前序、中序、后序三种遍历
树的相关术语如下:

  • 根节点: 没有父节点的节点,上图 A节点;
  • 兄弟节点:具有相同的父节点的孩子节点;比如 F,G互为兄弟节点;
  • 叶子节点没有孩子节点的节点;比如D,F,G,I,J;
  • 祖先节点与孙节点:如果存在根节点A到节点 J 的路径,并且存在节点E出现在该路径上,则称E是节点 J 的祖先节点,J是 E 的孙节点;A B E H 都可以算是 J 的祖先节点;
  • 节点大小:节点的大小是指节点拥护的孙节点个数,包括自身; 比如E 节点大小为4;
  • 节点的深度:指根节点到节点的路径长度 ; 比如 (A-B-D ), 两个 链,即D节点的深度为2;
  • 节点的高度:指节点到最深节点的 路径长度;比如 (E - H -J), 两个链, 即E节点的高度为2;
  • 树的层级:具有相同深度的集合称为树的层级;比如 B和C ; 又比如 D,E,F,G
  • 树的高度和深度: 树的深度指所有节点中深度的最大值,树的高度指所有节点中高度的最大值;树的高度等于树的深度

3 树的类型

  • 二叉树: 如果一棵树中每个节点有0个或者1个或者2个节点,则称该树为二叉树;故空树也是二叉树;

  • 严格二叉树: 树的每个节点都有左孩子右孩子或者没有孩子;

超硬核!一篇文章彻底搞懂【二叉树】及的前序、中序、后序三种遍历

  • 斜树:斜树的每个节点只有一个孩子;若斜树的每个节点都只有左孩子则称为左斜树,若斜树的每个节点只有右孩子则称为右斜树;

超硬核!一篇文章彻底搞懂【二叉树】及的前序、中序、后序三种遍历

  • 满二叉树:所有的父节点都存在左孩子和右孩子,并且所有的叶子结点都在同一层上,则称该类树为满二叉树

超硬核!一篇文章彻底搞懂【二叉树】及的前序、中序、后序三种遍历

  • 完全二叉树:对于一棵具有n个节点的二叉树按照层级编号,同时,左右孩子按照先左孩子后右孩子编号,如果编号为i的节点同样深度的满二叉树中编号为i的节点在二叉树中的位置完全相同,则这棵二叉树称为完全二叉树;故满二叉树一定是完全二叉树,反之不成立

超硬核!一篇文章彻底搞懂【二叉树】及的前序、中序、后序三种遍历

2.4满二叉树的性质

  • 满叉树的节点个数: 假设满二叉树层级为k,根据 数学归纳法和等比数列求和公式可得 2^0 + 2^1 +…+ 2^k = 2^(k+1) - 1; 推导过程如下图;

  • 满二叉树的叶子节点个数:根据满二叉树的结构可知,第k层就是叶子节点所在的层,故叶子节点个数为 2^k个

超硬核!一篇文章彻底搞懂【二叉树】及的前序、中序、后序三种遍历

二叉树的实现

二叉树的结构

  • 根据二叉树的结构可知,每个节点都可以假设有左孩子和右孩子,则可以对应为 左指针和右指针,并且每个节点上都可以存储值;故经过面向对象的编程思想进行抽象后的类如下
/**
 * <p>二叉树的结构 </p>
 */
public class TreeNode {

    // 左孩子
    private TreeNode leftNode;
    // 右孩子
    private TreeNode rightNode;
    // 存储值
    private Object value;
    // 构造方法
    TreeNode(Object value){
    this.value = value;
    }
   // 省略 set get 
}   
  • 现在需要实现以下的一颗满二叉树;

超硬核!一篇文章彻底搞懂【二叉树】及的前序、中序、后序三种遍历

思路如下:

  • 首先根节点储存1;然后分别储存 左孩子2,右孩子3;
  • 其次左孩子节点作为父节点,然后分别储存 左孩子4,右孩子5;
  • 最后右孩子节点作为父节点然后分别储存 左孩子6,右孩子7;
  • 代码实现如下:
 public static void main(String[] args) {
        // 初始化树
        TreeNode tree = initTree();

    }
    public static TreeNode initTree(){
        // 创建7个节点
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode6 = new TreeNode(6);
        TreeNode treeNode7 = new TreeNode(7);
        // 根据上面思路对节点进行组装
        // 组装根节点
        treeNode1.setLeftNode(treeNode2);
        treeNode1.setRightNode(treeNode3);
        // 组装左孩子
        treeNode2.setLeftNode(treeNode4);
        treeNode2.setRightNode(treeNode5);
        // 组装右孩子
        treeNode3.setLeftNode(treeNode6);
        treeNode3.setRightNode(treeNode7);
        return treeNode1;
    }

二叉树的遍历与实现

  • 二叉树的遍历分为前序遍历,中序遍历,后续遍历;假设 当前节点 为C (Current Node), 左节点为L ,右节点为R;
前序遍历:C----->L------->R
中序遍历:L----->C------->R
后续遍历:R----->C------>L

先序遍历的实现

思路 :

  • 首先访问当前节点;
  • 其次访问左节点;
  • 最后访问后节点;
  • 回到 前图 前序遍历CLR就是 1,2,4,5,3,6,7;
 public static void main(String[] args) {
        // 初始化树
        TreeNode tree = initTree();
        // 调用先序遍历
        preOrderTree(tree);
    }
    /**
     * <p> 先序遍历</p>
     * @Param [rootNode]
     * @Return void
     */
    public static void preOrderTree(TreeNode rootNode){
        if (rootNode!=null){
            // 值
            System.out.println(rootNode.getValue());
            // 左孩子
            preOrderTree(rootNode.getLeftNode());
            // 右孩子
            preOrderTree(rootNode.getRightNode());
        }

    }
  • 输出
1
2
4
5
3
6
7
  • 先序遍历实现为线性实现,时间复杂度为O(n)

中序遍历的实现

思路 :

  • 首先访问左节点
  • 其次访问当前节点
  • 最后访问右节点
  • 回到 前图中序遍历的结果是 4,2,5,1, 6,3,7
 public static void main(String[] args) {
        // 初始化树
        TreeNode tree = initTree();
        // 调用中序遍历
        middleOrderTree(tree);
    }
    /**
     * <p> 中序遍历</p>
     * @Param [rootNode]
     * @Return void
     */
    public static void middleOrderTree(TreeNode rootNode){
        if (rootNode!=null){
            // 左孩子
            middleOrderTree(rootNode.getLeftNode());
            // 值
            System.out.println(rootNode.getValue());
            // 右孩子
            middleOrderTree(rootNode.getRightNode());
        }

    }
  • 输出
4
2
5
1
6
3
7
  • 中序遍历实现为线性实现,时间复杂度为O(n)

后续遍历的实现

思路:

  • 首先访问左节点
  • 其次访问右节点
  • 最后访问当前节点
  • 回到 前图中序遍历的结果是 4,5,2,6, 7,3,1
 public static void main(String[] args) {
        // 初始化树
        TreeNode tree = initTree();
        // 调用后续遍历
        postOrderTree(tree);
    }

    /**
     * <p>后续遍历 </p>
     * @Param [rootNode]
     * @Return void
     */
    public static void postOrderTree(TreeNode rootNode){
        if (rootNode!=null){
            // 左孩子
            postOrderTree(rootNode.getLeftNode());
            // 右孩子
            postOrderTree(rootNode.getRightNode());
            // 值
            System.out.println(rootNode.getValue());
        }

    }
  • 输出
4
5
2
6
7
3
1
  • 后序遍历实现为线性实现,时间复杂度为O(n)
相关标签: 算法与数据结构