数据结构之二叉查找树Java泛型版

数据结构之二叉查找树Java泛型版

什么是二叉查找树

二叉查找树是父节点的权值比其左子树的权值大又比其右子树的权值小的二叉树。二叉查找树可递归生成，并且每一颗小子树都是二叉查找树。根据二叉查找树的特点对其进行中序遍历会得到一串有序的序列，故又称二叉查找树为二叉排序树。

二叉查找树的查找发挥了二叉树的二叉的优势，并且二叉查找树适合对原序列进行插入和删除操作，原始的二分查找是在数组中进行查找操作不适合进行插入和删除操作。

例如以下的树就是二叉查找树：

Java版的二叉树在遍历时细节

在遍历二叉树的时候，因为Java没有指针，所以遍历函数一定要传参数，不能像C++一样可以直接使用this指针来直接操作。

• C++版的遍历（中序遍历）

//函数实现
void BSTree::show_mid() {
    if (this == nullptr) return;
    lchild->show_mid();
    cout << this->key << ' ';
    rchild->show_mid();
}
//函数调用
tree->show_mid();
1
2
3
4
5
6
7
8
9

• Java版的遍历（中序遍历）

public void show_mid(BSTree<Ty> tree) {
    if (tree == null) return;
    show_mid(tree.lchild);
    System.out.print(tree.key + " ");
    show_mid(tree.rchild);
}
1
2
3
4
5
6

本文章使用泛型来实现，为了方便关键字的比较，所以未知类型Ty必须继承于Comparable.

开始封装Java版二叉查找树

二叉查找树的基本描述：

public class BSTree<Ty extends Comparable<Ty> > {
    private Ty key;
    private BSTree<Ty> lchild;
    private BSTree<Ty> rchild;
}
1
2
3
4
5

构造方法：

public BSTree(Ty key, BSTree<Ty> lchild, BSTree<Ty> rchild) {
    this.key = key;
    this.lchild = lchild;
    this.rchild = rchild;
}

public BSTree(Ty key) {
    this(key, null, null);
}
1
2
3
4
5
6
7
8
9

