数据结构：树

树的基本定义：

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

• 每个节点有零个或多个子节点；
• 没有父节点的节点称为根节点；
• 每一个非根节点有且只有一个父节点；
• 除了根节点外，每个子节点可以分为多个不相交的子树；

树的相关术语：

节点的度：

一个节点含有的子树的个数称为该节点的度；

叶节点：

度为0的节点称为叶节点，也可以叫做终端节点

分支节点：

度不为0的节点称为分支节点，也可以叫做非终端节点，显然除了叶子节点之外的节点都为分支节点。

节点的层次：

节点的层次为从节点到根节点的路径中边的条数，并且认为根节点的层次为0，因为根节点到自身的路径中边的条数为0

树的度：

树中所有节点的度的最大值

树的高度（深度）：

结点的深度指从根节点(度为1)自顶向下逐层累加至该结点时的深度。树的深度是树中深度最大的结点的深度。

如下图，该树的深度为5

💡1、二叉树：

二叉树的定义就是每个节点最多有两个子节点

二叉树的设计：

代码：

public class TreeNode<Key,Value> {private TreeNode left; //左子节点private TreeNode right; //右子节点private Key key; //存储键private Value value;//存储值public TreeNode(TreeNode left, TreeNode right, Key key, Value value) {this.left = left;this.right = right;this.key = key;this.value = value;}
}

插入方法put实现思想
1如果当前树中没有任何一个节点，则直接把新节点当做根节点使用
2如果当前树不为空，则从根节点开始
3如果新节点的key小于当前节点的key，则继续找当前节点的左子节点；
4如果新节点的key大于当前节点的key，则继续找当前节点的右子节点；
5如果新节点的key等于当前节点的key，则树中已经存在这样的节点，替换该节点的value即可；
插入方法代码：
 

 //记录根节点private TreeNode root;//记录元素个数private int N;public void put(Key key,Value value){root = put(root, key, value); //如果是第一次插入 直接该节点为根节点}//重载递归插入元素public TreeNode put(TreeNode node,Key key,Value value){if (node==null){//如果传入节点为空 则代表当前树中没有元素node=new TreeNode(null,null,key,value);N++;return node;}else {//如果不为空 则需要判断key大小 决定新插入元素是在左子节点还是右子节点int i = key.compareTo(node.key);  //需要实现 Comparable<>泛型接口 x.compareTo(y) 若返回“负数”，意味着“x比y小”；返回“零”，意味着“x等于y”；返回“正数”，意味着“x大于y”。if (i<0){  //i<0 表示新插入key 小于父节点key 那么就需要插入左边node.left = put(node.left, key, value);N++;}if (i>0){ //i>0 表示新插入的key 大于父节点key 那么就需要插入到右边node.right=put(node.right,key,value); //递归调用N++;}if (i==0){//i=0 表示当前key 和传入key 相等 那么直接将value覆盖node.value=value;}}return node;

获取方法get实现思想
从根节点开始：
1如果要查询的key小于当前节点的key，则继续找当前节点的左子节点；
2如果要查询的key大于当前节点的key，则继续找当前节点的右子节点;
3如果要查询的key等于当前节点的key，则树中返回当前节点的value；
代码实现：
 

 //查询元素方法 根据key 返回valuepublic Value get(Key key){if (root==null){return null; //当树中为空时 直接返回空}return get(root,key);}//查找递归public Value get(TreeNode node,Key key){int i = key.compareTo(node.key); //和插入同理 进行比较if (i<0){//i<0 表示需要查找的key 比节点key小 那么就继续寻找该节点的左子节点return get(node.left, key);}if (i>0){//i>0 表示要查找的key 比节点的key大 那么就继续寻找该节点的右子节点return get(node.right,key);}else {//i=0 表示找到对应的ke 直接返回对应的valuereturn node.value;}}

删除方法delete实现思想

