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;}