Java-数据结构-二叉树(配图详解)

一、什么是树形结构

① 认识树

之前我们学习的顺序表(ArrayList)和链表(LinkedList)都是线性表，也就都是线性的数据结构，而树则是一种非线性的数据结构，它由有限个结点组成一个具有层次关系的集合，之所以将它叫做"树"是因为其结构"从第一个结点开始，有层序的依次向下延申"，就像是一颗倒挂的树：

因为称为"倒挂的树"，所以其上下两端的结点名字也就可想而知啦：

📕 树的第一个结点被叫做"根节点"，根节点没有前驱结点

📕 树末梢没有后继结点的结点叫做"叶子结点"

又因为树的结构复杂，并不是线性结构，所以我们很难去按照一个指定的顺序或格式去对树进行访问和操作。不过因为"无论从哪个结点看(非叶子节点)，又都能将树的这部分看做一个(以该结点为根节点的子树)"，并且每根子树的根节点只有一个前驱(但可以有多个后继)，所以：

📕 树是递归定义的

（需要注意的是：树形结构中，子树之间是不能有交集的，否则就不能被称作是树形结构。）

形如这种子树与子树之间存在交集的，便不能叫做树，也不是树形结构~

② 树的重要概念

以下内容很重要，请务必认真阅读并理解

⭐ 结点的度：一个结点含有的子树的个数被称作该结点的度，如上图：A的度为2

⭐ 树的度：一棵树中，所有结点度的最大值为树的度，如上图：树的度为2

⭐ 叶子结点或终端结点：度为0的结点被称为叶子结点，如上图：E,D,G,H是叶节点

⭐ 双亲结点或父结点：若一个结点含有子节点，则这个结点称为其子节点的父节点，如上图：B为C的父结点

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

⭐ 根结点：一棵树中，没有双亲结点的结点；如上图A

⭐ 结点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推

⭐ 树的高度或深度：树中结点的最大层次，如上图：树的高度为4

以下概念只需要了解，遇到知道是什么意思即可

非终端结点或分支结点:度不为0的结点; 如上图：C、B、F节点为分支结点

兄弟结点：具有相同父结点的结点互称为兄弟结点;如上图：B、F是兄弟结点

堂兄弟结点：双亲在同一层的结点互为堂兄弟;如上图：C、H是堂兄弟结点

结点的祖先：从根到该结点所经分支上的所有结点;如上图：A是所有结点的祖先

子孙：以某结点为根的子树中任一结点都称为该结点的子孙。如上图：所有结点都是A的子孙

森林：由 m (m >= 0) 棵互不相交的树组成的集合称为森林

二、二叉树

① 认识二叉树

二叉树，顾名思义，就是只有两个分叉的树，也就是结点的一个有限结合，该集合：

📕 有可能为空

📕 也有可能是由一个根节点加上两棵互不相交，分别称为左子树和右子树的二叉树组成

⭐ 图示(二叉树)：

这就是一个比较标准的二叉树啦~并且通过这个图我们也能看出二叉树的基本性质：

📕 最多有两个子结点(度最大为2)：最多为两个子结点，分别为左子结点和右子结点

📕 有序性：左右子结点的位置都是固定的，即便只有一个结点，也仍需要分出是左节点还是右节点。

二叉树可以分为以下几种情况：

② 特殊的二叉树

📚 满二叉树：

📕 每一层的节点数都达到了最大值，即每一层的节点数都为 2^(i-1) ( i 为层号，i >= 1)

📕 深度为 k 的满二叉树有 2^(k-1) 个节点

⭐ 图示：

📚 完全二叉树：

📕 除了最底层外，每一层的节点数都达到最大值，并且最底层的节点从左到右依次排列。

📕 完全二叉树可以通过数组存储，利用节点的索引关系计算父子节点的位置。

需要注意的是，完全二叉树由于排列有序，所以可以比拟成数组，而比拟成数组使用就使得我们可以通过数组的下标来表示节点之间父子关系

当我们将其比拟成数组关系，用数组存储二叉树时，便能够避免通过索引依次查找所造成的开销，既节省了存储空间，又提高了访问效率

⭐ 图示：

📚 斜树：

📕 当二叉树中所有节点都只有左子节点或只有右子节点时，称为斜树，分为左斜树和右斜树。

📕 斜树的深度最大，性能较差，退化为线性结构。

⭐ 图示：