1. 找到被删除节点；
2. 找到被删除节点右子树的最小节点minNode
3. 删除右子树的最小节点
4. 让被删除节点的左子树称为minNode的左子树，被删除节点右子树同理；
5. 让被删除节点的父节点指向最小结点minNode

但删除会碰到许多的情况，如下：

1.当找到最小子节点时，如果它还有右子节点，那么还需要将右子节点赋给最小子节点的父节点。

如下图所示，但删除节点2时，找到最小子节点5，但是5节点还有一个右子节点，那么就需要将右子节点重新赋值给最小子节点的父节点也就是图中的8节点。然后在将5节点替换2节点

这部分对应代码

                TreeNode sonNode=node.right;  //找到右子树根节点  从右子节点开始遍历TreeNode sonFather=node;while (sonNode.left!=null){ //然后遍历寻找右子节点的左子节点sonFather=sonNode;  //记录最小左节点的父节点  为了应对最小子节点还有右子节点用  //TODO: bug记录 --顺序错误  应该在sonNode赋值前先将Father赋值 --否则会导致栈溢出sonNode=sonNode.left; //直到找到最左节点 也就是右子树中最小的那个节点}TreeNode minNode=sonNode;//如果最小节点此有右子节点 那么需要将最小节点的右子节点 重新赋值给最小节点的父节点if (minNode.right!=null){sonFather.left=minNode.right;  //将最小子节点的父节点  指向该节点的右子节点minNode.right=null; //将minNode 的子节点断开  --------------->  TODO:bug记录点1   此处导致 栈溢出}

删除方法完整代码：

后续可以进一步优化，提取重复代码

  //删除元素方法 根据key删除  返回被删除元素valuepublic Value delete(Key key){if (root==null){return null;}return   delete(root,key,root);}//递归查找删除方法public Value delete(TreeNode node,Key key,TreeNode father){//同样先要进行查找int i = key.compareTo(node.key);if (i<0){//key比节点key小 继续找左子节点father=node; //父节点变化    -----》TODO bug记录  父节点忘记变化 导致一直是指向根节点return     delete(node.left,key,node);//将父节点也传入}else if (i>0){//key 比当前节点key大 继续找右子节点father=node;  //父节点变化return delete(node.right,key,node);//将父节点也传入}else {  //此时找到了需要删除的key//临时记录 被删除元素的 左节点和右节点 --》需要判空处理 对左右节点//如果发现该节点的左右子节点都为空 那么就直接进行删除即可if (node.left==null&&node.right==null){//如果是根节点  并且树中只有根节点的时候if (N==1){root=null;}if (node.equals(father.left)){father.left=null;  //如果该节点是父节点的左子节点 则直接删除}else {father.right=null; //如果是右子节点则直接 则值节删除}N--;return node.value;  //返回删除的元素}//到这一步 必定是右子节点为null  左子节点不为null的情况if (node.right==null){ //如果被删除元素右子节点为空  那么直接将被删除元素的左子节点替换即可if (node.equals(father.left)){father.left=node.left;}else {father.right=node.left;}N--;return node.value; //返回删除的元素} else { //到这一步就 是左右子节点都不为null的情况  然后从被删除元素的右子树开始遍历 直到找右子树中最小的元素TreeNode sonNode=node.right;  //找到右子树根节点  从右子节点开始遍历TreeNode sonFather=node;while (sonNode.left!=null){ //然后遍历寻找右子节点的左子节点sonFather=sonNode;  //记录最小左节点的父节点  为了应对最小子节点还有右子节点用  //TODO: bug记录 --顺序错误  应该在sonNode赋值前先将Father赋值 --否则会导致栈溢出sonNode=sonNode.left; //直到找到最左节点 也就是右子树中最小的那个节点}TreeNode minNode=sonNode;//如果最小节点此有右子节点 那么需要将最小节点的右子节点 重新赋值给最小节点的父节点if (minNode.right!=null){sonFather.left=minNode.right;  //将最小子节点的父节点  指向该节点的右子节点minNode.right=null; //将minNode 的子节点断开  --------------->  TODO:bug记录点1   此处导致 栈溢出}//到此所有情况已经判断完毕 可以执行节点删除if (node.equals(father.left)){father.left=minNode;minNode.left=node.left;minNode.right=node.right;  //进行删除操作}else {father.right=minNode;minNode.left=node.left;minNode.right=node.right; // 进行删除操作}N--;return node.value;  //返回被删除元素}}}

