Java基础 - 二叉树的概念_java中二叉树是什么

二叉树指的是每个节点最多只能有两个子树的有序树。通常左边的子树被称为“左子树”，右边的子树被称为“右子树”。由此可见，二叉树仍然是树，只是一种特殊的树。

二叉树的每个节点最多只有两棵子树（不存在大于2的节点）。二叉树有左、右之分，不能颠倒。

树和二叉树的两个重要区别如下：

1.树中节点的最大度数没有限制，而二叉树节点的最大度数为2，也就是说，二叉树的节点最大度数为2。

2.无序树的节点无左右之分，而二叉树的节点有左右之分，也就是说二叉树是有序树。

一棵深度为K的二叉树，如果它包含了2^K - 1个节点，就把这棵二叉树称为满二叉树。满二叉树的特点是，每一层上的节点数都是最大节点数，即各层节点数分别为1,2,4,8,16，32，……，2^(K-1) 。满二叉树如下图所示：

一棵有n节点的二叉树，按满二叉树的方式对他进行编号，若树中所有节点和满二叉树1~n编号完全一致，则称该树为完全二叉树。也就是说如果一棵二叉树除最后一层外，其余所有的节点都是满的，并且最后一层或者是满的，或者仅在右边缺少若干连续的节点，则此二叉树就是完全二叉树。如下图所示完全二叉树：

注意：满二叉树是一种特殊的完全二叉树。当完全二叉树最后一层的所有节点都是满的情况下，这棵完全二叉树就变成了满二叉树。

综上所述，二叉树大致有如下几个性质：

（1）、二叉树的第 i 层上的节点至多有 2^(i-1)。 （i > 0）

（2）、深度为 k 的二叉树至多有 2^K   -   1 个节点。满二叉树的每层节点的数量依次为1,2,4,8，……，因此深度为 k 的满二叉树包含的节点数为公比为2的等比数列的前k项总合，即2^K   -   1。

（3）、在任何一棵二叉树中，如果其叶子节点的数量为N0，度为2的字节点数量为N2，则N0 = N2 + 1。这是因为：如果为任意叶子节点增加一个子节点，则原有叶子节点变成非叶子节点，新增节点变成叶子节点，上述等式不变；如果为任意叶子节点增加两个子节点，则原有叶子节点变成度为2的非叶子节点，新增的两个节点变成叶子节点，上述等式不变。

（4）、具有n个节点的完全二叉树的深度为log2（n+1）。

对于一棵具有 n 个节点的完全二叉树的节点按层自左向右编号，则对任意编号为 i （n >= i >= 1）的节点具有如下性质：

（1）当 i =1时，节点 i 是二叉树的根；若 i > 1，则节点的父节点是 i/2。

（2）若 2i <= n，则节点 i 有左孩子，左孩子的编号为 2i，否则，节点无左孩子，并且是叶子节点。

（3）若 2i + 1 <= n，则节点 i 有右孩子，右孩子的编号是 2i+ 1；否则节点无右孩子。

（4）1 ~ n/2 范围的节点都是有孩子的非叶子节点，其余的节点全部都是叶子节点，编号为 n/2 的节点可能只有左子节点，也极有可能有左子节点，也有右子节点。

二叉树的基本操作：

二叉树记录其节点之间的父子关系更加简单，因为二叉树中的每个节点最多只能保存两个子节点。接下来，就是需要为二叉树实现如下基本操作：

（1）初始化：通常是有个构造器，用于创建一个空树，或者指定节点为根节点来创建二叉树。

（2）为指定节点添加子节点。

（3）判断二叉树是否为空。

（4）返回根节点。

（5）返回指定节点（非根节点）的父节点

（6）返回指定节点（非叶子节点）的左子节点。

（7）返回指定节点（非叶子节点）的右子节点。

（8）返回该二叉树的深度。

（9）返回指定节点的位置。

要实现二叉树的这种数据结构，有如下三种选择：

（1）顺序存储：采用数组来记录二叉树的所有节点。

（2）二叉链表存储：每个节点保留一个left、right域，分别指向其左、右子节点。

（3）三叉链表存储：每个节点保留一个left、right、parent域，分别指向其左、右子节点和父节点。