数据结构之二叉查找树及Java实现

た入场券 2022-05-27 12:16 213阅读 0赞

## 一、二叉查找树的介绍 ##

二叉查找树(Binary Search Tree)，又被称为二叉搜索树或二叉排序树，是一种特殊的二叉树，利用它可以很方便的对树中节点进行排序和检索。  
二叉查找树需要满足以下的性质：

*  若它的左子树不为空，则左子树上的所有节点的值都小于根节点的值
 *  若它的右子树不为空，则右子树上的所有节点的值都大于根节点的值
 *  它的左、右子树也都是二叉查找树

对于二叉查找树，按照中序遍历（左根右）就可以得到由小到大的序列。

## 二、二叉查找树的实现 ##

二叉查找树与基于链表的二叉树创建方法类似，不同之处在于添加了一个父节点，也就是说采用二叉树的三叉链表存储方法，每个节点包括left、right和parent指针，用于表示该节点的左右节点和父节点。二叉查找树主要需要实现两个功能：

*  添加元素：添加元素后二叉树依然有序，依然是二叉查找树。
 *  删除元素：删除完成后二叉树依然有序，依然是二叉查找树。

1.添加元素

已知一个关键字值为value的结点，若将其插入到二叉查找树中，只要保证插入后仍符合二叉查找树的定义即可。插入可以用下面的方法进行：

（1）若二叉排序树是空树，则value成为二叉排序树的根；  
（2）若二叉排序树非空，则将value与二叉排序树的根进行比较。如果value的值小于根结点的值，则将左节点作为新的当前节点，如果value的值大于根结点的值，则将右节点作为新的当前节点。  
（3）重复步骤2，直到找到合适的插入位置。

2.删除元素

当程序从排序二叉树中删除一个节点之后，为了让它依然保持为排序二叉树，程序必须对该排序二叉树进行维护。维护可分为如下几种情况：

（1）若被删除的节点是叶子节点，则只需将它从其父节点中删除即可。  
（2）如果待删除节点左子树存在右子树不存在，或者左子树不存在右子树存在，直接将其子树中存在的一边候补上来即可。  
（3）若被删除节点 P 的左、右子树均非空，有两种做法：

*  将PL设为P的父节点Q的左或右子节点（取决于P是其父节点Q的左或右子节点），将PR设为P节点的中序前驱节点S的右子节点（S是PL最右下的节点，也就是PL子树中最大的节点）。
 *  以P节点的中序前驱或后继代替P所指节点，然后再从原排序二叉树中删去中序前驱或后继节点。（也就是，用大于P的最小节点或小于P的最大节点代替P节点）。

实现代码如下所示：