寻找最小值getMin实现思想

搞懂删除方法后，最小值思路就相比很简单了，一直循环或递归左子节点，直到为null即可。

  //寻找最小值public Value getMin(){if (root==null){return null;}TreeNode min=root;while (min.left!=null){min=min.left;}return min.value;}

寻找最大值getMax实现思想

与最小值方法同理，无非是从遍历左节点改为了右节点

  //寻找最大值public Value getMax(){if (root==null){return null;}TreeNode max=root;while (max.right!=null){max=max.right;}return max.value;}

二叉树遍历：

二叉树的遍历是树中很重要的一个部分了，由于树的结构特殊性，它没有办法从头开始依次向后遍历，所以存在如何遍历，也就是按照什么样的搜索路径进行遍历的问题。

1.前序遍历：

先访问根节点，然后再访问左子树，最后访问右子树

2.中序遍历:

先访问左子树，中间访问根节点，最后访问右子树

3.后序遍历:

先访问左子树，再访问右子树，最后访问根节点

1.前序遍历：

实现思路：

1. 把当前结点key放入到队列中；
2. 找到当前结点的左子树，如果不为空，则递归遍历左子树；
3. 找到当前节点的右子树，如果不为空，则递归遍历右子树；

以该树为例，那么前序遍历的结果应该是：

10-2-1-8-5-3-4-6-9-12-11-16

中序遍历结果应该是：

2-1-8-5-3-4-6-9-10-12-11-16

后序遍历结果应该是：

2-1-8-5-3-4-6-9-12-11-16-10

实现代码：

   //前序遍历 从根节点开始——》左子树——》右子树public Queue<Key> preErgodic(){Queue<Key> keys=new Queue<>();preErgodic(root,keys);return keys;}//递归遍历 将遍历到的都添加在队列中private void preErgodic(TreeNode x,Queue<Key> key){if (x==null){return;}key.inQueue(x.key);if (x.left!=null){//如果左子节点不为空 则递归遍历左子节点preErgodic(x.left,key);}if (x.right!=null){preErgodic(x.right,key);}}

运行结果

    public static void main(String[] args) {BinaryTree<Integer,String> tree=new BinaryTree<>();tree.put(10,"张三");tree.put(2,"老二");tree.put(1,"老一");tree.put(8,"老八");tree.put(5,"老五");tree.put(9,"老九");tree.put(3,"老三");tree.put(6,"老六");tree.put(4,"老四");tree.put(12,"老十二");tree.put(11,"老十一");tree.put(16,"老十六");Queue<Integer> queue=tree.preErgodic();for (Integer integer : queue) {System.out.println(integer);}System.out.println("------------------中序遍历-------------------------");Queue<Integer> queueMid = tree.midErgodic();for (Integer integer : queueMid) {System.out.println(integer);}System.out.println("---------后序遍历-------------------------");Queue<Integer> queueAfter = tree.afterErgodic();for (Integer integer : queueAfter) {System.out.println(integer);}}
//运行结果
10
2
1
8
5
3
4
6
9
12
11
16------------------------------中序遍历-------------------------
2
1
8
5
3
4
6
9
10
12
11
16
------------------------------后序遍历-------------------------
2
1
8
5
3
4
6
9
12
11
16
10

2.中序遍历：

1. 找到当前结点的左子树，如果不为空，则递归遍历左子树；
2. 把当前结点key放入到队列中；
3. 找到当前节点的右子树，如果不为空，则递归遍历右子树；