③ 二叉树的性质

以下内容非常重要！请一定要理解并记住！！

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

📕 2.若规定只有根节点的二叉树的深度为1，则深度为k的二叉树的最大结点数为 2^k - 1 [k >= 0]

⭐ 图示(1 & 2)：

📕 对于任意一棵二叉树，如果其结点个数为 n0，度为2的非结点个数为 n2，则有 n2 + 1 = n0

⭐ 图示(3)：

📕 具有n个结点的完全二叉树，其深度 k = log(n + 1) 向上取整[log是以2为底]

📚 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有结点从0开始编号，则对于序号为i的结点有以下性质：

📕 若孩子节点下标为 i ，那么父亲结点为 (i - 1) / 2 [i > 0]

📕 若父亲节点下标为 i ，那么左孩子节点为 2 * i + 1 [2i + 1 < n]，右孩子节点为 2 * i + 2  [2i + 2 < n]

④ 二叉树的存储

之前我们有提到过，二叉树的结构可以是顺序结构，也可以是类似链表的链式结构。

而二叉树的链式存储是通过一个个节点的引用来连接起来的，常用的表示方式有二叉以及三叉：

//二叉表示法
class TreeNode{
    int val;            // 该节点的数据
    TreeNode left;      // 左孩子的引用，代表左子树的根     
    TreeNode right;     // 右孩子的引用，代表右子树的根     
}

//三叉表示法
class TreeNode {
    int val;             // 该节点的数据
    TreeNode left;       // 左孩子的引用，代表左子树的根     
    TreeNode right;      // 右孩子的引用，代表右子树的根
    TreeNode parent;     //当前结点的根节点
}

三、二叉树的基本操作

刚刚我们介绍了二叉树的链式存储是由一个个结点的引用来链接的，接下来我们来看一下深入的看一下二叉树应该如何以链表的形式去实现出来~

① 二叉树的基本框架与创建

对于二叉树中结点的构造，我们就采取上面介绍到的"二叉表示法"：

public class MyBinaryTree {
    static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }

📚 而接下来我们要实现的方法有以下这些：(有兴趣的话也可以复制到自己的电脑上试一下哦)

    // 二叉树的前序遍历
    public void preOrder(TreeNode root) {

    }    
    // 二叉树的中序遍历
    public void inOrder(TreeNode root) {

    }
    // 二叉树的后序遍历
    public void postOrder(TreeNode root) {

    }
    // 获取二叉树中的结点个数(法1)
    public int size(TreeNode root) {

    }
    // 获取二叉树中的结点个数(法2)
    public int size2(TreeNode root) {

    }
    // 获取叶子节点个数(法1)
    public int getLeafNodeSize(TreeNode root) {

    }
    // 获取叶子结点个数(法2)
    public int getLeafNodeSize2(TreeNode root) {

    }
    // 获取第k层结点的个数
    public int getKLevelNodeCount(TreeNode root, int k) {

    }
    // 获取二叉树的高度
    public int TreeHeight(TreeNode root) {

    }
    // 查找值为val的元素是否存在
    public TreeNode find(TreeNode root,char val){

    }
    // 层序遍历
    public void levelOrder(TreeNode root){

    }
    // 判断该二叉树是否为完全二叉树
    public boolean isCompleteTree(TreeNode root){

    }

② 二叉树的简单创建：

在学习以下的那些方法前，我们需要先有一个能够作为示范的二叉树，而在我们目前，什么都没有了解的情况下，直接写构造二叉树的代码，大家或许是会懵懵的，所以我们这边先简单的按照链表的格式，手动创建几个结点，用 left 和 right 连接上，就充当我们的二叉树啦。

📚 代码示例：

    public TreeNode creative() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');

        A.left  = B;
        A.right = C;
        B.left  = D;
        B.right = E;
        C.left  = F;
        C.right = G;

        return A;
    }

这里我们创建的是形如这样的二叉树：

⭐ 图示：

③ 二叉树的前、中、后序遍历

在往常我们所学习的都是线性表，所以对于它们的顺序和打印也都是很容易就一带而过了，但是这次我们学习的"树"可是一种非线性的数据结构，所以想要学习它的方法之前，我们还需要知道什么是"前序遍历"，"中序遍历"，"后序遍历"。

📕 前序遍历：

在上面的学习中，我们已经知道了"树"的结构是一个从根结点开始，向下不断分支的结构：

