你好赵伟

这个屌丝很懒，什么也没留下！

热门标签

树型数据结构：二分搜索树(BST)及其遍历_一个节点数据为整数的二叉搜索树,他的遍历结果可以用一个整数数组来表示

作者：你好赵伟 | 2024-03-20 16:14:18

踩

一个节点数据为整数的二叉搜索树,他的遍历结果可以用一个整数数组来表示

二分搜索树

为什么要有树结构？

将数据使用树结构存储后，对数据的使用变得出奇的高效
对于常用的树形数据结构：
1. 二分搜索树（Binary Search Tree）
2. 平衡⼆二叉树：AVL；红⿊黑树
3. 堆；并查集
4. 线段树；Trie (字典树，前缀树)

二叉树的相关定义与性质：

和链表一样，是一种动态数据结构

class Node{
    E e;
    Node left;
    Node right
}
1
2
3
4
5

二叉树具有唯一根节点
每个节点最多有两个孩子（left–左孩子，right–右孩子）
每个节点最多有一个父亲（根节点没有父节点）
没有孩子的节点–>叶子节点
二叉树具有天然的递归结构
- 每个节点的左⼦子树也是二叉树
- 每个节点的右⼦子树也是二叉树

在这里插入图片描述

二叉树不一定是“满”的（一个节点也可以二叉树，null也可以为二叉树，只要满足定义即可）

二分搜索树 Binary Search Tree

二分搜索树是二叉树
二分搜索树的每个节点的值：
- 大于其左子树的所有节点的值
- 小于其右子树的所有节点的值
每⼀棵子树也是二分搜索树
存储的元素必须有可比较性
我们的二分搜索树不不包含重复元素
如果想包含重复元素的话，只需要定义：
左子树小于等于节点；或者右⼦子树⼤大于等于节点
注意：我们之前讲的数组和链表，可以有重复元素
二分搜索树添加元素的非递归写法，和链表很像

代码定义如下：

public class BST<E extends Comparable<E>> {
    private class Node{
        public E e;
        public Node left, right;

        public Node(E e){
            this.e = e;
            left = null;
            right = null;
        }
    }

    private Node root;
    private int size;

    public BST(){
        root = null;
        size = 0;
    }

    public int size(){
        return size;
    }

    public boolean isEmpty(){
        return size == 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
29

使用递归方法在二分搜索树上添加新的元素

    // 向二分搜索树中添加新的元素e
    public void add(E e){
        root = add(root, e);
    }

    // 向以node为根的二分搜索树中插入元素e，递归算法
    // 返回插入新节点后二分搜索树的根
    private Node add(Node node, E e){

        if(node == null){
            size ++;
            return new Node(e);
        }

        if(e.compareTo(node.e) < 0)
            node.left = add(node.left, e);
        else if(e.compareTo(node.e) > 0)
            node.right = add(node.right, e);

        return node;
    }

    // 看二分搜索树中是否包含元素e
    public boolean contains(E e){
        return contains(root, e);
    }

    // 看以node为根的二分搜索树中是否包含元素e, 递归算法
    private boolean contains(Node node, E e){

        if(node == null)
            return false;

        if(e.compareTo(node.e) == 0)
            return true;
        else if(e.compareTo(node.e) < 0)
            return contains(node.left, e);
        else // e.compareTo(node.e) > 0
            return contains(node.right, e);
    }
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

二分搜索树的遍历

树的遍历方式分为：深度优先遍历和广度优先遍历

遍历操作就是把所有节点都访问一遍
在线性结构下，遍历是极其容易的
访问的原因和业务相关
在树结构下，也没那么难：）

深度优先遍历：（具体来说是根据 根节点的遍历顺序）的遍历有三种遍历方式：
前序遍历、中序遍历、后序遍历

对于树的遍历，其实就是：在每个节点遍历三次（顺序为从左至右，下图由三个紫色的点表示）

针对下图的二分搜索树，根据节点的遍历顺序可以如下：1~21的顺序

前序遍历：
- 最自然的遍历方式
- 最常用的遍历方式

```
顺序为：根节点-->左节点-->右节点，
1
```
（可以看作是当遍历到节点中最左边的点时可以读取节点中的数据）
顺序表示：
1 -> 2-> 3-> 4-> 5-> 6-> 7-> 8-> 9-> 10-> 11-> 12-> 13-> 14-> 15-> 16-> 17-> 18-> 19-> 20-> 21

根据前序遍历对上图的二分搜索树进行遍历得到结果如下：
在这里插入图片描述

中序遍历：
- 二分搜索树的中序遍历结果是顺序的
- 其顺序为：左节点–>根节点–>右节点
（可以看作是当遍历到节点中中间的点时可以读取节点中的数据）
顺序表示：
1 -> 2-> 3-> 4-> 5-> 6-> 7-> 8-> 9-> 10-> 11-> 12-> 13-> 14-> 15-> 16-> 17-> 18-> 19-> 20-> 21
后序遍历：
- 后序遍历的⼀一个应用：为二分搜索树释放内存
- 其顺序为：左节点–>右节点–>根节点
（可以看作是当遍历到节点中最右的点时可以读取节点中的数据）
顺序表示：

1 -> 2-> 3-> 4-> 5-> 6-> 7-> 8-> 9-> 10-> 11-> 12-> 13-> 14-> 15-> 16-> 17-> 18-> 19-> 20-> 21

前中后序遍历在二叉树中代码的实现

此处的代码实现都运用了递归的算法，非递归的方法也可以实现三种遍历，在此不再赘述，可以放在后面可以让读者自行研究

公共打印方法

     @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        generateBSTString(root, 0, res);
        return res.toString();
    }

