JavaDS —— 二叉树

树的基本概念

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

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

在这里插入图片描述

结点的度：一个结点包含的子树的个数称为结点的度。例如上图：A的度为 6，D的度为1，B的度为0

树的度：一颗树中，所有结点度的最大值称为树的度。例如上图：A 的度为6是所有结点的度的最大值，所以树的度为 6

叶子结点或者终端结点：度为0的结点称为叶子结点或者终端结点。例如上图： B,C,H,I,P,Q,K,L,M,N是叶子结点

双亲结点或者父结点：若一个结点包含子节点，则这个结点就是子节点的双亲结点。例如上图： A是B的双亲结点，D是H的双亲结点

孩子结点或子结点：一个结点所在的子树的根节点称为该结点的子节点。例如：B是A孩子结点，P和Q是J的孩子结点

根结点：一个树中，没有双亲结点的结点。 A是整棵树的根结点，F是树（F，K,L,M构成的树）的根节点。

结点的层次：从根结点开始定义，根为第一层，根的子结点为第二层，以此类推

树的高度或深度：树中结点的最大层次，根结点定义为1，例如上图所示整棵树的高度为4

非终端结点或分支结点：度不为0的结点，例如：D,E,F,G等等结点是分支结点

兄弟结点：具有相同的双亲结点的结点互称为兴地结点。例如B,C,D,E,F,G的双亲结点都是A，那么它们都是对方的兴地结点

堂兄弟结点：双亲在同一层的结点互为堂兄弟。例如上图：H，I，K互为堂兄弟结点

结点的祖先：从根到该系欸但所经分支的所有结点。 A是所有结点的祖先。

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

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

树的表示形式

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，实际中树有很多种表示方式，如：双亲表示法，孩子表示法、孩子双亲表示法、孩子兄弟表示法等等。这里就简单介绍其中最常用的孩子兄弟表示法。

在这里插入图片描述

二叉树的概念与性质

二叉树中所有的结点的度都小于等于2，并且可以分为左子树和右子树，是一个有序树
在这里插入图片描述

二叉树的几种形态：
在这里插入图片描述

满二叉树

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

完全二叉树

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。通俗一点来说，完全二叉树就是只有最后一层可能不是满的，并且最后一层的结点排列是从左到右依次排列的。 要注意的是满二叉树是一种特殊的完全二叉树。
在这里插入图片描述

性质

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

证明：下面是一颗满二叉树。
在这里插入图片描述
第一层有 1 个结点
第二层有 2 个结点
第三层有 4 个结点
。。。。。。

可以看出这是一个等比数列，使用等比数列求某一项的公式可得：第 i 层的结点数最多为 2 ^ ( i - 1 )

2.若规定只有根结点的二叉树的深度为1，则深度为 k 的二叉树结点总数最多为 2 ^ k - 1 (k > 0)

证明：
还是拿上面的满二叉树举例，现在是求深度为 k 的最多的结点总数是多少？这里很简单直接使用等比数列求和公式，2 ^ 0 + 2 ^ 1 + 2 ^ 2 + 2 ^ 3 + … = 2 ^ 0 * (1 - 2 ^ k) / (1 - 2 ) = 2 ^ k - 1

3.对于任意一颗二叉树，如果其叶子结点个数为 n0,度为2的分支结点个数为 n2 ，则 n0 = n2 + 1

证明：
二叉树的结点总数等于度为 0 的叶子节点加度为 1 的根节点加度为 2 的分支节点，设节点总数为 N，度为 0 的叶子节点总数为 n0 , 度为1的根节点的数量为 n1 ，度为2的分支节点数量为 n2 , N = n0 + n1 + n2
在二叉树中 N 个节点就会产生 N - 1 条边，因为每一个节点上面都会有一条边连接着，除了根节点，所以要减一。
除了上面这种即使边的方式，还能这样理解，度为1 的节点会向下延伸一条边，度为 2 的节点会向下延伸两条条边，度为 0 的节点不会向下延伸，则边的总数还能等于 1 * n1 + 2 * n2

联立方程：
N = n0 + n1 + n2
边的总数等于 N - 1
边的总数还能等于 1 * n1 + 2 * n2

