理解递归的关键:
调用的时候就离开了，离开了以后就深入下一层，什么时候下一层返回了，还要继续执行。
![https://cdn.jsdelivr.net/gh/Nngxu/ImgHosting/PicGo/%E6%88%AA%E5%B1%8F2022-02-09%20%E4%B8%8B%E5%8D%888.16.47.png]( "截屏2022-02-09 下午8.16.47")
![https://cdn.jsdelivr.net/gh/Nngxu/ImgHosting/PicGo/%E6%88%AA%E5%B1%8F2022-02-09%20%E4%B8%8B%E5%8D%888.19.36.png]( "截屏2022-02-09 下午8.19.36")
![https://cdn.jsdelivr.net/gh/Nngxu/ImgHosting/PicGo/%E6%88%AA%E5%B1%8F2022-02-09%20%E4%B8%8B%E5%8D%888.24.27.png]( "截屏2022-02-09 下午8.24.27")
![https://cdn.jsdelivr.net/gh/Nngxu/ImgHosting/PicGo/%E6%88%AA%E5%B1%8F2022-02-09%20%E4%B8%8B%E5%8D%888.22.57.png]( "截屏2022-02-09 下午8.22.57")
![https://cdn.jsdelivr.net/gh/Nngxu/ImgHosting/PicGo/%E6%88%AA%E5%B1%8F2022-02-09%20%E4%B8%8B%E5%8D%888.22.34.png]( "截屏2022-02-09 下午8.22.34")
所有Node的度要么是0，要么是2
1.每一层上的节点数都是最大节点数
2.所有的叶子Node都在最后一层
![https://cdn.jsdelivr.net/gh/Nngxu/ImgHosting/PicGo/%E6%88%AA%E5%B1%8F2022-02-09%20%E4%B8%8B%E5%8D%888.26.33.png]( "截屏2022-02-09 下午8.26.33")
在满二叉树中，从最后一个节点开始，连续去掉任意个节点，即是一颗完全二叉树
![https://cdn.jsdelivr.net/gh/Nngxu/ImgHosting/PicGo/%E6%88%AA%E5%B1%8F2022-02-09%20%E4%B8%8B%E5%8D%888.27.44.png]( "截屏2022-02-09 下午8.27.44")
![https://cdn.jsdelivr.net/gh/Nngxu/ImgHosting/PicGo/%E6%88%AA%E5%B1%8F2022-02-09%20%E4%B8%8B%E5%8D%888.28.19.png]( "截屏2022-02-09 下午8.28.19")
![https://cdn.jsdelivr.net/gh/Nngxu/ImgHosting/PicGo/%E6%88%AA%E5%B1%8F2022-02-09%20%E4%B8%8B%E5%8D%888.29.35.png]( "截屏2022-02-09 下午8.29.35")
对于动态数组:添加、删除、搜索的时间复杂度都是O(n),因为都需要遍历
对于有序的动态数组:添加和删除的时间复杂度都是O(n)，因为都需要遍历挪动元素；搜索的时间复杂度为O(log2n)
而使用二叉搜索树的添加、删除、搜索的time complexity都可以优化到O(log2n)
1.任意一个节点的值都大于其左子树所有节点的值
2.任意一个节点的值都小于其右子树所有节点的值
3.不允许节点内数据为null(无法比较大小)
4.二叉搜索树没有索引的概念，因为无法标记索引，因为add会改变索引位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
//基本操作
/**
* 删除某个元素
*/
public E remove(E element);
/**
* 清空所有元素
*/
public void clear();
/**
* @return 返回二叉树中数据元素的数量
*/
public int size();
/**
* @return 判断该顺序表是否为空
*/
public boolean isEmpty();
/**
* @param element 要比较的element
* @return 判断顺序表中是否有该element
* 是否包含某元素
*/
public boolean contains(E element);
/**
* @param element
*/
public void add(E element) ;
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
/**
Binary Search Tree需要的字段
*/
//树内Node数量
private int size;
//node of root
private Node<E> root;
//Node
private static class Node<E> {
E element
Node<E> left;
Node<E> right;
Node<E> parent;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
/**
算法功能:实现按照客户要求进行的前序遍历，并在客户想要终止时，即使终止，防止cpu资源的浪费，减小时间复杂度
输入参数：Node<E> node, Visitor<E> vistor (想要从哪个节点开始遍历,访问的方式及访问到哪里终止访问）
这里包含的非常重要的设计思想：设计一个类时；不想把方法完全定死，想要按照客户的个性化需求来实现方法，给予设计的方法一定的自由度（如这里想要按照客户的vistor方法来遍历打印）
--->将Visitor设置为接口（优点：简单清晰，缺点：无法声明字段）
--->将Visitor设置为静态抽象内部类（优点：可以声明字段，缺点：稍微复杂）
因为这里想使用声明stop字段来表示访问到某个变量时及时终止遍历---->所以选用方式二
*/
//方式一显然不满足现在的要求
public Interface Visitor<E>
{
boolean visit(E element);
}
/**方式二
* 如果从客户返回false表示进行访问，如果返回true表示停止访问
* 该接口实现客户决定访问节点时想要干啥
* static是内部类new的时候不用先有外部类的对象
* abstract是为了让visit方法可以由客户自定
*/
public static abstract class Visitor<E>
{
boolean stop;
abstract boolean visit(E element);
}
/**
算法分析：
0.判断visitor是否为空
1.根据node和visitor.stop判断使用需要进行遍历
2.传入客户想要的打印方式和更新stop
3.递归传入左节点
4.递归传入右节点
总结:在第一次发现了想要终止的节点后就及时进行了停止---->次数就是Ning氏分析二叉树图的左中右的左
*/
/**
* 客户自定的前序遍历访问方式
* @param visitor
*/
public void PreOrder(Visitor<E> visitor)
{
if (visitor==null) return;
PreOrder(root,visitor);
}
protected void PreOrder(Node<E> node, Visitor<E> visitor)
{
//见下图 如要找到5就停止 在A处找到5 stop变为ture 在B处就停止
if (node == null|| visitor.stop) return;
visitor.stop = visitor.visit(node.element);
PreOrder(node.left,visitor);
PreOrder(node.right,visitor);
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
/**
算法分析：
0.判断visitor是否为空
1.根据node判断使用需要进行遍历
2.递归传入左节点
3.传入客户想要的打印方式和更新stop
4.递归传入右节点
总结:
*/
/**
* 客户自定的中序遍历访问方式
* @param visitor
*/
public void InOrder(Visitor<E> visitor)
{
if (visitor==null) return;
InOrder(root,visitor);
System.out.println();
}
private void InOrder(Node<E> node, Visitor<E> visitor)
{
//见下图 如要找到5就停止 在G处找到5 stop变为ture 在H处就停止
if (node == null||visitor.stop) return;
InOrder(node.left,visitor);
//见下图 如要找到5就停止 在G处找到5 stop变为ture 在O处就停止
if (visitor.stop) return;
visitor.stop = visitor.visit(node.element);
InOrder(node.right,visitor);
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
/**
算法分析：
0.判断visitor是否为空
1.根据node和stop判断使用需要进行遍历
2.递归传入左节点
3.递归传入右节点
4.根据stop判断是否需要停止遍历
5.传入客户想要的打印方式和更新stop
总结:
*/
/**
* 客户自定的后序遍历访问方式
* @param visitor
*/
public void PostOrder(Visitor<E> visitor)
{
if (visitor==null) return;
PostOrder(root,visitor);
System.out.println();
}
//见下图 如要找到5就停止 在I处找到5 stop变为ture
private void PostOrder(Node<E> node, Visitor<E> visitor)
{
////见下图 如要找到5就停止 在I处找到5 stop变为ture 在J处停止
if (node == null||visitor.stop==true) return;
PostOrder(node.left,visitor);
PostOrder(node.right,visitor);
//见下图 如要找到5就停止 在I处找到5 stop变为ture 在15N处才停止
if (visitor.stop == true) return;
visitor.stop = visitor.visit(node.element);
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
/**
* 客户自定的层序遍历访问方式
* 使用队列思想：从对头出对一个 将其子节点都入对
* @param visitor
*/
public void levelOrder(Visitor<E> visitor)
{
if (root==null || visitor == null) return;
Queue<Node<E>> queue = new Queue<>();
queue.enQueue(root);
while (!queue.isEmpty())
{
Node<E> node = queue.deQueue();
//如果等于true就停止访问
boolean b = visitor.visit(node.element);
if (b == true) return;
if (node.left!=null)
{
queue.enQueue(node.left);
}
if (node.right!=null)
{
queue.enQueue(node.right);
}
}
}
|
1
2
3
4
5
6
|
/**
* 前序遍历:树状结构展示
* 中序遍历:二叉搜索树的中序遍历按什序或者降序处理节点
* 后序遍历:适合一些先子后父的操作
* 层序遍历:计算二叉树的高度、计算二叉树是否为完全二叉树
*/
|
1
2
3
4
5
6
7
8
9
10
11
|
/**
* 算法分析:
* 1.根节点的高度就是二叉树的高度
* 2.如何获取一个节点的高度:和左右子节点的高度有关---等于子节点中高度最大的节点的高度+1
* @return
*/
private int height1(Node<E> node)
{
if (node == null) return 0;
return 1+Math.max(height1(node.left),height1(node.right));
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
//获取BST的高度--等价于有多少层---层序遍历--迭代
/**
* 获取任意根节点开始的树的height
* @param node 根节点
* @return BST的高度
* 算法分析1---使用迭代
* 1.什么时候高度会发生变化--访问完一层
* 2.什么时候算是访问完一层--首先要明确一层有多少个（用一个变量装起来）--从对头取出一层元素数量时，访问完一层---heigh++
* 3.一层有多少个怎么确定--访问完一层，取出对头元素完成一次while中的一次迭代，队列里面的元素长度为下一层的元素个数，
* 比如取出22会装入12 55 对内元素数量为2即为第二层的元素数量
* ┌─22_p(null)─┐
* │ │
* 12_p(22) ┌─55_p(22)─┐
* │ │
* ┌─45_p(55) 71_p(55)─┐
* │ │
* 44_p(45) 79_p(71)
* 4.如何确定访问完一层--使用一个levelsize的变量来确定 当levelsize减为0时就说明这一次访问完成 这时进行一次while遍历后 将levelsize置为下一层的元素个数
* 5.什么时候访问完成-
*/
private int height(Node<E> node)
{
if (node == null) return 0;
//初始化高度变量用来，当一层访问完时 heigt++
int height = 0;
//初始化记录每一层的元素个数的变量levelsize 因为初始时有root一层所以levelsize=1
int levelsize = 1;
//使用Queue进行层序遍历
Queue<Node<E>> queue = new Queue<>();
//根节点先入队
queue.enQueue(node);
while (!queue.isEmpty())
{
Node<E> de = queue.deQueue();
levelsize--;
if (de.left!=null)
queue.enQueue(de.left);
if (de.right!=null)
queue.enQueue(de.right);
if (levelsize == 0)
{
levelsize = queue.size();
//访问完一层后 将levelsize置为下一层的元素数量 将height+1
height++;
}
}
return height;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
/**
* 翻转一颗二叉树,并返回根节点
* ┌──────────8_p(null)───────────┐
* │ │
* ┌─────4_p(8)────┐ ┌─13_p(8)
* │ │ │
* ┌─2_p(4)─┐ ┌─6_p(4)─┐ ┌─10_p(13)─┐
* │ │ │ │ │ │
* 1_p(2) 3_p(2) 5_p(6) 7_p(6) 9_p(10) ┌─12_p(10)
* │
* 11_p(12)
* @return
*/
public Node<E> invertTree()
{
return invertTree(root);
}
/**
* 先翻转再去遍历左子树右子树
* 先遍历左子树再遍历右子树再翻转
* 先遍历左子树 翻转 再去遍历左子树
* 想清楚在A、B、C哪个位置（前序、中序、后序）进行的是什么操作（翻转该节点的子节点）
* @param node
* @return 返回根节点
*/
private Node<E> invertTree(Node<E> node)
{
if (node == null) return node;
Node<E> temp = node.left;
node.left = node.right;
node.right = temp;
invertTree(node.left);
invertTree(node.right);
return node;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
/**
* 完全二叉树的判断--基于层序遍历的完全二叉树判断
* 0.如果树为空树，返回false
* 1.如果树不为空，开始层序遍历二叉树(use queue)
* 2.如果node.left != null && node.right != null,将node.left、node.right按顺序入队
* 3.如果node.left == null && node.right != null,一定不是完全二叉树,返回false
* 4.如果node.left != null && node.right == null或者node.right == null && node.left == null
* 那么后来遍历的节点都应该为叶子节点(用leaf做标志位)，才是完全二叉树
* 否则返回false
* 遍历结束如果还没发现问题，说明是完全二叉树 返回true
*/
public boolean isComplete()
{
return isComplete(root);
}
private boolean isComplete(Node<E> node)
{
//空树不是完全二叉树
if (node == null) return false;
Queue<Node<E>> queue = new Queue<>();
queue.enQueue(node);
//当当前node应该为叶子节点时 leaf = true
boolean leaf = false;
while (!queue.isEmpty())
{
Node<E> de = queue.deQueue();
//如果应该为leaf 而de不是leaf时就不是完全二叉树
if ((leaf == true) && (de.isLeaves() == false)) return false;
if (de.left!=null)
{
queue.enQueue(de.left);
}
//de.left == null && de.right != null
else if (de.right != null)
{
return false;
}
//node.left == null
if (de.right!=null)
{
queue.enQueue(de.right);
}
else
{
//left == null&&right==null or left!=null&&right==null -- 保证为叶子节点
leaf = true;
}
}
//检查完毕没问题就是完全二叉树
return true;
}
|
1
2
3
4
5
6
7
8
9
10
11
|
/**
算法分析：
1.添加合法性判断(not null element)
2.添加根节点 元素数量加一
3.添加非根节点
找到父节点
比较要添加的节点和父节点的大小关系
创建新节点
根据比较关系进行添加操作
*/
|
1
2
3
4
5
6
7
8
9
10
|
/**
算法分析：
0.判断visitor是否为空
1.根据node和visitor.stop判断使用需要进行遍历
2.递归传入左节点
3.判断是否还需要遍历
3.传入客户想要的打印方式和更新stop
4.递归传入右节点
*/
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
/**
* ┌──────────8_p(null)───────────┐
* │ │
* ┌─────4_p(8)────┐ ┌─13_p(8)
* │ │ │
* ┌─2_p(4)─┐ ┌─6_p(4)─┐ ┌─10_p(13)─┐
* │ │ │ │ │ │
* 1_p(2) 3_p(2) 5_p(6) 7_p(6) 9_p(10) ┌─12_p(10)
* │
* 11_p(12)
*
* 1.什么是前驱节点:中序遍历时的上一个节点--前驱节点是BT中的概念，但放到BST中 更好理解 在BST中为前一个比他小的节点
* 2.在BST中中序遍历可以获得从小到大的node.element排列，而在BST的add规则规定了node左边小右边大，所有前驱节点等价于node的左子树中的最大节点
* 情况归纳：这些规则适用于任意的BT，但我们放到BST中更好理解
*/
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
情况一:前驱节点在左子树(如8 4)
一定有前驱节点--node.left != null
node的前驱节点是左子树的最大节点(仅对BST有效)
从左子树开始最靠右的node(这条可以推导到所有BT)
predecessor = node.left.right.right.right.........
End Condition: right == null
情况二:前驱节点在父节点中(如9 7 11)
node.left == null && node.parent!=null
可能有前驱节点--node.parent.parent....!=null&&node.parent.parent.. = node.parent.parent.parent.....right
可能没有前驱节点node.parent.parent.... = null
情况三:node.left == null && node.parent == null
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
/**
* ┌──────────8_p(null)───────────┐
* │ │
* ┌─────4_p(8)────┐ ┌─13_p(8)
* │ │ │
* ┌─2_p(4)─┐ ┌─6_p(4)─┐ ┌─10_p(13)─┐
* │ │ │ │ │ │
* 1_p(2) 3_p(2) 5_p(6) 7_p(6) 9_p(10) ┌─12_p(10)
* │
* 11_p(12)
*
* 1.什么是后继节点:中序遍历时的下一个节点--后继节点是BT中的概念，但放到BST中 更好理解 在BST中为后一个比他大的节点
* 2.在BST中中序遍历可以获得从小到大的node.element排列，而在BST的add规则规定了node左边小右边大，所有后继节点等价于node的右子树中的最小节点
* 情况归纳：这些规则适用于任意的BT，但我们放到BST中更好理解
*/
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
情况一:后继节点在右子树(如8 4)
一定有后继节点--node.right != null
node的后继节点是右子树的最小节点(仅对BST有效)
从右子树开始最靠左的node(这条可以推导到所有BT)
predecessor = node.right.left.left.left.........
End Condition: left == null
情况二:后继节点在父节点中(如7 3)
node.left == null && node.parent!=null
可能有后记节点--node.parent.parent....!=null&&node.parent.parent.. = node.parent.parent.parent.....left
可能没有后继节点node.parent.parent.... = null
情况三:一定没有后继节点node.left == null && node.parent == null
|
1
2
3
4
5
6
7
8
9
10
11
|
/**
most important:度为2的节点的前驱节点或者后继节点的为度为1或者0--可以根据BST自己推理然后扩散到BT中
因为度为2的节点一个有左右子节点前驱节点一定在下面，可以一直找
算法分析:
先用前驱或者后继节点的值覆盖原节点的值
然后删除相应的前驱或者后继节点
一、删除节点5
先用前驱或者后继节点的值覆盖原节点的值
然后删除相应的前驱或者后继节点--使用删除度为1、0度方法
*/
|
1
2
3
|
二、删除节点4
先用前驱或者后继节点的值覆盖原节点的值
然后删除相应的前驱或者后继节点--使用删除度为1、0度方法
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
/**
算法分析:
一、如果node是左子节点(4)
1.child.parent = node.parent
node.parent.left = child
二、如果node是右子节点(9)
1.child.parent = node.parent
2.node.parent.right = child
三、如果node为根节点(node.parent == null)放在最前面，防止空指针访问
root = child
child.parent == null
如何确定child为node的左子节点还是右子节点
*/
|
1
2
3
4
5
6
7
8
9
|
/**
算法分析--直接删除
1.如果node为左子节点(2)--node.parent.left == node
node.parent.left = null;
2.如果node为右子节点(9)--node.parent.right == node
node.parent.right = null
3.如果要删除的是根节点(node.parent == null)放在最前面，防止空指针访问
root = null;
*/
|
1
2
3
|
/**
先删除度为2的节点(内部包含了删除度为1或者0的节点)
*/
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
//树状打印二叉树---使用前序遍历
/**
* 前序遍历:树状结构展示
* 中序遍历:二叉搜索树的中序遍历按什序或者降序处理节点
* 后序遍历:适合一些先子后父的操作
* 层序遍历:计算二叉树的高度
* @return
*/
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
PreOrderforToString(root,sb,"");
return sb.toString();
}
/**
* 由自己设计的简易版打印二叉树
* @param node
* @param sb
* @param prefix
*/
private void PreOrderforToString(Node<E> node,StringBuilder sb,String prefix)
{
if (node == null) return ;
sb.append(prefix).append(node.element).append("\n");
PreOrderforToString(node.left,sb,prefix + "---");
PreOrderforToString(node.right,sb,prefix+"---");
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
//使用compare比较器
private Node<E> getNode(E element)
{
//BST不允许有空element为null的node
if (element == null) return null;
//如果element != null 就查找
Node<E> node = this.root;
while (node != null)
{
int com = compare(element,node.element);
if (com == 0) return node;
if (com >0 ) node =node.right;
else node = node.left;
}
return null;
}
|
BST的复杂度和Tree的高度有关
1.如果BST是一颗完全二叉树时
添加删除搜索 复杂度为:（logn是完全二叉树的性质）
2.如果BST 从小到大添加节点或者从叶子到根删除元素时或者搜索时—–二叉搜索树退化成链表
防止方法——>
将普通二叉树的方法(不讲究顺序的方法如：Clear、elementNotNullCheck、height、PreOrder、Inorder、PostOrder、LevelOrder、invertTree、isComplete、isEmpty、MLGJ打印二叉树的方法、predecessor、successor、toString)放入Binary Tree
将需要用到大小排列的所有方法（用到compare的所有方法）都放入BST中