    // 生成以node为根节点，深度为depth的描述二叉树的字符串
    private void generateBSTString(Node node, int depth, StringBuilder res){

        if(node == null){
            res.append(generateDepthString(depth) + "null\n");
            return;
        }

        res.append(generateDepthString(depth) + node.e + "\n");
        generateBSTString(node.left, depth + 1, res);
        generateBSTString(node.right, depth + 1, res);
    }

    private String generateDepthString(int depth){
        StringBuilder res = new StringBuilder();
        for(int i = 0 ; i < depth ; i ++)
            res.append("--");
        return res.toString();
    }
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

         以此二分搜索树为例
        /
        //      5      //
        //    /   \    //
        //   3    6    //
        //  / \    \   //
        // 2  4     8  //
        /
1
2
3
4
5
6
7
8

前序遍历：

    // 二分搜索树的前序遍历
    public void preOrder(){
        preOrder(root);
    }

    // 前序遍历以node为根的二分搜索树, 递归算法
    private void preOrder(Node node){
        if(node == null)
            return;

        System.out.println(node.e);
        preOrder(node.left);
        preOrder(node.right);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

//测试类
public class Main {
    public static void main(String[] args) {
        BST<Integer> bst = new BST<>();
        int[] nums = {5, 3, 6, 8, 4, 2};
        for(int num: nums)
            bst.add(num);
        System.out.println();
        System.out.println(bst);
    }
    //打印结果：
    5
	--3
	----2
	------null
	------null
	----4
	------null
	------null	
	--6
	----null
	----8
	------null
	------null
}
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

中序遍历

    // 二分搜索树的中序遍历
    public void inOrder(){
        inOrder(root);
    }

    // 中序遍历以node为根的二分搜索树, 递归算法
    private void inOrder(Node node){
        if(node == null)
            return;

        inOrder(node.left);
        System.out.println(node.e);
        inOrder(node.right);
    } 
1
2
3
4
5
6
7
8
9
10
11
12
13
14

后序遍历

    // 二分搜索树的后序遍历
    public void postOrder(){
        postOrder(root);
    }

    // 后序遍历以node为根的二分搜索树, 递归算法
    private void postOrder(Node node){
        if(node == null)
            return;

        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.e);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

非递归的前中后序的遍历

//前序遍历
public void preOrderNR(){

        if(root == null)
            return;

        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            Node cur = stack.pop();
            System.out.println(cur.e);

            if(cur.right != null)
                stack.push(cur.right);
            if(cur.left != null)
                stack.push(cur.left);
        }
    } 

//层序遍历
    public void levelOrder(){

        if(root == null)
            return;

        Queue<Node> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            Node cur = q.remove();
            System.out.println(cur.e);

            if(cur.left != null)
                q.add(cur.left);
            if(cur.right != null)
                q.add(cur.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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/274939?site