即 n0 + n1 + n2 - 1 = 1 * n1 + 2 * n2
n0 = n2 + 1

具有n 个结点的完全二叉树的深度 k 为 log( n + 1 ) 【以2为底的对数】结果向上取整

证明：
由性质二可知深度为 k 的二叉树结点总数 n 最多为 2 ^ k - 1 (k > 0) ，则取对数可得 k = log( n + 1 ) 结果向上取整，因为完全二叉树最后一层可能不是满的，所以你得到的结果可能有小数部分，这时候最后一层也是算的，所以结果要向上取整。

性质5：
对于具有 n 个结点的完全二叉树，如果按照从上到下从左到右的顺序对所有的结点从0开始编号，则对于序号为 i 的结点有：
若 i = 0，i 为根节点的编号，没有双亲结点
若 i > 0 , 双亲结点的序号为（i - 1) / 2
若 2 * i + 1 < n , 左孩子序号为 2 * 1 + 1，否则没有左孩子
若 2 * i + 2 < n , 右孩子序号为 2 * 1 + 2，否则没有右孩子

二叉树的实现

创建二叉树

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

创建方法一：这个方法可以实现自己想要的二叉树，而且写起来比较方便。

    //创建二叉树public TreeNode creatTree() {TreeNode root = 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');root.left = B;root.right = C;B.left = D;B.right = E;C.left = F;return root;}

创建方法二：根据前序遍历中序遍历或者后序遍历的结果进行创建，但是有一个前提就是必须提供所有的空树和所有的结点的序列。

下面的创建方法是基于前序遍历的字符串使用的。

    public static int i;public TreeNode creatTree(String str){TreeNode root = null;if(str.charAt(i) == '#') {i++;return null;}root = new TreeNode(str.charAt(i));i++;root.left = creatTree(str);root.right = creatTree(str);return root;}

这里使用了一个外部的变量 i ，这个变量是用来表示此时指向字符串的哪个字符

由于这是一个静态的变量所有所有使用Tree实例化的对象都应该只有一份的 i ，这就意味着如果创建多个树的时候需要重置一下 i 的数值。

前序遍历

前序遍历又可以称为先序遍历，遍历方式是先访问根节点的数值，然后遍历左子树，最后遍历右子树。

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

迭代的方法在二叉树 OJ （一）的习题文章中，大家可在文末点开链接阅读

中序遍历

中序遍历是先遍历左子树，然后访问根节点的数值，最后遍历右子树

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

迭代的方法在二叉树OJ（一）的习题文章中，大家可以点开链接阅读

后序遍历

后序遍历是先遍历左子树，然后遍历右子树，最后访问根节点的数值。

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

迭代的方法在二叉树OJ（一）的习题文章中，大家可以点开链接阅读

如何从遍历序列推导二叉树？

先序遍历能确定根节点，后序遍历也能确定根结点，中序遍历在得知根节点的前提下能推导根节点左右子树序列，所以要想从遍历序列推导出二叉树，就一定要知道中序遍历序列，还要知道先序遍历或者后序遍历序列其中之一即可。

已知某二叉树的前序遍历序列为ABDEC，中序遍历序列为BDEAC，那么它的后序遍历序列是什么？

首先根据前序序列，我们知道根节点为 A，然后根据中序序列找到 A，发现A的左边为 BDE，右边为 C，即获得A的右子树为C，如下图：
在这里插入图片描述
由于前序遍历是根左右，那么 B 就是 A 的左孩子，也是左子树的根节点，然后回到中序遍历序列找到结点 B ，发现结点 B 左边没有其他结点所以 B 的左子树为空，右子树为 DE：

继续之前的步骤，从先序遍历得到 D 是根节点，再看中序遍历得到 E 在 B 的右边，所以 E 是 B 的右子树：
在这里插入图片描述
然后根据还原的二叉树写出后序遍历的序列：EDBCA

已知某二叉树的后序遍历序列为EDBCA，中序遍历序列为BDEAC，那么它的前序遍历序列是什么？

