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

喜欢ヅ旅行 2023-06-24 15:27 3阅读 0赞

![e42c52b9af8d79486a0f3cd0e50df7b7.png][]

# 前言 #

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

--------------------

# 目录 #

![示意图][format_png]

--------------------

# 1. 简介 #

![示意图][format_png 1]

--------------------

# 2. 性质 #

![示意图][format_png 2]

--------------------

# 3. 存储结构 #

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

![示意图][format_png 3]

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

![示意图][format_png 4]

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

--------------------

# 4. 二叉树的建立 #

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

### 4.1 数据结构 ###

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

> 1.  为了确保每个结点都有左右孩子，所以空指针 = 虚结点 = \#
> 2.  这种处理也称：**扩展二叉树**

![示意图][format_png 5]

*  节点结构 & 树的定义如下

/**
         * 设置结点结构
         */
        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 遍历方式 ###

二叉树的遍历方式包括：

1.  前序遍历（深度优先遍历）
2.  中序遍历
3.  后序遍历
4.  层序遍历（广度优先遍历）

### 5.3 遍历实现 ###

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

#### 5.3.1 前序遍历 ####

> 也称 深度优先遍历

*  简介

![示意图][format_png 6]

*  递归实现

/**
         * 内容：前序遍历
         * 方式：递归
         */
         public void preOrder(Node root){
            // 1. 判断二叉树结点是否为空；若是，则返回空操作
            if(root ==null)
                return;
    
            // 2. 访问根节点（显示根结点）
            printNode(root);
    
            // 3. 遍历左子树
            preOrder(root.getLeftNode());
    
            // 4. 遍历右子树
            preOrder(root.getRightNode());
    
        }

![示意图][format_png 7]

*  非递归实现  
    主要采用 **栈实现**  
    ![流程图][format_png 8]

/**
      * 方式：非递归（栈实现）
      */
        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
                }
            }
        }

![示意图][format_png 9]

### 5.3.2 中序遍历 ###

*  简介

![示意图][format_png 10]

*  递归实现

/**
      * 方式：递归
      */
        public void InOrder(Node root){
        
            // 1. 判断二叉树结点是否为空；若是，则返回空操作
            if(root ==null)
                return;
    
            // 2. 遍历左子树
            InOrder(root.getLeftNode());
    
            // 3. 访问根节点（显示根结点）
            printNode(root);
    
            // 4. 遍历右子树
            InOrder(root.getRightNode());
    
        }

![示意图][format_png 11]

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

![流程图][format_png 12]

/**
      * 方式：非递归（栈实现）
      */
        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 后序遍历 ###

*  简介

![示意图][format_png 13]

*  递归实现

/**
      * 方式：递归
      */
        public void PostOrder(Node root){
            // 1. 判断二叉树结点是否为空；若是，则返回空操作
            if(root ==null)
                return;
    
            // 2. 遍历左子树
            PostOrder(root.getLeftNode());
    
            // 3. 遍历右子树
            PostOrder(root.getRightNode());
    
            // 4. 访问根节点（显示根结点）
            printNode(root);
    
        }

![示意图][format_png 14]

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

![示意图][format_png 15]

/**
      * 方式：非递归（栈实现）
      */
        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());
    
            }
    
        }

![示意图][format_png 16]

### 5.3.4 层序遍历 ###

*  简介

![示意图][format_png 17]

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

![示意图][format_png 18]

*  算法流程图  
    ![示意图][format_png 19]

/**
      * 方式：非递归（采用队列）
      */
        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());
            }
        }

![示意图][format_png 20]

### 5.4 遍历方式总结 ###

![示意图][format_png 21]

--------------------

# 6. 二叉树的类型 #

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

![示意图][format_png 22]

*  下面，我将详细讲解各种二叉树的类型

### 6.1 线索二叉树 ###

*  简介

![示意图][format_png 23]

*  示意图  
    ![示意图][format_png 24]
 *  特别注意
    
     *  问：如何区别该指针 = 指向左（右）孩子 or 前驱（后继）
     *  答：增设标志域：Ltag 和 Rtag

![示意图][format_png 25]

### 6.2 二叉排序树 ###

> 也称：二叉查找树、二叉搜索树

*  特点  
    ![示意图][format_png 26]
 *  作用 & 应用场景

![示意图][format_png 27]

### 6.3 平衡二叉排序树（AVL树） ###

> 属于 二叉搜索树的一种特殊类型

*  特点

![示意图][format_png 28]

*  具体介绍

![示意图][format_png 29]

### 6.4 红黑树 ###

> 属于 二叉搜索树的一种特殊类型

![示意图][format_png 30]

### 6.5 赫夫曼树 ###

*  简介

![示意图][format_png 31]

*  哈夫曼树算法  
    即，如何找出哈弗曼树。具体算法请看下图

![算法描述][format_png 32]

![示意图][format_png 33]

> 更加详细请看文章：http://www.cnblogs.com/mcgrady/p/3329825.html

*  哈夫曼编码

![示意图][format_png 34]

> 更加详细请看文章：http://blog.csdn.net/lfeng\_coding/article/details/47782141

### 6.6 其他类型（特殊形态） ###

包括：斜树、满二叉树 & 完全二叉树

![示意图][format_png 35]

