JAVA 二叉树超详解（1）

痛定思痛。 2023-10-16 14:06 4阅读 0赞

## 树形结构 ##

### 概念 ###

树是一种非线性的数据结构，它是由n(n>=0)个有限结点组成的一个具有层次关系的集合。**把它叫做树是因为它看起来像一棵倒挂的树，也就是说它根朝上，而叶朝下的**，具有以下的特点：

> 1.有一个特殊的结点，称为根结点，根节点没有前驱节点
> 
> 2.除根节点外，其余节点被分成M(M>0)个互不相交的集合T1，T2.....Tm,其中每一个集合Ti又是一棵与树类似的子树。每棵子树的根节点有且只有一个前驱，可以有0或者多个后继(**一棵树是由若干不相交的子树构成**)
> 
> 3.树是递归定义的

**注意：树形结构中，子树之间不能有交集，否则就不是树形结构**

> 判断树与非树的重要考察点：
> 
> **1.子树是不想交的**
> 
> **2.除了跟节点外，每个节点有且仅有一个父节点**
> 
> **3.一棵N个节点的树有N-1条边**

### 关键词 ###

以下图为例：

![eb71637528ef4987b2fa7434f37cd809.jpeg][]

**节点的度：**一个结点含有子树的个数称为结点的度； 如上：A的度为6

**树的度：**一棵树中，所有结点的度的最大值称为树的度；如上：树的度为6

**叶子节点或终端节点：**度为零的结点称为叶节点；如上：B，C，H，I，P等为叶子节点

**孩子结点或子节点**：一个节点含有的子树的根节点称为该结点的子节点；如：B是A的子节点

**根结点：**一棵树中，没有双亲结点的结点，如上：A为根结点

**树的高度或深度：**树中结点的最大层次；如上：树的高度为4.

### 树的表示形式 ###

> 树结构相对于线性表就比较复杂了，要存储表示起来就比较麻烦了，实际中树有很多表示方式，如：**双亲表示法，孩子表示法，孩子双亲表示法等等。**我们就来简单了解一下最常用的孩子兄弟表示法（通过一个结点的一个孩子去找它其它的子节点（这个孩子的兄弟））。

class Node {
        int value;    //树中存储的数据
        Node firstChild;    //第一个孩子的引用
        Node nextBrother;    //下一个兄弟的引用
    }

简图：

![3cf8fc5011e74ff8957f0d08ed0d44ae.png][]

### 树的应用 ###

文件系统管理（目录和文件）

![cd269beb007b4a80b1fed9580cc6b6f4.png][]

## 二叉树 ##

### 概念 ###

一棵二叉树是结点的一个有限集合，该集合：

> 1.或者为空
> 
> 2.或者是由**一个根节点**加上两棵分别被称为**左子树和右子树**的二叉树组成。

![5eb69dbf6f4d45a2a701d6d66d55ce7d.png][]

其中：A为根节点，B及其以下的部分为根结点的左子树，C及其以下的部分为根节点的右子树。

> 从上图可以看出：
> 
> 1.二叉树不存在度大于2的结点
> 
> 2.二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

注意：对于任意的二叉树都是由以下几种情况复合而成的：

![b0ba4ac4de2e40828444917cfd75f765.png][]

###  ###

### 两种特殊的二叉树 ###

> **1.满二叉树：**一棵二叉树，**如果每层的节点数都达到最大值，则这棵二叉树就是满二叉树。**也就是说，**如果一棵二叉树的层数为k，且节点总数2^K-1,那么他就是满二叉树。**
> 
> 2**.完全二叉树**：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引来的。对于深度为K 的，有N个结点的二叉树，满二叉树中编号从0至N-1的结点--对应时称之为完全二叉树，**也就是从左到右，从上到下依次存放结点的二叉树（其中一个为空就不是）**。**要注意满二叉树是一种特殊的完全二叉树**。

![7d38e82fbcb741109a25c865a8ee8358.png][]

### 二叉树的性质（重要） ###

**1.若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1)（i>0）个结点** 。

2.**若规定只有根节点的二叉树深度为1，则深度为K的二叉树所含最多节点数为**（就是满二叉树）：2^K - 1(K>=0)

**3.对于任何一棵二叉树，如果其叶节点个数为n0，度为二的结点个数为n2,则有n0 = n2 + 1**

推理如下：![f1099879c4a04f1ebd93d477b484ce48.jpeg][]

**4.具有N个结点的完全二叉树的深度为log(n+1)向上取整,底数为2（可以借助第二点反推）**。

5.对于具有**n个结点的完全二叉树**，如果按照**从上至下从左至右的顺序对所有节点从0开始编号**，那么对**序号为i的节点有**：

> (1).若i>0,双亲序号：(i-1)/2;i = 0,i为根结点编号，无双亲结点
> 
> (2).若2i+1<n,左孩子序号：2i+1,否则无左孩子
> 
> (3).若2i+2<n,右孩子序号：2i+2，否则无右孩子

### 二叉树的存储 ###

**二叉树的存储结构分为：顺序存储和类似于链表的链式存储。**

**二叉树的链式存储是通过一个一个的结点引用起来的，常见的引用方式有二叉和三叉表示方式：**

//孩子表示法
    class Node {
        int val;    //数据域
        Node left;    //左孩子的引用，常常代表左孩子为根的整棵左子树
        Node right;    //右孩子的引用，常常代表右孩子为根的整棵左子树
    }
    
    //孩子双亲表示法
    class Node{
        int val;    //数据域
        Node left;    //左孩子的引用，常常代表左孩子为根的整棵左子树
        Node right;    //右孩子的引用，常常代表右孩子为根的整棵左子树
        Node parent;    //当前节点的根结点
    }

