二叉搜索树详解（Java实现）

阳光穿透心脏的1/2处 2021-06-10 20:39 413阅读 0赞

## 二叉搜索树定义[\#][Link 1] ##

--------------------

二叉搜索树，是指一棵空树或者具有下列性质的二叉树：

1.  若任意节点的左子树不空，则**左子树**上所有节点的值均**小于**它的**根节点**的值；
2.  若任意节点的右子树不空，则**右子树**上所有节点的值均**大于**它的**根节点**的值；
3.  任意节点的左，右子树也分别为二叉搜索树；
4.  **没有键值相等的节点。**

## **用Java来表示二叉树**[\#][Link 2] ##

public class BinarySearchTree
    { // 二叉搜索树类
        private class Node
        { // 节点类
            int data; // 数据域
            Node right; // 右子树
            Node left; // 左子树
        }
    
        private Node root; // 树根节点
    }

首先，需要一个节点对象的类。这个对象包含数据域和指向节点的两个子节点的引用。

其次，需要一个树对象的类。这个对象包含一个根节点root。

## 创建树（insert）[\#][Link 3] ##

public void insert(int key)
        {    
            Node p=new Node(); //待插入的节点
            p.data=key;
            
            if(root==null)
            {
                root=p;
            }
            else
            {
                Node parent=new Node();
                Node current=root;
                while(true)
                {
                    parent=current;
                    if(key>current.data)    
                    {
                        current=current.right; // 右子树
                        if(current==null)
                        {
                            parent.right=p;
                            return;
                        }
                    }
                    else //本程序没有做key出现相等情况的处理，暂且假设用户插入的节点值都不同
                    {
                        current=current.left; // 左子树
                        if(current==null)
                        {
                            parent.left=p;
                            return;
                        }
                    }
                }
            }
        }

创建树的时候，主要用到了parent，current来记录要插入节点的位置。哪么怎么检验自己是否正确地创建了一颗二叉搜索树呢，我们通过**遍历**来输出各个节点的值

## 遍历树（travel）[\#][Link 4] ##

遍历指的是按照某种特定的次序来访问二叉搜索树中的每个节点，主要有三种遍历的方法：

1.  前序遍历，“中左右”
2.  中序遍历，“左中右”
3.  后续遍历，“左右中”

上面的口诀“中左右”表示的含义是，先访问根节点，再访问左子，最后访问右子。举个例子：

[![format_png][]][format_png 1]

*  前序遍历：39 24 23 30 64 53 60
 *  中序遍历：23 24 30 39 53 60 64
 *  后序遍历：23 30 24 60 53 64 39

你会发现，按照中序遍历的规则将一个二叉搜索树输入，结果为按照正序排列。

public void preOrder(Node root)
        { // 前序遍历,"中左右"
            if (root != null)
            {
                System.out.print(root.data + " ");
                preOrder(root.left);
                preOrder(root.right);
            }
        }
    
        public void inOrder(Node root)
        { // 中序遍历,"左中右"
            if (root != null)
            {
                inOrder(root.left);
                System.out.print(root.data + " ");
                inOrder(root.right);
            }
        }
    
        public void postOrder(Node root)
        { // 后序遍历,"左右中"
            if (root != null)
            {
                postOrder(root.left);
                postOrder(root.right);
                System.out.print(root.data + " ");
            }
        }
    
        public void traverse(int traverseType)
        {    // 选择以何种方式遍历
            switch (traverseType)
            {
            case 1:
                System.out.print("preOrder traversal ");
                preOrder(root);
                System.out.println();
                break;
            case 2:
                System.out.print("inOrder traversal ");
                inOrder(root);
                System.out.println();
                break;
            case 3:
                System.out.print("postOrder traversal ");
                postOrder(root);
                System.out.println();
                break;
            }
        }

以上的代码采用递归的方式实现三种遍历，为了方便我们使用，又写了一个traverse函数来实现选择哪种方式进行树的遍历。