### 6.7 总结 ###

![示意图][format_png 36]

--------------------

# 7. 总结 #

*  本文主要讲解了数据结构中的二叉树
 *  下面我将继续对 **数据结构**，有兴趣可以继续关注[Carson\_Ho的安卓开发笔记][Carson_Ho]

--------------------

# 请帮顶 / 点赞！因为你的鼓励是我写作的最大动力！ #

[e42c52b9af8d79486a0f3cd0e50df7b7.png]: https://img-blog.csdnimg.cn/img_convert/e42c52b9af8d79486a0f3cd0e50df7b7.png
[format_png]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS1hOGZiMjNmMzVmODEzZWFhLnBuZw?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS03MDdmNjQ1MGFlODQ2NGQ0LnBuZw?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS0wMmI1MmMxNTZmZTU2ZDcyLnBuZw?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS0yYzkyNDZkZThkNTI3NDg1LnBuZw?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS0wMmY1MWUxMWIyYmEwNjU5LnBuZw?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS1jMjY4NzdkMjQ4MTBjMGY4LnBuZw?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS0yYmY4ZDFhYjExYmFmNGI3LnBuZw?x-oss-process=image/format,png
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS1kYjYzZTE0MDhjMWE2MDc2LnBuZw?x-oss-process=image/format,png
[format_png 8]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS00OWY3MDQ5YmRlMzkzNzc1LnBuZw?x-oss-process=image/format,png
[format_png 9]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS1hMjhlZWI4ODg1ODkyZjEwLnBuZw?x-oss-process=image/format,png
[format_png 10]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS1kZjhkNWQ1MWM0OGUxNTUwLnBuZw?x-oss-process=image/format,png
[format_png 11]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS01OTJmZDBmOTU0MTg3NzViLnBuZw?x-oss-process=image/format,png
[format_png 12]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS04NTZlMWFhZGI3MzdjNWM0LnBuZw?x-oss-process=image/format,png
[format_png 13]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS0yNDllMzAxMmUwZWNkNmJhLnBuZw?x-oss-process=image/format,png
[format_png 14]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS0wNGEzZGU4NzMwOWVmZDZhLnBuZw?x-oss-process=image/format,png
[format_png 15]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS0yZDYwNjZlYzczOWJiZmE2LnBuZw?x-oss-process=image/format,png
[format_png 16]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS1jOTU3Mjk3MTU0YmI0OWUzLnBuZw?x-oss-process=image/format,png
[format_png 17]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS01YmRlYzhmZDMzMWQ3MmE5LnBuZw?x-oss-process=image/format,png
[format_png 18]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85NDQzNjUtODlhODA5ZjI2YTRmYTVmZS5wbmc?x-oss-process=image/format,png
[format_png 19]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS0xMWMxMzg0NjhhNDI4NmRiLnBuZw?x-oss-process=image/format,png
[format_png 20]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS01MWI0ODZlNmJmMzllZjFjLnBuZw?x-oss-process=image/format,png
[format_png 21]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS03NmZmOWY1YTk4NTg1NzE1LnBuZw?x-oss-process=image/format,png
[format_png 22]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS1mZDc4NDhhMGE0M2M5M2E4LnBuZw?x-oss-process=image/format,png
[format_png 23]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS05YjVhYmFhODlmYmVmZmQ2LnBuZw?x-oss-process=image/format,png
[format_png 24]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS1lZjAwNzZlYjlhNmYxNjk3LnBuZw?x-oss-process=image/format,png
[format_png 25]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS04ZjE1ZmNjMTU3ODBmOTgzLnBuZw?x-oss-process=image/format,png
[format_png 26]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS0xMzRjMTMyMzVlNjU3ODBjLnBuZw?x-oss-process=image/format,png
[format_png 27]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS1hNmRhOTJhNTI4NjdkM2Y4LnBuZw?x-oss-process=image/format,png
[format_png 28]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS02OTRjNzMyN2U4MTY4ZjQwLnBuZw?x-oss-process=image/format,png
[format_png 29]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS01NzU4OGU3ZWVhMWIwNzNhLnBuZw?x-oss-process=image/format,png
[format_png 30]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS1mZDNmMzI1YzA4N2FkOTAyLnBuZw?x-oss-process=image/format,png
[format_png 31]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS01MjBjYjJkNzI4ZWZhNDExLnBuZw?x-oss-process=image/format,png
[format_png 32]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS01OTZjZTkzNWFlMGM2ZmIzLnBuZw?x-oss-process=image/format,png
[format_png 33]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS1mOTA0OWQyN2QzZTljNTBmLnBuZw?x-oss-process=image/format,png
[format_png 34]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS0yNTg5N2MzZDdiMTQzOGJmLnBuZw?x-oss-process=image/format,png
[format_png 35]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS0xNWRiM2UyZGM4MzYzMTY1LnBuZw?x-oss-process=image/format,png
[format_png 36]: https://imgconvert.csdnimg.cn/aHR0cDovL3VwbG9hZC1pbWFnZXMuamlhbnNodS5pby91cGxvYWRfaW1hZ2VzLzk0NDM2NS05ZTU4N2RkMWJhNTgwNmU2LnBuZw?x-oss-process=image/format,png
[Carson_Ho]: https://blog.csdn.net/carson_ho