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

Carson.Ho

发布于 2020-01-13 17:03:30

6170

发布于 2020-01-13 17:03:30

文章被收录于专栏：Android知识分享Android知识分享

前言

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

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());
        }
    }