Java二叉树详解

标签：Node 结点遍历 Java 详解二叉树 root 节点

当你看到一棵茂盛的大树时，你是否曾想过这样的问题：它是如何生长起来的？落叶归根，数百年来，不断地生长与死亡。其实，每个程序员也可以成为一棵大树的缔造者。而 Java 的二叉树，就像互联网上的知识一样，通过它的枝干和叶子，能够让我们更加高效地搜索、插入和删除节点。虽然二叉树算法并不简单，但只要掌握了它的基本原理，便能从中得到无限的可能和成长。接下来，让我们一起探索 Java 二叉树的神秘之处，成为一名更加出色的程序员。

Java二叉树详解_子树

看到这棵树，大家的第一反应是啥？反正我的反应是：我去，这不就是程序员的梦中情树嘛，把这棵树放门口，这编程实力不得嘎嘎提升？好了，玩笑开到这儿，首先我们想了解二叉树，我们得知道树是什么？

一、什么是树？

那树是什么呢？通俗点来说，树其实就是链表或顺序表，但是这篇博客不说顺序表实现的二叉树，因为太简单了，我们来说用链表实现的。树其实就是一个节点里面存了两种域，一种是指针域，另外一种是值域，指针域是指向另外一个节点，值域存值，看图就明白了，如图所示：

Java二叉树详解_二叉树_02

怎么样，是不是很简单捏，指针域可以指向一个节点，也可以是两个或者多个，比如说这种：

Java二叉树详解_二叉树_03

如图是指向两个节点的，这种就是我们今天要说的二叉树，但是二叉树又分两类，一种是完全二叉树，一种是普通二叉树，有的同志可能会说了，不是还有个满二叉树吗，其实满二叉树就是特殊的完全二叉树，因为普通二叉树没什么需要将的点，所以本篇文章就只讲完全二叉树和满二叉树。

二、树的基本概念

结点的度：一个结点含有子树的个数称为该结点的度
树的度：一棵树中，所有结点度的最大值称为树的度
叶子结点或终端结点：度为0的结点称为叶结点
双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点
孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点
根结点：一棵树中，没有双亲结点的结点
结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推
树的高度或深度：树中结点的最大层次

树的以下概念只需了解，在看书时只要知道是什么意思即可：

非终端结点或分支结点：度不为0的结点
兄弟结点：具有相同父结点的结点互称为兄弟结点
堂兄弟结点：双亲在同一层的结点互为堂兄弟
结点的祖先：从根到该结点所经分支上的所有结点
子孙：以某结点为根的子树中任一结点都称为该结点的子孙
森林：由m（m>=0）棵互不相交的树组成的集合称为森林

三、两种特殊的二叉树

满二叉树：一棵二叉树，如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树。也就是说，如果一棵二叉树的层数为K，且结点总数是 2^k - 1 ，则它就是满二叉树。

完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。

2.2、二叉树的性质

若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有 (i>0)个结点
若规定只有根结点的二叉树的深度为1，则深度为K的二叉树的最大结点数是 (k>=0)
对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0＝n2＋1
具有n个结点的完全二叉树的深度k为上取整
对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i的结点有：

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

这里性质3有点难理解，我们来列个方程就知道啦，假设总结点是N，度为0，1，2的节点分别是n0，n1，n2，那可得：

N = n0 + n1 + n2;
又因为节点和边的关系是有N个节点，就有N - 1条边;
又因为一个n1节点能创造1条边，一个n2节点能创造两条边，n0不创造边
所以可得方程：
N = n0 + n1 + n2;
N - 1 = n1 + 2 * n2;
解得：n0 = n2 + 1;

其他的兄弟们应该都没啥大问题，好好理解一下就行了。

四、二叉树的创建

我们想知道二叉树是怎么创建的，就先要知道二叉树的表示方法，树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，实际中树有很多种表示方式，如：双亲表示法，孩子表示法、孩子双亲表示法、孩子兄弟表示法等等。下面是链式二叉树的创建：

// 孩子表示法
class Node {
    int val; // 数据域
    Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树
    Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
}
// 孩子双亲表示法
class Node {
    int val; // 数据域
    Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树
    Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
    Node parent; // 当前节点的根节点
}
// 孩子兄弟表示法
class Node {
    int value; // 树中存储的数据
    Node firstChild; // 第一个孩子引用
    Node nextBrother; // 下一个兄弟引用
}

我们主要讲第一种，孩子表示法，下面是是代码实现：

class Node {
    int value;
    Node left;
    Node right;
    public Node(int value) {
        this.value = value;
        left = null;
        right = null;
    }
}
public class BinaryTree {
    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        node1.left = node2;
        node2.left = node3;
        node1.right = node4;
        node4.left = node5;
        node5.right = node6;
    }
}