这会儿就可以写单元测试了，我们首先创建一个二叉搜索树，然后分别使用“前序”，“中序”，“后序”来遍历输出树的所有节点。

public static void main(String[] args)    //unit test
        {    
            BinarySearchTree tree=new BinarySearchTree();
            
            tree.insert(39);
            tree.insert(24);
            tree.insert(64);
            tree.insert(23);
            tree.insert(30);
            tree.insert(53);
            tree.insert(60);
            
            tree.traverse(1);
            tree.traverse(2);
            tree.traverse(3);
        }

运行该单元测试，可以看到如下的结果：

[![format_png 2][]][format_png 2 1]

## 查找节点（find）[\#][Link 5] ##

public Node find(int key)
        { // 从树中按照关键值查找元素
            Node current = root;
            while (current.data != key)
            {
                if (key > current.data)
                    current = current.right;
                else
                    current = current.left;
                if (current == null) return null;
            }
            return current;
        }
        
        public void show(Node node)
        {    //输出节点的数据域
            if(node!=null)
                System.out.println(node.data);
            else
                System.out.println("null");
        }

查找节点比较简单，如果找到节点则返回该节点，否则返回null。为了方便在控制台输出，我们有添加了一个show函数，用来输出节点的数据域。

## 删除节点（delete）[\#][Link 6] ##

删除节点是二叉搜索树中，最复杂的一种操作，但是也不是特别难，我们分类讨论：

*  要删除节点有**零个孩子**，即叶子节点

[![format_png 3][]][format_png 3 1]

如图所示，只需要将parent.left(或者是parent.right)设置为null，然后Java垃圾自动回收机制会自动删除current节点。

*  要删除节点有**一个孩子**

[![format_png 4][]][format_png 4 1]

如图所示，只需要将parent.left(或者是parent.right)设置为curren.right(或者是current.left)即可。

[![aHR0cHM6Ly9pbWcyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTQ1OTE3OS8yMDE5MDUvMTQ1OTE3OS0yMDE5MDUwNjEyMDM0NzM5MC0xOTAwNTA0MTguZ2lm][]][aHR0cHM6Ly9pbWcyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTQ1OTE3OS8yMDE5MDUvMTQ1OTE3OS0yMDE5MDUwNjEyMDM0NzM5MC0xOTAwNTA0MTguZ2lm 1]

*  要删除节点有**两个孩子**

这种情况比较复杂，首先我们引入**后继节点**的概念，如果将一棵二叉树按照中序周游的方式输出，则任一节点的下一个节点就是该节点的后继节点。例如：上图中24的后继节点为25，64的后继节点为70.找到后继节点以后，问题就变得简单了，分为两种情况：

1.**后继节点为待删除节点的右子**，只需要将curren用successor替换即可，注意处理好current.left和successor.right.

注意：这种情况下，successor一定没有左孩子，一但它有左孩子，哪它必然不是current的后继节点。

[![format_png 5][]][format_png 5 1]

[![aHR0cHM6Ly9pbWcyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTQ1OTE3OS8yMDE5MDUvMTQ1OTE3OS0yMDE5MDUwNjEzMTAxMzU3NC04MTg1NDUyMDIuZ2lm][]][aHR0cHM6Ly9pbWcyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTQ1OTE3OS8yMDE5MDUvMTQ1OTE3OS0yMDE5MDUwNjEzMTAxMzU3NC04MTg1NDUyMDIuZ2lm 1]

2.**后继节点为待删除结点的右孩子的左子树**，这种情况稍微复杂点，请看动态图片演示。

[![format_png 6][]][format_png 6 1]

[![aHR0cHM6Ly9pbWcyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTQ1OTE3OS8yMDE5MDUvMTQ1OTE3OS0yMDE5MDUwNjEzMTYzNTM2OC0xNzgxNTAyMjcxLmdpZg][]][aHR0cHM6Ly9pbWcyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTQ1OTE3OS8yMDE5MDUvMTQ1OTE3OS0yMDE5MDUwNjEzMTYzNTM2OC0xNzgxNTAyMjcxLmdpZg 1]