代码：

 //中序遍历 从左子树开始——》根节点——》右子树public Queue<Key> midErgodic(){Queue<Key> keys=new Queue<>();preErgodic(root,keys);return keys;}//递归遍历 将遍历到的都添加在队列中private void midErgodic(TreeNode x,Queue<Key> key){if (x==null){return;}//先找到左子节点if (x.left!=null){//如果左子节点不为空 则递归遍历左子节点preErgodic(x.left,key);}key.inQueue(x.key);if (x.right!=null){preErgodic(x.right,key);}}

3.后序遍历：

1. 找到当前结点的左子树，如果不为空，则递归遍历左子树；
2. 找到当前节点的右子树，如果不为空，则递归遍历右子树；
3. 把当前结点key放入到队列中；

//后序遍历 从左子树开始——》右子树——》根节点public Queue<Key> afterErgodic(){Queue<Key> keys=new Queue<>();preErgodic(root,keys);return keys;}//递归遍历 将遍历到的都添加在队列中private void afterErgodic(TreeNode x,Queue<Key> key){if (x==null){return;}//先找到左子节点if (x.left!=null){//如果左子节点不为空 则递归遍历左子节点preErgodic(x.left,key);}if (x.right!=null){preErgodic(x.right,key);}key.inQueue(x.key);}

4.层序遍历：

层序遍历，就是从根节点（第一层）开始，依次向下，获取每一层所有结点的值。

以该树为例，那么层序遍历结果是：

10-2-12-1-8-11-16-5-9-3-6-4

实现思路：

1. 创建一个队列，存储每一层的节点；
2. 使用循环队列中弹出一个节点；
3. 然后获取到到当前节点key
4. 如果当前节点的左子节点不为空，则把左子结点放入队列中
5. 如果当前节点的右子节点不为空，则把右子结点放入队列中

代码:

  public Queue<Key> layerErgodic(){Queue<Key> keys=new Queue<>();   //存储遍历结果队列Queue<TreeNode> nodes=new Queue<>();//循环节点队列nodes.inQueue(root); //将根节点添加至循环队列中while (!nodes.isEmpty()){ //如果不为空 则代表还需要判断是否有 子节点判断TreeNode treeNode = nodes.outQueue();keys.inQueue(treeNode.key); //先将该节点加入 结果队列中if (treeNode.left!=null){nodes.inQueue(treeNode.left);}if (treeNode.right!=null){nodes.inQueue(treeNode.right);}}return keys;}//运行结果：
10-2-12-1-8-11-16-5-9-3-6-4-

实际例题：

在力扣的题中，有时候是要求你将每一层作为一个结果输出，比单纯输出顺序要更为复杂一点点。

思路：通过递归的方式+两个队列来实现.

首先将根节点传入父层节点队列，然后检查根节点的左右子节点，将左右子结点添加到子层待搜索队列，父层节点中的所有队列元素取出后，将待搜索的子结点队列作为父节点队列进行递归。然后将每一层的父节点队列作为结果添加即可。

第一层递归。

第二层递归

完整代码：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {List<List<Integer>> result=new ArrayList<>();public List<List<Integer>> levelOrder(TreeNode root) {//层序遍历 就是广度优先搜索//创建待搜索队列if(root==null){return result;}Queue<TreeNode> queue=new LinkedList<>();queue.offer(root);cenxu(queue);return result;}public void cenxu(Queue queue){ //将根节点和队列传入//将当前节点传入queueList<Integer> r=new ArrayList<>();  //层序结果Queue<TreeNode> waitSearch=new LinkedList<>();//通过两个队列来实现 父队列存放当前层的所有节点 子队列存当前节点的所有子结点while(!queue.isEmpty()){//遍历父节点//先取出所有节点 然后表示是一个层的//存放到结果中TreeNode node=(TreeNode)queue.poll();r.add(node.val);if(node.left!=null){//将当前层级的所有子结点存入 子队列中waitSearch.offer(node.left);}if(node.right!=null){waitSearch.offer(node.right);}}//递归 队列就是下一个的父队列result.add(r);if(waitSearch.isEmpty()){return;}cenxu(waitSearch);}
}