![9b556785b6fe495888ad326d0fae068c.png][]

### 二叉树的基本操作 ###

#### 说明 ####

> 在学习二叉树基本操作之前，需要创建一棵二叉树，然后才能学习其相关的基本操作。此处先创建一个简单的二叉树：

public class BinaryTree {
        public static class BTNode {
            BTNode left;
            BTNode right;
            int value;
            
            BTNode(int value) {
                this.value = value;
            }
        }
        
        private BTNode root;
        
        public void createBinaryTree() {
            BTNode node1 = new BTNode(1);
            BTNode node2 = new BTNode(2);
            BTNode node3 = new BTNode(3);
            BTNode node4 = new BTNode(4);
            BTNode node5 = new BTNode(5);
            BTNode node6 = new BTNode(6);
            
            root = node1;
            node1.left = node2;
            node2.left = node3;
            node1.right = node4;
            node4.left = node5;
            node5.right = node6;
        }
    }

注意：上述代码并不是创建二叉树的真正方式，真正创建二叉树的方式后续再讲。

#### 二叉树的遍历 ####

1.前中后序遍历

> 学习二叉树结构，最简单的方式就是遍历。**所谓遍历就是指沿着某条路线，依次对树中每个结点均做一次且仅做一次访问。访问节点所做的操作依赖于具体的应用问题（比如：打印节点内容，节点内容+1）。遍历是二叉树上的最重要的操作之一，是二叉树上进行其它运算的基础。**

![85406ead23e946a4907733081679b136.png][]

> 在遍历二叉树时，如果没有某种规定，每一个人都煮自家的粥，按照各个不同的遍历方法，难免会有些混乱，**如果按照某种规则进行约定，则每一个人遍历二叉树的方法是相同的**。
> 
> 如果规定N为根结点，L代表根结点的左子树，R代表根结点的右子树，则根据结点的先后次序有以下的遍历方式：
> 
> 1.NLR：前序遍历--先访问根节点--根的左子树--根的右子树（先遇到哪个就先访问哪个）
> 
> 2.LNR：中序遍历--先访问根的左子树--根节点--根的右子树（一直向左走，直到左边为空，然后回溯访问结点）
> 
> 3.LRN：后序遍历--先访问根的左子树--根的右子树--根结点（将一个结点的左右子树走完，再访问结点）

代码（主要利用递归的方式）：

//前序遍历
    void preOrder(Noot root) {
        //访问到并进行对节点内容打印的操作
        System.out.print(root.value);
        //先对左子树进行递归
        preOrder(root.left);
        //后对右子树进行递归
        preOrder(root.right);
    }
    
    //中序遍历
    void inOrder(Noot root) {
         //先对左子树进行递归
        preOrder(root.left);
        //访问到并进行对节点内容打印的操作
        System.out.print(root.value);
        //后对右子树进行递归
        preOrder(root.right);
    }
    
    //后序遍历
    void postOrder(Noot root) {
         //先对左子树进行递归
        preOrder(root.left);
        //后对右子树进行递归
        preOrder(root.right);
        //访问到并进行对节点内容打印的操作
        System.out.print(root.value);
    }

参考示例：

![77bdc0bb4ba549b3b4a340fecabd280f.png][]

> 1.前序遍历：123456
> 
> 2.中序遍历：321546
> 
> 3.后序遍历：325641

2.**层序遍历**

**定义：**除了先序遍历，中序遍历，后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在的层数为1，层序遍历就是从所在的二叉树的根节点出发，进行从上到下，从左到右的遍历。

![ef7da27fed1a4ef585dc5cbffc72c6a7.png][]

[eb71637528ef4987b2fa7434f37cd809.jpeg]: https://img-blog.csdnimg.cn/eb71637528ef4987b2fa7434f37cd809.jpeg
[3cf8fc5011e74ff8957f0d08ed0d44ae.png]: https://img-blog.csdnimg.cn/3cf8fc5011e74ff8957f0d08ed0d44ae.png
[cd269beb007b4a80b1fed9580cc6b6f4.png]: https://img-blog.csdnimg.cn/cd269beb007b4a80b1fed9580cc6b6f4.png
[5eb69dbf6f4d45a2a701d6d66d55ce7d.png]: https://img-blog.csdnimg.cn/5eb69dbf6f4d45a2a701d6d66d55ce7d.png
[b0ba4ac4de2e40828444917cfd75f765.png]: https://img-blog.csdnimg.cn/b0ba4ac4de2e40828444917cfd75f765.png
[7d38e82fbcb741109a25c865a8ee8358.png]: https://img-blog.csdnimg.cn/7d38e82fbcb741109a25c865a8ee8358.png
[f1099879c4a04f1ebd93d477b484ce48.jpeg]: https://img-blog.csdnimg.cn/f1099879c4a04f1ebd93d477b484ce48.jpeg
[9b556785b6fe495888ad326d0fae068c.png]: https://img-blog.csdnimg.cn/9b556785b6fe495888ad326d0fae068c.png
[85406ead23e946a4907733081679b136.png]: https://img-blog.csdnimg.cn/85406ead23e946a4907733081679b136.png
[77bdc0bb4ba549b3b4a340fecabd280f.png]: https://img-blog.csdnimg.cn/77bdc0bb4ba549b3b4a340fecabd280f.png
[ef7da27fed1a4ef585dc5cbffc72c6a7.png]: https://img-blog.csdnimg.cn/ef7da27fed1a4ef585dc5cbffc72c6a7.png