算法的步骤是：

1.  successorParent.left=successor.right
2.  successor.left=current.left
3.  parent.left=seccessor

弄懂原理后，我们来看具体的代码实现：

private Node getSuccessor(Node delNode)    //寻找要删除节点的中序后继结点
        {
            Node successorParent=delNode;
            Node successor=delNode;
            Node current=delNode.right;
            
            //用来寻找后继结点
            while(current!=null)
            {
                successorParent=successor;
                successor=current;
                current=current.left;
            }
            
            //如果后继结点为要删除结点的右子树的左子，需要预先调整一下要删除结点的右子树
            if(successor!=delNode.right)
            {
                successorParent.left=successor.right;
                successor.right=delNode.right;
            }
            return successor;
        }
        
        public boolean delete(int key) // 删除结点
        {
            Node current = root;
            Node parent = new Node();
            boolean isRightChild = true;
            while (current.data != key)
            {
                parent = current;
                if (key > current.data)
                {
                    current = current.right;
                    isRightChild = true;
                }
                else
                {
                    current = current.left;
                    isRightChild = false;
                }
                if (current == null) return false; // 没有找到要删除的结点
            }
            // 此时current就是要删除的结点,parent为其父结点
            // 要删除结点为叶子结点
            if (current.right == null && current.left == null) 
            {
                if (current == root)
                {
                    root = null; // 整棵树清空
                }
                else
                {
                    if (isRightChild)
                        parent.right = null;
                    else
                        parent.left = null;
                }
                return true;
            }
            //要删除结点有一个子结点
            else if(current.left==null)
            {
                if(current==root)
                    root=current.right;
                else if(isRightChild)
                    parent.right=current.right;
                else
                    parent.left=current.right;
                return true;
            }
            else if(current.right==null)
            {
                if(current==root)
                    root=current.left;
                else if(isRightChild)
                    parent.right=current.left;
                else
                    parent.left=current.left;
                return true;
            }
            //要删除结点有两个子结点
            else 
            {
                Node successor=getSuccessor(current);    //找到要删除结点的后继结点
                
                if(current==root)
                    root=successor;
                else if(isRightChild)
                    parent.right=successor;
                else
                    parent.left=successor;
                
                successor.left=current.left;
                return true;
            }
        }

大家注意哪个私有函数getSuccessor的功能，它不仅仅是用来找后继结点的。

## 总结[\#][Link 7] ##

二叉搜索树其实不是特别难，理解以后，多练习几次，应该可以掌握。以下是全部的代码：