根据后序遍历的特点，最后一个结点为根节点即为 A，然后到中序遍历中找到 A，A 的左子树为 BDE，右子树为 C ：
在这里插入图片描述

然后后序遍历的倒数第二个结点为 C ，回到中序遍历可得 C 的左子树右子树都为空，继续，后序遍历倒数第三个结点为 B，根据中序遍历序列可得 B 的左子树为空，右子树为 DE：
在这里插入图片描述
重复上诉步骤，最后可得：

则前序遍历的结果为 ABDEC

这里不演示代码，代码放在二叉树OJ（一）文章中，大家可以打开链接自行查阅。

层序遍历

层序遍历是从上到下从左到右依次遍历每一层的结点。

这里我们需要队列这个数据结构来存放每一个结点，通过出队打印数值，然后入队这个出了队的结点的左右孩子结点(不为空的结点进行入队)，之后就是一直重复出队、入队、出队、入队等等这些操作，通过循环实现，直到所有结点遍历完成。

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

获取结点总数

使用递归先遍历左子树再遍历右子树，当结点不为空的时候 nodes++

    public int nodes;public void size(TreeNode root) {if(root == null) {return;}nodes++;size(root.left);size(root.right);}

除了可以使用遍历思路，还可以采用子问题思路，就是将问题变成结点总数等于左子树的结点总数加右子树的结点总数加根节点。

    //计算结点个数//左子树节点数加右子树节点数加根节点public int size(TreeNode root) {if(root == null) {return 0;}return size(root.left) + size(root.right) + 1;}

获取叶子结点总数

可以采用遍历思路，遍历所有结点，将不为空的结点使用计数器++即可

    public int leafNodes;public void getLeafNodes(TreeNode root) {if(root == null) {return;}if(root.left == null && root.right == null) {leafNodes++;}getLeafNodes(root.left);getLeafNodes(root.right);}

也可以采用子问题，叶子结点数目等于左子树的叶子加右子树的叶子。

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

获取树的高度或深度

采用子问题思路，树的高度是左右子树的最大高度，然后加一，因为还有根节点。

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

获取第 k 层的结点个数

子问题思路：左子树的第 k 层节点数加右子树的第 k 层结点数，在根节点不为空的前提下，当k 就是1 的时候，那么返回 1 .

    public int getKNodes(TreeNode root,int k) {if(root == null) {return 0;}if(k == 1) {return 1;}return getKNodes(root.left,k-1) + getKNodes(root.right,k-1);}

判断一棵树是不是完全二叉树

在这里插入图片描述

从上图可以得知：如果我们把空节点也入队的话，那么如果是完全二叉树最后存放的结点应该全是 null，否则就不是完全二叉树。

    public boolean isCompleteTree(TreeNode root) {if(root == null) {return true;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while(!queue.isEmpty()) {TreeNode tmp = queue.poll();if(tmp != null) {queue.offer(tmp.left);queue.offer(tmp.right);} else {break;}}while(!queue.isEmpty()) {TreeNode tmp = queue.poll();if(tmp != null) {return false;}}return true;}

平衡二叉树

平衡二叉树是指该树所有节点的左右子树的深度相差不超过 1

要注意是所有结点的子树！！！
在这里插入图片描述
上图则是一颗平衡二叉树。

在这里插入图片描述
这就不是一颗平衡二叉树。

二叉搜索树

‌二叉搜索树（Binary Search Tree），也称为二叉查找树或二叉排序树，是一种特殊的二叉树。它的定义基于以下性质：

若它的左子树不空，则左子树上所有节点的值都小于根节点的值。
若它的右子树不空，则右子树上所有节点的值都大于根节点的值。
它的左、右子树也分别为二叉搜索树。
此外，二叉搜索树的一个重要特性是它的中序遍历结果一定是有序的。这意味着在二叉搜索树中，如果按照中序遍历的方式访问所有节点，将得到一个有序的节点值序列。‌

二叉搜索树的这些性质使得它在数据检索、排序等算法中具有高效性，尤其是在需要频繁查找、插入或删除数据的场景中，二叉搜索树的操作效率通常优于其他数据结构。

习题文章链接：
http://t.csdnimg.cn/YYNy7