专栏名称: Carson_Ho

走在产品路上的Android研究生

数据结构：图文详解二叉树（遍历、类型、操作）

Carson_Ho · 掘金 · android · 2020-02-17 01:02

正文

前言

二叉树是一种特殊的树结构，应用广泛
下面，我将详细介绍二叉树的相关知识，希望你们会喜欢。

1. 简介

2. 性质

3. 存储结构

二叉树的存储结构包括：顺序存储结构 & 链式存储结构

注：上述的链式存储方式，即为树结构中的孩子兄弟表示法。具体如下：

大多数情况下，二叉树的建立会采用链式存储结构

4. 二叉树的建立

建立的核心：数据结构 = 链表、实现方式 = 递归 / 非递归算法

4.1 数据结构

采用链表的方式，也称为：二叉链表

为了确保每个结点都有左右孩子，所以空指针 = 虚结点 = #

这种处理也称： 扩展二叉树

节点结构 & 树的定义如下

   /**
     * 设置结点结构
     */
    public static class TreeNode<T> {
        T val; // 二叉树的结点数据
        TreeNode<T> leftNode; // 二叉树的左子树（左孩子）
        TreeNode<T> rightNode; // 二叉树的右子树（右孩子）

        public TreeNode(T data,TreeNode<T> left,TreeNode<T> right) {
            this.val = data;
            this.leftNode = left;
            this.rightNode = right;
        }


        // 获得 & 设置二叉树的结点数据
        public T getData(){
            return val;
        }

        public void setData(T data){
            this.val = data;
        }

        // 获得 & 设置二叉树的左子树（左孩子）
        public TreeNode getLeftNode(){
            return leftNode;
        }

        public void setLeftNode(TreeNode leftNode){
            this.leftNode = leftNode;
        }

        // 获得 & 设置二叉树的右子树（右孩子）
        public TreeNode getRightNode(){
            return rightNode;
        }
        public void setRightNode(TreeNode rightNode){
            this.rightNode = rightNode;
        }
    }


/**
 * 作用：构造二叉树
 * 注：必须逆序建立，即：先建立子节点，再逆序往上建立
 * 原因：非叶子节点会使用到下面的节点，而初始化是按顺序初始化的，不逆序建立会报错
 */ 
public Node init(){
    // 结构如下：(由下往上建立)
    //            A
    //       B         C
    //    D         E     F
    //  G   H         I
    Node I = new Node("I", null, null);
    Node H = new Node("H", null, null);
    Node G = new Node("G", null, null);
    Node F = new Node("F", null, null);
    Node E = new Node("E", null, I);
    Node D = new Node("D", G, H);
    Node C = new Node("C", E, F);
    Node B = new Node("B", D, null);
    Node A = new Node("A", B, C);
    return A;  // 返回根节点
}

4.2 递归算法

通过 递归方式 构造出整个二叉树
构造过程 = 将遍历算法的 输出结点操作 替换成： 生成结点 & 赋值操作 即可

关于遍历算法，下节会详细说明

5. 二叉树的遍历

5.1 定义

从根节点出发，按照某种次序访问二叉树中的所有结点， 使得每个结点被访问1次且只被访问1次

5.2 遍历方式

二叉树的遍历方式包括：

前序遍历（深度优先遍历）
中序遍历
后序遍历
层序遍历（广度优先遍历）

5.3 遍历实现

遍历的实现方式分为：递归 & 非递归方式，下面会详细说明

5.3.1 前序遍历

也称深度优先遍历

简介

递归实现

   /**
     * 内容：前序遍历
     * 方式：递归
     */
     public void preOrder(Node root){
        // 1. 判断二叉树结点是否为空；若是，则返回空操作
        if(root ==null)
            return;

        // 2. 访问根节点（显示根结点）
        printNode(root);

        // 3. 遍历左子树
        preOrder(root.getLeftNode());

        // 4. 遍历右子树
        preOrder(root.getRightNode());

    }

非递归实现
主要采用 栈实现

/**
  * 方式：非递归（栈实现）
  */
    public static void preOrder_stack(Node root){

        Stack<Node> stack = new Stack<Node>();

        // 步骤1：直到当前结点为空 & 栈空时，循环结束
        while(root != null || stack.size()>0){

            // 步骤2：判断当前结点是否为空
              // a. 若不为空，执行3
              // b. 若为空，执行5
              if(root != null){

                // 步骤3：输出当前节点，并将其入栈
                printNode(root);
                stack.push(root);

                // 步骤4：置当前结点的左孩子为当前节点
                // 返回步骤1
                root = root.getLeftNode();

            }else{

                // 步骤5：出栈栈顶结点
                root = stack.pop();
                // 步骤6：置当前结点的右孩子为当前节点
                root = root.getRightNode();
                  // 返回步骤1
            }
        }
    }

5.3.2 中序遍历

简介

递归实现