我们可以看到在这个树形结构中，可以用大致三部分来描述：

"根结点"、"左子树"、"右子树"。

而所谓的前序遍历，就是说，我们需要按照"根节点"、"根的左子树"、"根的右子树"的顺序来进行遍历(后面也是类似的，前中后分别对应根节点访问顺序的前中后)

⭐ 图示：

由图可以知道，在遍历过程中结点都会被指向三次：(叶子结点遇null返回，这里也算被指两次)

📕 被该结点的根节点指向 (1)

📕 被该结点的左子树指回 (2)

📕 被该结点的右子树指回 (3)

而前序遍历就是说遇到根结点，直接就访问并打印，也就是说"被指向的次数 = 1时，被访问"

📖 代码示例：

    public void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

📕 中序遍历：

和前面的是一样的，只是顺序变成了"左子树 -> 根 -> 右子树"，这里也就不过多赘述了。

⭐ 图示：

(中序遍历就变成了该结点 "被指向次数 = 2" 时才进行访问打印~)

📖 代码示例：

    public void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

📕 后序遍历：

仍然是一样的规定，变成" 左子树 -> 右子树 -> 根 "直接看图~

⭐ 图示：

(后序遍历就变成了该结点 "被指向次数 = 3" 时才进行访问打印~)

📖 代码示例：

    public void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }

📌 结果展示：

④ 二叉树的层序遍历

上面我们介绍了三种遍历方式，都是按照树的轨迹与指向去遍历的，那么难道就没有遍历起来简单易懂，并且适合平时调试代码使用的遍历呢？欸你别说，还真有，他就是层序遍历~

因为如果使用层序遍历，我们打印出来的形式就是"从上而下，从左向右"的顺序。

⭐ 图示：

没错，就是这么个易于理解~

那么具体应该如何实现呢？需要借助我们之前学习过的"队列"。

📕 先将根节点放入队列中，随后使用 while(队列非空) 开始循环

📕 在循环中，取出队列顶元素并打印，若该队列顶元素有左/右孩子，则左/右孩子入栈

📕 继续循环，打印队列内剩余结点并添加子结点，直到只剩下所有叶子结点，也就不会再有新节点的加入，循环继续，将所有队列内元素出队并打印~

⭐ 图示：

📖 代码示例：

    public void levelOrder(TreeNode root){
        if(root == null){
            return;
        }
        Deque<TreeNode> queue = new LinkedList<>();
        queue.push(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.removeLast();
            System.out.print(node.val + " ");
            if(node.left != null){
                queue.push(node.left);
            }
            if(node.right != null){
                queue.push(node.right);
            }
        }
        System.out.println();
    }

⑤ 获取结点个数

顾名思义，用于获取二叉树结点个数的方法：

📚 思路提示：

在上面我们学习了遍历二叉树的四种方法，在这里就能用得上啦~对的，想要获得结点个数，也是通过遍历，计数器++的方式即可~

📖 代码示例：

    public int NodeSize = 0;
    // 获取二叉树中的结点个数(法1)
    public int size(TreeNode root) {
        if(root == null){
            return 0;
        }
        size(root.left);
        size(root.right);
        NodeSize++;
        return NodeSize;
    }

但其实并不止有这一种思路，我们不妨换一种思路：

根节点的树，由它的左子树和右子树组成，而左子树和右子树又分别由它们的左右子树组成，既然这么想，那我们是否可以理解为：总结点数 = 左子树结点数 + 右子树节点数 = 左子树的左子树节点数......

⭐ 图示：

📖 代码示例：

    public int size2(TreeNode root) {
        if(root == null){
            return 0;
        }
        int left = size2(root.left);
        int right = size2(root.right);
        return left + right + 1;
    }

⑥ 获取叶子结点数

想要获取叶子结点个数，只要找到二叉树中所有"left == null && right == null"的结点即可，具体该怎么实现呢？我们仍然有两种方法去实现：

📕 遍历二叉树，遇到符合条件的结点，计数器++

📖 代码示例：

    // 获取叶子节点个数(法1)
    public int getLeafNodeSize(TreeNode root) {
        if(root == null){
            return 0;
        }
        getLeafNodeSize(root.left);
        getLeafNodeSize(root.right);
        if(root.left == null && root.right == null){
            leafNodeSize++;
        }
        return leafNodeSize;
    }