package org.yahuian;
    
    public class BinarySearchTree
    { // 二叉搜索树类
        private class Node
        { // 节点类
            int data; // 数据域
            Node right; // 右子树
            Node left; // 左子树
        }
    
        private Node root; // 树根节点
    
        public void insert(int key)
        {
            Node p = new Node(); // 待插入的节点
            p.data = key;
    
            if (root == null)
            {
                root = p;
            }
            else
            {
                Node parent = new Node();
                Node current = root;
                while (true)
                {
                    parent = current;
                    if (key > current.data)
                    {
                        current = current.right; // 右子树
                        if (current == null)
                        {
                            parent.right = p;
                            return;
                        }
                    }
                    else // 本程序没有做key出现相等情况的处理，暂且假设用户插入的节点值都不同
                    {
                        current = current.left; // 左子树
                        if (current == null)
                        {
                            parent.left = p;
                            return;
                        }
                    }
                }
            }
        }
    
        public void preOrder(Node root)
        { // 前序遍历,"中左右"
            if (root != null)
            {
                System.out.print(root.data + " ");
                preOrder(root.left);
                preOrder(root.right);
            }
        }
    
        public void inOrder(Node root)
        { // 中序遍历,"左中右"
            if (root != null)
            {
                inOrder(root.left);
                System.out.print(root.data + " ");
                inOrder(root.right);
            }
        }
    
        public void postOrder(Node root)
        { // 后序遍历,"左右中"
            if (root != null)
            {
                postOrder(root.left);
                postOrder(root.right);
                System.out.print(root.data + " ");
            }
        }
    
        public void traverse(int traverseType)
        { // 选择以何种方式遍历
            switch (traverseType)
            {
            case 1:
                System.out.print("preOrder traversal ");
                preOrder(root);
                System.out.println();
                break;
            case 2:
                System.out.print("inOrder traversal ");
                inOrder(root);
                System.out.println();
                break;
            case 3:
                System.out.print("postOrder traversal ");
                postOrder(root);
                System.out.println();
                break;
            }
        }
    
        public Node find(int key)
        { // 从树中按照关键值查找元素
            Node current = root;
            while (current.data != key)
            {
                if (key > current.data)
                    current = current.right;
                else
                    current = current.left;
                if (current == null) return null;
            }
            return current;
        }
        
        public void show(Node node)
        {    //输出节点的数据域
            if(node!=null)
                System.out.println(node.data);
            else
                System.out.println("null");
        }
        
        private Node getSuccessor(Node delNode)    //寻找要删除节点的中序后继结点
        {
            Node successorParent=delNode;
            Node successor=delNode;
            Node current=delNode.right;
            
            //用来寻找后继结点
            while(current!=null)
            {
                successorParent=successor;
                successor=current;
                current=current.left;
            }
            
            //如果后继结点为要删除结点的右子树的左子，需要预先调整一下要删除结点的右子树
            if(successor!=delNode.right)
            {
                successorParent.left=successor.right;
                successor.right=delNode.right;
            }
            return successor;
        }
        
        public boolean delete(int key) // 删除结点
        {
            Node current = root;
            Node parent = new Node();
            boolean isRightChild = true;
            while (current.data != key)
            {
                parent = current;
                if (key > current.data)
                {
                    current = current.right;
                    isRightChild = true;
                }
                else
                {
                    current = current.left;
                    isRightChild = false;
                }
                if (current == null) return false; // 没有找到要删除的结点
            }
            // 此时current就是要删除的结点,parent为其父结点
            // 要删除结点为叶子结点
            if (current.right == null && current.left == null) 
            {
                if (current == root)
                {
                    root = null; // 整棵树清空
                }
                else
                {
                    if (isRightChild)
                        parent.right = null;
                    else
                        parent.left = null;
                }
                return true;
            }
            //要删除结点有一个子结点
            else if(current.left==null)
            {
                if(current==root)
                    root=current.right;
                else if(isRightChild)
                    parent.right=current.right;
                else
                    parent.left=current.right;
                return true;
            }
            else if(current.right==null)
            {
                if(current==root)
                    root=current.left;
                else if(isRightChild)
                    parent.right=current.left;
                else
                    parent.left=current.left;
                return true;
            }
            //要删除结点有两个子结点
            else 
            {
                Node successor=getSuccessor(current);    //找到要删除结点的后继结点
                
                if(current==root)
                    root=successor;
                else if(isRightChild)
                    parent.right=successor;
                else
                    parent.left=successor;
                
                successor.left=current.left;
                return true;
            }
        }
        
        public static void main(String[] args) // unit test
        {
            BinarySearchTree tree = new BinarySearchTree();
    
            tree.insert(39);
            tree.insert(24);
            tree.insert(64);
            tree.insert(23);
            tree.insert(30);
            tree.insert(53);
            tree.insert(60);
    
            tree.traverse(1);
            tree.traverse(2);
            tree.traverse(3);
            
            tree.show(tree.find(23));
            tree.show(tree.find(60));
            tree.show(tree.find(64));
            
            tree.delete(23);
            tree.delete(60);
            tree.delete(64);
            
            tree.show(tree.find(23));
            tree.show(tree.find(60));
            tree.show(tree.find(64));
        }
    }

--------------------