上面代码的main函数里面只是我们自己创建的一个伪二叉树，实际上不是这么创建的，有一百个节点呢？这不得麻烦亖？后续的文章我会教大家怎么通过中序和后序或者前序和中序遍历来创建二叉树，所以大家给个免费的三连+关注吧（啊不是） Java二叉树详解_结点_04 ，既然说到了遍历，那这个可是二叉树的重中之重，很有必要给兄弟们讲一下。

五、二叉树的遍历

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

5.1、前序遍历

前序遍历又叫先序遍历，首先我们得清楚三个概念，那就是二叉树的根节点、左节点、右节点的简洁表示字母，分别是N、L、R，所以前序遍历顾名思义，就是把根节点放在前面，NLR，左和右顺序肯定不变，从左到右嘛。这个先序遍历的意思就是先访问根节点，再访问根的左子树，再最后访问根的右子树。

5.2、中序遍历

和上文的前序遍历一样，只不过根是在中间，就是LNR，意思就是先访问根的左子树，再访问根节点，最后访问根的右子树。

5.3、后续遍历

这个应该就不用多说了吧，意思就是先访问根的左子树，再访问右子树，最后访问根节点。

Java二叉树详解_结点_05

例如上面这张图，它的前中后序分别是：

前序遍历结果：1 2 3 4 5 6
中序遍历结果：3 2 1 5 4 6
后序遍历结果：3 2 5 6 4 1

5.4、层序遍历

除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。说白了就是一层一层的访问，每层的访问书顺序是从左到右访问，例如上面这张图，它的层序遍历就是：1 2 4 3 5 6

六、二叉树的相关操作

写二叉树相关的这些操作，首先头脑要打清楚，二叉树相关操作一般都用递归写，每个二叉树不管有多少个节点，都可以看作左树+右树，这个想明白了，那这些操作就很简单。

6.1、获取树中节点的个数

根据我说的，左树+右树，先想好递归的出口，是不是碰到null就说明这条路线上的节点已经走完了呀，那就是返回0，其他的情况返回1，然后还要+上这颗子树的节点，那代码就写出来了，代码实现如下：

public int size(TreeNode root) {
    if (root == null) {
        return 0;
    }
    // 返回左树的节点个数+右树的节点个数+上本身
    return size(root.left) + size(root.right) + 1;
}

6.2、获取叶子节点的个数

首先想好递归出口，和上面一样，只要走到null，这条路线就是走完了，再判断要算什么，是不是要算叶子节点呢？所以只有为叶子的时候，才+上1，代码实现如下：

public int getLeafNodeCount(TreeNode root) {
    if (root == null) {
        return 0;
    }
    // 判断是叶子节点才+1
    if (root.left == null && root.right == null) {
        return getLeafNodeCount(root.left) + getLeafNodeCount(root.right) + 1;
    }
    return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
}

6.3、获取二叉树的高度

比较左树和右树哪个更高，取最大值，再+上1，1代表本身节点，代码实现如下：

public int getHeight(TreeNode root) {
    if (root == null) {
        return 0;
    }
    return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
}

6.4、寻找元素

递归出口：找到了，或者找完了

public TreeNode find(TreeNode root, int val) {
    // 为空证明这边找完了，没找到，返回空
    if (root == null) {
        return null;
    }
    // 如果找到了就返回
    if (root.val == val) {
        return root;
    }
    TreeNode leftret = find(root.left, val);
    // 如果左边为空，表示左边没找到，去右边找，找到了返回右边，不然就返回空，反之也是如此
    if (leftret == null) {
        return find(root.right, val);
    }
    else {
        return leftret;
    }
}

七、总结

掌握 Java 二叉树，对于 Java 程序员而言是一项必备的技能。在本篇博客中，我们深入讲解了 Java 二叉树的基本原理及其应用，包括二叉树节点定义、搜索和删除等操作以及二叉树的遍历。通过学习，我们不仅深入了解了二叉树的基本原理，更重要的是我们掌握了如何通过二叉树算法来解决实际的编程问题。让我们始终保持对编程语言的热爱，在未来的职业生涯中持续学习提升，用优秀的代码闪耀程序开发的世界。

八、结语

Java 二叉树算法的学习不仅仅是要掌握一些语法和知识，更是需要一份自我勉励和不断努力的精神。在学习二叉树时，我们需要不断尝试并写下自己的代码，不断地调试并优化代码，甚至要面对自己的挫败和失败。但正是这种不断努力，才能让我们不断提升自己，在未来的实际开发和面试中取得更好的成果。让我们保持一颗求知的心，并肩负起我们作为程序员的责任，将 Java 二叉树的优秀思想延续和发扬光大。无论遇到多么艰难的困难和挑战，我们都要持之以恒，坚持到底，相信你一定会成为一名优秀的 Java 开发工程师。

Java二叉树详解_结点_06

标签：Node,结点,遍历,Java,详解,二叉树,root,节点
From： https://blog.51cto.com/bitzmbdp/6318739