📕 同上 size法2 思路，不断的求结点子树的叶子结点个数，最后相加到一起。

📖 代码示例：

    // 获取叶子结点个数(法2)
    public int getLeafNodeSize2(TreeNode root) {
        if(root == null){
            return 0;
        }
        int left = getLeafNodeSize2(root.left);
        int right = getLeafNodeSize2(root.right);
        if(root.left == null && root.right == null){
            return 1;
        }
        return left + right;
    }

⑦ 获取第K层结点数

相信大家对第K层这个词并不陌生，这个就是上面知识点中反复提到过的~

📚 思路提示：

当我们输入 K 的时候，比如我们输入 3，那么我们就要从上往下遍历，当找到第3层的结点时就对应的记录它。这里我们仍然可以使用上两个方法所使用过的"根 = 左子树 + 右子树"的方法~还是非常的万能的。

(每往下找一层，k对应 -- ，当 k == 1 时也就代表走到了要查找的层数，将该结点作为1返回给对应的子树结点就好了~)

⭐ 图示：

📖 代码示例：

    // 获取第k层结点的个数
    public int getKLevelNodeCount(TreeNode root, int k) {
        if(root == null){
            return 0;
        }
        int left = getKLevelNodeCount(root.left,k - 1);
        int right = getKLevelNodeCount(root.right,k - 1);
        if(k == 1){
            return 1;
        }
        return left + right;
    }

⑧ 获取二叉树高度

📚 思路提示：

同样换汤不换药...使用访问子树的方法来实现，但这次的获取二叉树高度就不在是左 + 右了。而是我们分别求左子树和右子树的高度，最后退出方法的时候，return一个左右子树中最高的那一个~

对于求子树的高度，我们知道，我们使用的"递归二叉树子树"方法，一般都是到达树的最低端才开始往回爬，那么我们就可以在每 return 一次时 就对 return 的值 + 1，这样就是逐层 + 1，等到回去的时候，就能够得到对应子树的高度了

⭐ 图示：(为了方便区分，我们这边又临时添加了一个 ' H ' 结点)

📖 代码示例：

    // 获取二叉树的高度
    public int TreeHeight(TreeNode root) {
        if(root == null){
            return 0;
        }
        int leftHeight = TreeHeight(root.left) + 1;
        int rightHeight = TreeHeight(root.right) + 1;
        return Math.max(leftHeight,rightHeight);
    }

加了H结点：

没加H结点：

⑨ 查找value值

📚 思路提示：

想要查找一个指定的value值，其实主要的思路还是通过递归遍历我们的二叉树，只需要我们遇到结点的值等于value时进行return即可~

至于查找的具体思路，仍然还是分别查找结点的左右子树即可~

📖 代码示例：

    // 查找值为val的元素是否存在
    public TreeNode find(TreeNode root,char val){
        if(root == null){
            return null;
        }
        if(root.val == val){
            return root;
        }
        TreeNode left = find(root.left,val);
        if(left != null){
            return left;
        }
        TreeNode right = find(root.right,val);
        if(right != null){
            return right;
        }
        return null;
    }

⑩ 判断是否为完全二叉树

📚 思路提示：

该方法用于判断二叉树是否为完全二叉树，想要实现这个方法，其实使用的思路和上面讲到的第四种遍历方式 ==》层序遍历，还是比较接近的~

因为层序遍历需要我们按照从上至下，从左至右的顺序遍历，而同样的，完全二叉树的要求是如果给结点标号，那么从上至下，从左至右的标号时，中间不应有中断的号~这种排列顺序正好与我们的顺序遍历顺序是相同的~

还记得层序遍历的方法嘛？如果忘记了，不妨回过头再去看看哦~(正所谓读书百遍，其义自见~)

层序遍历时，我们通过将一个个不为null的结点存入队列，并且每次循环都将队头的结点出队并打印其值，这样做能够做到(同一层结点间，中间有null相隔，也仍能打印后续结点)。

而现在我们要做的是"判断是否为完全二叉树"，和他做的恰恰相反，它保证了"中间有null也能遍历"，那我们就照着它反着来即可，也就是将"判断入队列结点是否为null"这一步给删掉即可~

这样如果队列中最后剩余的都是"null"就代表所有结点均被打印，这是完全二叉树，而如果最后队列中有结点存在，则证明被null阻断了，便不是完全二叉树~

⭐ 图示：

