数据结构:Binary Search Tree

理解递归的关键:

调用的时候就离开了,离开了以后就深入下一层,什么时候下一层返回了,还要继续执行。

二叉树(Binary Tree)

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

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.20.11](https://cdn.jsdelivr.net/gh/Nngxu/ImgHosting/PicGo/截屏2022-02-09 下午8.20.11.png)

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

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

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-01-10 上午11.49.22](/Users/ningxu/Desktop/截屏2022-01-10 上午11.49.22.png)

真二叉树(proper binary tree)

所有Node的度要么是0,要么是2

截屏2022-02-09 下午8.26.01

满二叉树(Full Binary Tree)

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.27.06

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

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

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

![第5章 树和二叉树-40](/Users/ningxu/Desktop/第5章 树和二叉树-40.jpg)

二叉搜索树

对于动态数组:添加、删除、搜索的时间复杂度都是O(n),因为都需要遍历

对于有序的动态数组:添加和删除的时间复杂度都是O(n),因为都需要遍历挪动元素;搜索的时间复杂度为O(log2n)

截屏2022-02-09 下午8.31.39

而使用二叉搜索树的添加、删除、搜索的time complexity都可以优化到O(log2n)

1.任意一个节点的值都大于其左子树所有节点的值

2.任意一个节点的值都小于其右子树所有节点的值

截屏2022-02-09 下午8.32.18

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

截屏2022-02-09 下午8.35.06
 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);
    }
截屏2022-02-09 下午8.36.28
 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);
    }
截屏2022-02-09 下午8.37.07
 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
  
截屏2022-02-09 下午8.40.34
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
/**
most important:度为2的节点的前驱节点或者后继节点的为度为1或者0--可以根据BST自己推理然后扩散到BT中
因为度为2的节点一个有左右子节点前驱节点一定在下面,可以一直找
算法分析:
先用前驱或者后继节点的值覆盖原节点的值
然后删除相应的前驱或者后继节点
一、删除节点5
先用前驱或者后继节点的值覆盖原节点的值
然后删除相应的前驱或者后继节点--使用删除度为1、0度方法
*/

截屏2022-02-09 下午8.40.16
1
2
3
删除节点4
先用前驱或者后继节点的值覆盖原节点的值
然后删除相应的前驱或者后继节点--使用删除度为10度方法
截屏2022-02-09 下午8.39.56
 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的左子节点还是右子节点
*/
截屏2022-02-09 下午8.39.31
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是完全二叉树的性质)

截屏2022-02-09 下午8.39.05

2.如果BST 从小到大添加节点或者从叶子到根删除元素时或者搜索时—–二叉搜索树退化成链表

防止方法——>

截屏2022-02-09 下午8.38.53 截屏2022-02-09 下午8.38.25

将普通二叉树的方法(不讲究顺序的方法如:Clear、elementNotNullCheck、height、PreOrder、Inorder、PostOrder、LevelOrder、invertTree、isComplete、isEmpty、MLGJ打印二叉树的方法、predecessor、successor、toString)放入Binary Tree

将需要用到大小排列的所有方法(用到compare的所有方法)都放入BST中