动态图片来自于：[https://visualgo.net/en/bst][https_visualgo.net_en_bst]

[Link 1]: https://www.cnblogs.com/yahuian/p/10813614.html#4003703296
[Link 2]: https://www.cnblogs.com/yahuian/p/10813614.html#410340401
[Link 3]: https://www.cnblogs.com/yahuian/p/10813614.html#3965203171
[Link 4]: https://www.cnblogs.com/yahuian/p/10813614.html#3625626127
[format_png]: /images/20210527/20a3cd6121ad4c49bc1166ca84c62b35.png
[format_png 1]: https://img2018.cnblogs.com/blog/1459179/201905/1459179-20190505154256695-637397729.png
[format_png 2]: /images/20210527/7290d4b190e844f291f3fdd2dba2df03.png
[format_png 2 1]: https://img2018.cnblogs.com/blog/1459179/201905/1459179-20190505161033208-1864500540.png
[Link 5]: https://www.cnblogs.com/yahuian/p/10813614.html#3699878923
[Link 6]: https://www.cnblogs.com/yahuian/p/10813614.html#705554173
[format_png 3]: /images/20210527/5c514217746641b08071308e9af6748e.png
[format_png 3 1]: https://img2018.cnblogs.com/blog/1459179/201905/1459179-20190506103928855-819858787.png
[format_png 4]: /images/20210527/0b92605f276a4d0bbc24d0f8df7260ce.png
[format_png 4 1]: https://img2018.cnblogs.com/blog/1459179/201905/1459179-20190506104753788-110670825.png
[aHR0cHM6Ly9pbWcyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTQ1OTE3OS8yMDE5MDUvMTQ1OTE3OS0yMDE5MDUwNjEyMDM0NzM5MC0xOTAwNTA0MTguZ2lm]: /images/20210527/3d2b154f2ba84b2ba93183107317fa3a.png
[aHR0cHM6Ly9pbWcyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTQ1OTE3OS8yMDE5MDUvMTQ1OTE3OS0yMDE5MDUwNjEyMDM0NzM5MC0xOTAwNTA0MTguZ2lm 1]: https://img2018.cnblogs.com/blog/1459179/201905/1459179-20190506120347390-190050418.gif
[format_png 5]: /images/20210527/0bbcc5de889646a598187d2aecbf984d.png
[format_png 5 1]: https://img2018.cnblogs.com/blog/1459179/201905/1459179-20190506130426071-932016809.png
[aHR0cHM6Ly9pbWcyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTQ1OTE3OS8yMDE5MDUvMTQ1OTE3OS0yMDE5MDUwNjEzMTAxMzU3NC04MTg1NDUyMDIuZ2lm]: /images/20210527/dcf6d389be064dd79fe7d66b36eb83de.png
[aHR0cHM6Ly9pbWcyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTQ1OTE3OS8yMDE5MDUvMTQ1OTE3OS0yMDE5MDUwNjEzMTAxMzU3NC04MTg1NDUyMDIuZ2lm 1]: https://img2018.cnblogs.com/blog/1459179/201905/1459179-20190506131013574-818545202.gif
[format_png 6]: /images/20210527/e619dd3b5f07448c89c67be85dc6cdb5.png
[format_png 6 1]: https://img2018.cnblogs.com/blog/1459179/201905/1459179-20190506131255284-111280623.png
[aHR0cHM6Ly9pbWcyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTQ1OTE3OS8yMDE5MDUvMTQ1OTE3OS0yMDE5MDUwNjEzMTYzNTM2OC0xNzgxNTAyMjcxLmdpZg]: /images/20210527/317547e7ad2641e0aacc6d0fa52000a1.png
[aHR0cHM6Ly9pbWcyMDE4LmNuYmxvZ3MuY29tL2Jsb2cvMTQ1OTE3OS8yMDE5MDUvMTQ1OTE3OS0yMDE5MDUwNjEzMTYzNTM2OC0xNzgxNTAyMjcxLmdpZg 1]: https://img2018.cnblogs.com/blog/1459179/201905/1459179-20190506131635368-1781502271.gif
[Link 7]: https://www.cnblogs.com/yahuian/p/10813614.html#960131183
[https_visualgo.net_en_bst]: https://visualgo.net/en/bst