📖 代码示例：

    // 判断该二叉树是否为完全二叉树
    public boolean isCompleteTree(TreeNode root){
        if(root == null) {
            return true;
        }
        Deque<TreeNode> queue = new LinkedList<>();
        queue.push(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.removeLast();
            if(cur == null){
                break;
            }
            queue.push(cur.left);
            queue.push(cur.right);
        }
        TreeNode node = queue.removeLast();
        while(!queue.isEmpty()){
            if(node != null){
                return false;
            }
            node = queue.removeLast();
        }
        return true;
    }

完整代码：

📖 MyBinaryTree.java：

import java.util.*;

public class MyBinaryTree {
    static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }

    public int nodeSize = 0;
    public int leafNodeSize = 0;

    public TreeNode creative() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        //TreeNode H = new TreeNode('H');

        A.left  = B;
        A.right = C;
        B.left  = D;
        B.right = E;
        C.left  = F;
        C.right = G;
        //E.left = H;

        return A;
    }
    // 二叉树的前序遍历
    public void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }
    // 二叉树的中序遍历
    public void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }
    // 二叉树的后序遍历
    public void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }
    // 获取二叉树中的结点个数(法1)
    public int size(TreeNode root) {
        if (root == null) {
            return 0;
        }
        nodeSize++;
        size(root.left);
        size(root.right);
        return nodeSize;
    }
    // 获取二叉树中的结点个数(法2)
    public int size2(TreeNode root) {
        if(root == null){
            return 0;
        }
        int left = size2(root.left);
        int right = size2(root.right);
        return left + right + 1;
    }
    // 获取叶子节点个数(法1)
    public int getLeafNodeSize(TreeNode root) {
        if(root == null){
            return 0;
        }
        getLeafNodeSize(root.left);
        getLeafNodeSize(root.right);
        if(root.left == null && root.right == null){
            leafNodeSize++;
        }
        return leafNodeSize;
    }
    // 获取叶子结点个数(法2)
    public int getLeafNodeSize2(TreeNode root) {
        if(root == null){
            return 0;
        }
        int left = getLeafNodeSize2(root.left);
        int right = getLeafNodeSize2(root.right);
        if(root.left == null && root.right == null){
            return 1;
        }
        return left + right;
    }
    // 获取第k层结点的个数
    public int getKLevelNodeCount(TreeNode root, int k) {
        if(root == null){
            return 0;
        }
        int left = getKLevelNodeCount(root.left,k - 1);
        int right = getKLevelNodeCount(root.right,k - 1);
        if(k == 1){
            return 1;
        }
        return left + right;
    }
    // 获取二叉树的高度
    public int TreeHeight(TreeNode root) {
        if(root == null){
            return 0;
        }
        int leftHeight = TreeHeight(root.left) + 1;
        int rightHeight = TreeHeight(root.right) + 1;
        return Math.max(leftHeight,rightHeight);
    }
    // 查找值为val的元素是否存在
    public TreeNode find(TreeNode root,char val){
        if(root == null){
            return null;
        }
        if(root.val == val){
            return root;
        }
        TreeNode left = find(root.left,val);
        if(left != null){
            return left;
        }
        TreeNode right = find(root.right,val);
        if(right != null){
            return right;
        }
        return null;
    }
    // 层序遍历
    public void levelOrder(TreeNode root){
        if(root == null){
            return;
        }
        Deque<TreeNode> queue = new LinkedList<>();
        queue.push(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.removeLast();
            System.out.print(node.val + " ");
            if(node.left != null){
                queue.push(node.left);
            }
            if(node.right != null){
                queue.push(node.right);
            }
        }
        System.out.println();
    }
    // 判断该二叉树是否为完全二叉树
    public boolean isCompleteTree(TreeNode root){
        if(root == null) {
            return true;
        }
        Deque<TreeNode> queue = new LinkedList<>();
        queue.push(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.removeLast();
            if(cur == null){
                break;
            }
            queue.push(cur.left);
            queue.push(cur.right);
        }
        TreeNode node = queue.removeLast();
        while(!queue.isEmpty()){
            if(node != null){
                return false;
            }
            node = queue.removeLast();
        }
        return true;
    }
}

那么这次关于二叉树的知识，就为大家分享到这里啦，作者能力有限，如果有讲得不清晰或者不正确的地方，还请大家在评论区多多指出，我也会虚心学习的！那我们下次再见哦