二叉树遍历：

    private void show_pre(BSTree<Ty> tree) {
        if (tree == null) return;
        System.out.print(tree.key + " ");
        show_pre(tree.lchild);
        show_pre(tree.rchild);
    }

    public void show_pre() {
        this.show_pre(this);
    }

    private void show_mid(BSTree<Ty> tree) {
        if (tree == null) return;
        show_mid(tree.lchild);
        System.out.print(tree.key + " ");
        show_mid(tree.rchild);
    }

    public void show_mid() {
        this.show_mid(this);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

发现笔者会多写一些函数，这些函数的作用就是可以在调用的使用少传一些参数，因为笔者比较习惯C++的风格。如果不想多写，那就可以不写缺省的那块，然后把权限打开，外界就可以访问得到。

二叉查找树的插入：

如果当前树是空树，就直接申请一个节点将要插入进来的数据赋值给关键字即可。

如果当前树不是空树，就依次使用要插入进来的数据和当前节点的关键字进行比较，小了就往左边走继续比较，大了就往右边走继续比较，直到走到空的位置，就申请一个节点的空间进行关键字赋值。因为Java的参数传递是值传递，所以记得返回根节点回去，不然就做了无用功。

	//递归写法
	private BSTree<Ty> insertNode(BSTree<Ty> tree, Ty key) {
        if (tree == null) return new BSTree<Ty>(key);
        if (key.compareTo(tree.key) < 0) {
            tree.lchild = insertNode(tree.lchild, key);
        } else {
            tree.rchild = insertNode(tree.rchild, key);
        }
        return tree;
    }

    public void insertNode(Ty key) {
        this.insertNode(this, key);
    }    

	//非递归写法
    public BSTree<Ty> insertNode2(BSTree<Ty> tree, Ty key) {
        if (tree == null) return new BSTree<Ty>(key);
        BSTree<Ty> pMove = tree;
        BSTree<Ty> parent = tree;
        while (pMove != null) {
            parent = pMove;
            pMove = key.compareTo(pMove.key) < 0 ? pMove.lchild : pMove.rchild;
        }
        if (key.compareTo(parent.key) < 0) {
            parent.lchild = new BSTree<Ty>(key);
        } else {
            parent.rchild = new BSTree<Ty>(key);
        }
        return tree;
    }

    public void insertNode2(Ty key) {
        this.insertNode2(this,key);
    }
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

二叉查找树的删除：

因为使用循环来写的话就太麻烦了，使用递归的写法结构比较清晰。

如果当前树是空树就直接结束。

如果当前树不是空树就比较要删除的数据和当前节点的关键字进行比较，小了就往左边继续找，大了就往右边继续找，直到遍历完了都没找到或者是找到了相等的关键字，就将其删除出树。

在删除的时候也不是直接删除，而是找到key和当前节点的关键字的节点的左子树中最大的节点maxNode，然后将maxNode的关键字赋值给当前节点的关键字，这样就把当前节点的关键字覆盖掉（即把它删除了），然后就是再往maxNode的方向走把maxNode删掉。

这样做的好处就是不改动二叉查找树原本的基本结构，理解起来也比较好。

    private BSTree<Ty> findMaxNode(BSTree<Ty> tree) {
        while (tree.rchild != null) {
            tree = tree.rchild;
        }
        return tree;
    }
    
	private BSTree<Ty> deleteNode(BSTree<Ty> tree, Ty key) {
        if (tree == null) return null;
        int val = key.compareTo(tree.key);
        if (val < 0) {
            tree.lchild = deleteNode(tree.lchild, key);
        } else if (val > 0) {
            tree.rchild = deleteNode(tree.rchild, key);
        } else {
            if (tree.lchild != null && tree.rchild != null) {
                BSTree<Ty> maxNode = findMaxNode(tree.lchild);
                tree.key = maxNode.key;
                tree.lchild = deleteNode(tree.lchild, maxNode.key);
            } else {
                tree = tree.lchild != null ? tree.lchild : tree.rchild;
            }
        }
        return tree;
    }

    public void deleteNode(Ty key) {
        this.deleteNode(this, key);
    }
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

在二叉查找树中查找数据：

其实在实现插入和删除的时候已经间接的实现了查找的功能。就不多说了，直接看代码就好，会发现似曾相识。

    //递归写法
    public BSTree<Ty> searchNode(BSTree<Ty> tree, Ty key) {
        if (tree == null) return null;
        int val = key.compareTo(tree.key);
        if (val < 0) return searchNode(tree.lchild, key);
        else if (val > 0) return searchNode(tree.rchild, key);
        else return tree;
    }

    //非递归写法
    public BSTree<Ty> searchNode2(BSTree<Ty> tree, Ty key) {
        BSTree<Ty> pMove = tree;
        while (pMove != null && !key.equals(pMove.key))
            pMove = key.compareTo(pMove.key) < 0 ? pMove.lchild : pMove.rchild;
        return pMove;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

主函数简单测试一下：

public class Main {
    public static void main(String[] args) {
        int arr[] = {5, 4, 1, 3, 0, 2, 9, 8, 7, 6};
        BSTree<Integer> tree = new BSTree<>(arr[0]);
        for (int i = 1; i < arr.length; i++) {
            tree.insertNode(arr[i]);
        }
        tree.show_mid();
        tree.deleteNode(5);
        System.out.println("\n---------------------------------------");
        tree.show_mid();
        int key = 7;
        BSTree<Integer> node = tree.searchNode2(tree, key);
        if (node == null) {
            System.out.println("\n找不到" + key);
        } else {
            System.out.println("\n在二叉树中找到" + key);
        }
        System.out.println("还原二叉树:");
        System.out.println("\n前序遍历:");
        tree.show_pre();
        System.out.println("\n中序遍历:");
        tree.show_mid();
    }
}

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

输出结果：

0 1 2 3 4 5 6 7 8 9 
---------------------------------------
0 1 2 3 4 6 7 8 9 
在二叉树中找到7
还原二叉树:

前序遍历:
4 1 0 3 2 9 8 7 6 
中序遍历:
0 1 2 3 4 6 7 8 9 
1
2
3
4
5
6
7
8
9
10

还原二叉查找树的样子：