/**
  * 方式：递归
  */
    public void InOrder(Node root){
    
        // 1. 判断二叉树结点是否为空；若是，则返回空操作
        if(root ==null)
            return;

        // 2. 遍历左子树
        InOrder(root.getLeftNode());

        // 3. 访问根节点（显示根结点）
        printNode(root);

        // 4. 遍历右子树
        InOrder(root.getRightNode());

    }

非递归实现
主要采用 栈实现

/**
  * 方式：非递归（栈实现）
  */
    public static void InOrder_stack(Node root){

        Stack<Node> stack = new Stack<Node>();

        // 1. 直到当前结点为空 & 栈空时，循环结束
        while(root != null || stack.size()>0){

            // 2. 判断当前结点是否为空
            // a. 若不为空，执行3、4
            // b. 若为空，执行5、6
            if(root != null){

                // 3. 入栈当前结点
                stack.push(root);

                // 4. 置当前结点的左孩子为当前节点
                // 返回步骤1
                root = root.getLeftNode();

            }else{

                // 5. 出栈栈顶结点
                root = stack.pop();
                // 6. 输出当前节点
                printNode(root);
                // 7. 置当前结点的右孩子为当前节点
                root = root.getRightNode();
                // 返回步骤1
            }
        }

5.3.3 后序遍历

简介

递归实现

/**
  * 方式：递归
  */
    public void PostOrder(Node root){
        // 1. 判断二叉树结点是否为空；若是，则返回空操作
        if(root ==null)
            return;

        // 2. 遍历左子树
        PostOrder(root.getLeftNode());

        // 3. 遍历右子树
        PostOrder(root.getRightNode());

        // 4. 访问根节点（显示根结点）
        printNode(root);

    }

非递归实现
主要采用 栈实现

/**
  * 方式：非递归（栈实现）
  */
    public void PostOrder_stack(Node root){

        Stack<Node> stack = new Stack<Node>();
        Stack<Node> output = new Stack<Node>();

        // 步骤1：直到当前结点为空 & 栈空时，循环结束——> 步骤8
        while(root != null || stack.size()>0){

            // 步骤2：判断当前结点是否为空
            // a. 若不为空，执行3、4
            // b. 若为空，执行5、6
            if(root != null){

                // 步骤3：入栈当前结点到中间栈
                output.push(root);

                // 步骤4：入栈当前结点到普通栈
                stack.push(root);

                // 步骤4：置当前结点的右孩子为当前节点
                // 返回步骤1
                root = root.getRightNode();

            }else{

                // 步骤5：出栈栈顶结点
                root = stack.pop();
                // 步骤6：置当前结点的右孩子为当前节点
                root = root.getLeftNode();
                // 返回步骤1
            }
        }

        // 步骤8：输出中间栈的结点
        while(output.size()>0){
            printNode(output.pop());

        }

    }

5.3.4 层序遍历

简介

实现思路
非递归实现，采用队列

算法流程图

/**
  * 方式：非递归（采用队列）
  */
    public void levelTravel(Node root){
        // 创建队列
        Queue<Node> q=new LinkedList<Node>();

        // 1. 判断当前结点是否为空；若是，则返回空操作
        if(root==null)
            return;
        // 2. 入队当前结点
        q.add(root);

        // 3. 判断当前队列是否为空，若为空则跳出循环
        while(!q.isEmpty()){

            // 4. 出队队首元素
            root =  q.poll();

            // 5. 输出 出队元素
            printNode(root);

            // 6. 若出队元素有左孩子，则入队其左孩子
            if(root.getLeftNode()!=null) q.add(root.getLeftNode());

            // 7. 若出队元素有右孩子，则入队其右孩子
            if(root.getRightNode()!=null) q.add(root.getRightNode());
        }
    }

5.4 遍历方式总结

6. 二叉树的类型

上述讲解的是基础的二叉树
根据不同的需求场景，二叉树分为许多类型，主要有：

数据结构：图文详解二叉树（遍历、类型、操作）

正文

前言

目录

1. 简介

2. 性质

3. 存储结构

4. 二叉树的建立

4.1 数据结构

4.2 递归算法

5. 二叉树的遍历

5.1 定义

5.2 遍历方式

5.3 遍历实现

5.3.1 前序遍历

5.3.2 中序遍历

5.3.3 后序遍历

5.3.4 层序遍历

5.4 遍历方式总结

6. 二叉树的类型

请到「今天看啥」查看全文

数据结构：图文详解二叉树（遍历、类型、操作）

正文

前言

目录

1. 简介

2. 性质

3. 存储结构

4. 二叉树的建立

4.1 数据结构

4.2 递归 算法

5. 二叉树的遍历

5.1 定义

5.2 遍历方式

5.3 遍历实现

5.3.1 前序遍历

5.3.2 中序遍历

5.3.3 后序遍历

5.3.4 层序遍历

5.4 遍历方式总结

6. 二叉树的类型

请到「今天看啥」查看全文

4.2 递归算法