import java.util.ArrayList;
    import java.util.List;
    
    
    public class SortTree {
        
    
        class Node{
            private int data;
            private Node parent;
            private Node left;
            private Node right;
            public Node(int value){
                this.data = value;
                this.parent = null;
                this.left = null;
                this.right = null;
            }
        }
        private Node root = null;
        /**
         * 返回根节点
         * @return
         */
        public Node getRoot(){
            return root;
        }
        /**
         * 判断是否为空
         * @return
         */
        public boolean isEmpty(){
            return root==null;
        }
        /**
         * 返回树的深度
         * @return
         */
        public int deep(){
            return deep(root);
        }
        private int deep(Node n){
            if(n == null){
                return 0;
            }
            if(n.left==null&&n.right==null){
                return 1;
            }
            //递归方式
            int deepLeft = deep(n.left);
            int deepRight = deep(n.right);
            return deepLeft>deepRight?deepLeft:deepRight;
        }
        //比较两个值的大小，用于插入和删除操作
        public int compare(int a,int b){
            return a>b?1:-1;
        }
        /**
         * 添加新节点
         * @param value 新节点的值
         * @return 返回是否成功
         */
        public boolean add(int value){
            //新节点newNode初始化
            Node newNode = new Node(value);
            //如果root为空，则新节点为root节点
            if(root == null){
                root = newNode;
                return true;
            }
            Node current = root;
            Node parent = null;
            int cmp = 0;
            //遍历找到合适的插入节点位置
            do{
                parent = current;
                cmp = compare(value,current.data);
                if(cmp == 1){
                    current = current.right;
                }
                else{
                    current = current.left;
                }
            }
            while(current!=null);
            //设置新节点
            if(cmp == 1){
                parent.right = newNode;
                newNode.parent = parent;
            }
            else{
                parent.left = newNode;
                newNode.parent = parent;
            }
            return true;
        }
        /**
         * 找到某个值的节点，用于删除操作
         * @param value 目标节点的值
         * @return 返回节点
         */
        public Node findNode(int value){
            if(root == null){
                return null;
            }
            Node curr = root;
            while(curr!=null){
                if(value<curr.data){
                    curr = curr.left;
                }
                else if(value>curr.data){
                    curr = curr.right;
                }
                else{
                    return curr;
                }
            }
            return null;
        }
        public boolean del(int value){
            Node target = findNode(value);
            if(target == null){
                return false;
            }
            //如果删除的节点没有左节点也没有右节点
            if(target.left==null&&target.right==null){
                //如果节点为根节点
                if(target == root){
                    root = null;
                }
                else{
                    //要删除的节点为左节点
                    if(target == target.parent.left){
                        target.parent.left = null;
                    }
                    //要删除的节点为右节点
                    else{
                        target.parent.right = null;
                    }
                }
            }
            //如果删除的节点只有右节点
            if(target.left==null && target.right!=null){
                //要删除的节点为根节点
                if(target == root){
                    root = target.right;
                }
                else{
                    //要删除的节点为左节点
                    if(target == target.parent.left){
                        target.parent.left = target.right;
                    }
                    //要删除的节点为右节点
                    else{
                        target.parent.right = target.right;
                    }
                    target.right.parent = target.parent;
                }
            }
            //如果删除的节点只有左节点
            if(target.left!=null&&target.right==null){
                if(target == root){
                    root = root.left;
                }
                else{
                    if(target == target.parent.left){
                        target.parent.left = target.left;
                    }
                    else{
                        target.parent.right = target.left;
                    }
                    target.left.parent = target.parent;
                }
            }
            //如果删除的节点包含左节点和右节点
            //以P节点的中序前驱代替P所指节点，然后再从原排序二叉树中删去中序前驱节点，用大于P的最小节点代替P节点
            if(target.left!=null&&target.right!=null){
                //leftMaxNode用于保存左子树中最大的节点
                Node leftMaxNode = target.left;
                //遍历右节点，找到值最大的节点
                while(leftMaxNode.right!=null){
                    leftMaxNode = leftMaxNode.right;
                }
                //如果target.left没有右节点
                if(leftMaxNode == target.left){
                    leftMaxNode.parent.left = null;
    
                }
                //如果找到了最大的右节点
                else{
                    leftMaxNode.parent.right = null;
    
                }
                //左子树的最大节点指向目标节点的父节点
                leftMaxNode.parent = target.parent;
                if(target ==target.parent.left){
                    //如果目标节点为左节点，左节点指向leftMaxNode
                    target.parent.left = leftMaxNode;
                }
                else{
                    //如果目标节点为右节点，右节点指向leftMaxNode
                    target.parent.right = leftMaxNode;
                }
                //leftMaxNode替代target的位置
                leftMaxNode.left = target.left;
                leftMaxNode.right = target.right;
                //target置空
                target.parent = target.left = target.right = null;
            }
    
            return true;
        }
        /**
         * 中序遍历
         * @return 返回存储Node节点的list
         */
        public List<Node> inIterator(){
            return inIterator(root);
        }
        public List<Node> inIterator(Node n){
            List<Node> list = new ArrayList<Node>();
            //递归方式
            if(n.left!=null){
                list.addAll(inIterator(n.left));
            }
            list.add(n);
            if(n.right!=null){
                list.addAll(inIterator(n.right));
            }
            return list;
        }
    
        public static void main(String args[]){
            SortTree st = new SortTree();
            /**
             *                 1
             *                      8
             *                  5      10 
             *               2    7  9    11
             *                3  6         
             */
            st.add(1);
            st.add(8);
            st.add(5);
            st.add(2);
            st.add(7);
            st.add(10);
            st.add(9);
            st.add(11);
            st.add(6);
            st.add(3);
            st.del(10);
            List<SortTree.Node> inlist = new ArrayList<SortTree.Node>();
            inlist = st.inIterator();
            for(SortTree.Node n:inlist){
                System.out.print(n.data + " ");
            }
            System.out.println();
        }
    
    }

测试结果：

1 2 3 5 6 7 8 9 11