Java Collection(3)——BinaryTree(二叉树)
前言
1.掌握树的基本概念
2.掌握二叉树概念及特性
3.掌握二叉树的基本操作
后面的优先级队列(大根堆，小根堆)也是基于二叉树实现的，所以理解好二叉树至关重要
1.树形结构
1.1描述
树是一种非线性的数据结构，它是由不为零个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，叶朝下的
1.2特点
-
一棵树只有一个根节点，并且根节点没有前驱节点 -
除根结点外，其余节点分成n个（n>0）互不相交的集合，每个集合又是一颗与树类似的子树。每颗子树有且只有一个前驱节点，任意个后继节点 -
树是递归定义的
1.3概念（重要）
-
节点的度：一个节点拥有的子节点的数量就是该节点的度；例如A节点的度为2 -
树的度：该树种所有节点的度取**最大值** -
叶子节点/终端节点：度为零的节点 -
双亲结点/父节点：一个节点拥有子节点，那么该节点就是其子节点的父节点 -
子节点：一个节点拥有父节点，那么该节点就是其父节点的子节点 -
根节点：没有父节点的节点 -
结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推 -
树的高度/深度：该树中节点的层次取最大值
剩下的几个概念很少提及，知道即可
非终端结点或分支结点：度不为0的结点
兄弟结点：具有相同父结点的结点互称为兄弟结点
堂兄弟结点：双亲在同一层的结点互为堂兄弟
结点的祖先：从根到该结点所经分支上的所有结点；例如：D节点的祖先有A和B
子孙：以某结点为根的子树中任一结点都称为该结点的子孙；例如：以B为根节点，它的子孙有D和E
1.4表示方式
表示方式知道一个最常用的就好了：孩子兄弟表示法
1.5树的应用
文件系统管理（目录和文件）
将电脑的所有文件看成一棵树，这里的C盘就相当于根节点，C盘下有四个子节点(文件夹/目录)，每个目录下又有n个子节点
2.二叉树
2.1概念：
树的度<=2的树形结构
2.2特点
由上图可知
-
二叉树不存在度大于2的结点 -
二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
二叉树有以下几种情况
2.3两种特殊的二叉树
-
满二叉树: 一棵二叉树，如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树。也就是说，如果一棵二叉树的层数为K，且结点总数是2^k - 1 ，则它就是满二叉树 -
完全二叉树: 对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树.
2.4二叉树的性质
- 若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有 2^(i - 1)(i>0)个结点
- 若规定根结点的层数为1，则一棵深度为k非空二叉树的总结点数为(2^k) - 1
-
对任何一棵二叉树, 如果其**叶结点**个数为 n0, **度为2的非叶结点**个数为 n2,则有**n0＝n2＋1** - 具有n个结点的完全二叉树的深度k=log₂(n)向上取整
2.5完全二叉树的节点组成**(我自己总结的规律)
设总结点数N，度为1的节点数n1，度为2的节点数n2，度为1的节点数n0
-
完全二叉树中度为1的节点要么有一个，要么没有 -
当总结点数目为奇数时，没有度为1的节点，满足关系式N=n2+n0,且n2=n0-1；当总结点数为偶数时，有一个度为1的节点，满足关系式N=n2+n0+n1,且n2=n0-1
2.5二叉树的存储方式
二叉树的存储结构分为：顺序存储和类似于链表的链式存储
下篇博文会在完全二叉树的基础上实现优先级队列/堆(顺序存储)；本文模拟实现二叉树/（下篇博文的二叉搜索树）用类似链表的方式，非完全二叉树使用顺序存储会浪费空间。
二叉树的链式存储是通过一个一个的节点引用起来的，常见的表示方式有二叉和三叉表示方式
//二叉表示法
public static class BTNode {
BTNode left;//左孩子的引用
BTNode right;//右孩子的引用
int val;//数据域
public BTNode(int val) {
this.val = val;
}
}
//三叉表示法
public static class BTNode {
BTNode left;//左孩子的引用
BTNode right;//右孩子的引用
BTNode parent;//当前节点的根节点/父节点
int val;//数据域
public BTNode(int val) {
this.val = val;
}
}
2.6二叉树的基本操作
2.6.1前置说明
学习二叉树的基本操作之前，首先得创建一颗二叉树，由于大家对于二叉树还不够了解，所以我先手动创建一颗二叉树，等熟悉二叉树的基本操作后再来研究二叉树真正的创建方式
public BTNode getRoot() {
return root;
}
//二叉表示法
public static class BTNode {
BTNode left;//左孩子的引用
BTNode right;//右孩子的引用
int val;//数据域
public BTNode(int val) {
this.val = val;
}
}
private BTNode root;
//手动创建二叉树
public void createBinaryTree(){
BTNode btNode1 = new BTNode(1);
BTNode btNode2 = new BTNode(2);
BTNode btNode3 = new BTNode(3);
BTNode btNode4 = new BTNode(4);
BTNode btNode5 = new BTNode(5);
BTNode btNode6 = new BTNode(6);
BTNode btNode7 = new BTNode(7);
BTNode btNode8 = new BTNode(8);
btNode1.left = btNode2;
btNode2.left = btNode4;
btNode2.right = btNode5;
btNode1.right = btNode3;
btNode3.left = btNode6;
btNode3.right = btNode7;
btNode4.left = btNode8;
root = btNode1;
}
注意：上述代码并不是创建二叉树的方式，真正创建二叉树方式下篇博文讲到二叉搜索树再介绍
2.6.2二叉树的遍历
学习二叉树结构，最简单的方式就是遍历。所谓遍历，就是沿着某条搜索路线，对树中的每一个节点做一次且仅做一次访问操作，访问操作依赖于实际的应用场景(打印节点，节点+1)
对于二叉树来说，常用的遍历方式有四种(前序遍历，中序遍历，后序遍历，层序遍历)，这里先介绍前三种
-
前序遍历(Preorder Traversal)：访问根节点——>根的左子树——>根的右子树 -
中序遍历(Inorder Traversal)：根的左子树——>根节点——>根的右子树 -
后序遍历(Postorder Traversal)：根的左子树——>根的右子树——>根节点
这图是前序遍历的路径
以这张图片的二叉树为准，三种遍历方式的访问顺序如下
前序遍历：1->2->3->4->5->6
中序遍历：3->2->1->5->4->6
后序遍历：3->2->5->6->4->1
//前序遍历
public void preOrder(BTNode root){
if (root == null) return;
//打印当前节点
System.out.print(root.val+" ");
//遍历左树
preOrder(root.left);
//遍历右树
preOrder(root.right);
}
//中序遍历
public void inOrder(BTNode root){
if (root == null) return;
//遍历左树
inOrder(root.left);
//打印当前节点
System.out.print(root.val+" ");
//遍历右树
inOrder(root.right);
}
//后序遍历
public void postOrder(BTNode root){
if (root == null) return;
//遍历左树
postOrder(root.left);
//遍历右树
postOrder(root.right);
//打印当前节点
System.out.print(root.val+" ");
}
2.6.3二叉树的基本操作
1.获取树中节点的个数
public int size(BTNode root){
if (root == null) return 0;
return (size(root.left) + size(root.right) + 1);
}
2.获取叶子节点的个数
public int getLeafNodeCount(BTNode root){
if (root == null) return 0;
if( root.left == null && root.right == null) return 1;
return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
}
3.获取第K层节点的个数
public int getKLevelNodeCount(BTNode root,int k){
if (root == null) return 0;
if (k == 1) return 1;
return getKLevelNodeCount(root.left,k - 1) + getKLevelNodeCount(root.right,k - 1);
}
4.获取二叉树的高度
public int getHeight(BTNode root){
if (root == null) return 0;
int countLeft = getHeight(root.left);
int countRight = getHeight(root.right);
return (countLeft >= countRight ? countLeft + 1 : countRight + 1);
}
5.检测值为value的元素是否存在
public Boolean findValue(BTNode root, int val){
if (root == null) return false;
if (root.val == val) return true;
if(findValue(root.left,val)) return true;
if(findValue(root.right,val)) return true;
return false;
}
6.层序遍历初阶
public void levelOrder(BTNode root){//两种
if (root == null) return;
Queue<BTNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
BTNode cur = queue.poll();
System.out.print(cur.val+" ");
if (cur.left != null){
queue.offer(cur.left);
}
if (cur.right != null){
queue.offer(cur.right);
}
}
}
7.层序遍历进阶
public List<List<BTNode>> levelOrder2(BTNode root){//两种
List<List<BTNode>> ret = new ArrayList<>();
if (root == null) return ret;
Queue<BTNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
int size = queue.size();
List<BTNode> temp = new ArrayList<>();
while (size != 0) {
BTNode cur = queue.poll();
temp.add(cur);
size--;
if (cur != null && cur.left != null) {
queue.offer(cur.left);
}
if (cur != null && cur.right != null) {
queue.offer(cur.right);
}
}
ret.add(temp);
}
return ret;
}
8.判断完全二叉树
public Boolean isCompleteTree (BTNode root){
if (root == null) return true;
Queue<BTNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
BTNode cur = queue.poll();
if (cur != null){
queue.offer(cur.left);
queue.offer(cur.right);
}else {
break;
}
}
while (!queue.isEmpty()){
BTNode cur = queue.poll();
if (cur != null) return false;
}
return true;
}
三.小结
至此，二叉树的基本操作已经介绍完毕了，下篇博文会在二叉树的基础上延伸出其他的结构，例如：二叉搜索树，优先级队列