Java数据结构-树的应用-二叉查找树

痛定思痛。 2022-08-03 00:52 153阅读 0赞

#### 二叉查找树 ####

也叫二叉排序树。

对于树中的每个节点X，它的所有左子树中项的值小于X节点中的项，所有右子树中的项的值大于X的项。

需要实现的基本操作有：

1.**包含：**

判断某个元素是否包含在二叉查找树中，若存在则放回true，否则返回false。

具体操作步骤如下：

（1）.从根结点开始进行判断，根结点为空则直接结束返回false；

（2）.如果相等则直接结束返回true；如果大于根结点的值，则继续与根结点的右子树进行比较；如果小于根结点的值，则继续与根结点的左子树进行比较；

（3）.重复第（2）步操作，直至找到相等的元素返回true或者二叉树遍历结束也没找到则返回false。

2.**插入：**

注意在插入的时候需要判断该元素是否存在于二叉树中，即需要进行比较查找操作，若存在则不插入，否则则插入。

具体操作步骤如下：

（1）.从根结点开始进行判断，根结点为空则直接插入；

（2）.如果相等则直接结束，不进行插入；如果大于根结点的值，则继续与根结点的右子树进行比较；如果小于根结点的值，则继续与根结点的左子树进行比较；

（3）.一直进行第（2）步的循环，直至对应的结点为空，则直接将该元素对应的结点插入在此。

3.**删除：**

注意在删除的时候需要判断该元素是否存在于二叉树中，即需要进行比较查找操作，若不存在则不进行相关操作，直接返回，否则删除对应结点，然后调整二叉查找树的结点位置关系，返回。

具体操作如下：

（1）.从根结点开始进行判断，若根结点为空则直接无操作返回；

（2）.如果相等则直接删除该结点，然后进行相关结点调整，返回返回；如果大于根结点的值，则继续与根结点的右子树进行比较；如果小于根结点的值，则继续与根结点的左子树进行比较；

（3）.一直进行第（2）步的循环，直至相等条件出现进行第（2）步前面的操作，或者直至对应的二叉树为空也未出现相等的值，则直接无操作返回。

注意：上述说的进行相关结点调整是这样的，**删除结点的值为e的结点后需要找到以该结点为根结点的最小右子树或者最大左子树结点来替代该结点，即以该结点的前驱或者后继来替换**(前驱:是该节点的左子树中的最大节点;后继:是该节点的右子树中的最小节点)。

4.**最大：**

根据二叉查找树的性质：右子树的项比左子树的项的值大。

从根结点开始进行遍历，直至最右子树结点的出现，则该结点的值为该二叉查找树最大值。

5.**最小：**

同上述查找最大值一样，我们只要找到最左子树结点的值即可。

6.**遍历：**

同二叉树的遍历一样，可以进行前序遍历，中序遍历，后序遍历，层次遍历等。

注意中序遍历的结果为一个递增的序列。

此外还有查找前驱结点和后继结点等操作。

下面是我的Java实现方法。

package com.phn.tree;
    /**
     * @author 潘海南
     * @Email 1016593477@qq.com
     * @TODO 二叉查找树
     * @date 2015年7月27日
     */
    public class FOBinarySearchTree<E extends Comparable<E>> {
        //二叉查找树的根结点
        private FOBinaryTreeNode<E> root;
        /**
         * TODO 无参构造函数，初始化二叉排序树
         */
        public FOBinarySearchTree() {
            this.root = null;
        }
        /**
         * @TODO 输入元素e是否包含在该二叉排序树中
         * @param e 输入元素
         * @return true or false
         */
        public boolean contains(E e) {
            return this.contains2(e, root);
        }
        /**
         * @TODO 二叉排序树是否包含某个元素的具体实现
         * @param e 输入元素
         * @param node 树的根结点
         * @return true or false
         */
        private boolean contains2(E e, FOBinaryTreeNode<E> node) {
            if (node == null)
                return false;
            else {
                int result = e.compareTo(node.getE());
                if (result < 0) {
                    return contains2(e, node.getLeftChild());
                } else if (result > 0) {
                    return contains2(e, node.getRightChild());
                } else {
                    return true;
                }
            }
        }
        /**
         * @TODO 二叉排序树查找输入元素在树中的结点信息
         * @param e 输入元素
         * @return 该输入元素在树中的结点信息
         */
        public FOBinaryTreeNode<E> search(E e) {
            if (root == null) {
                throw new RuntimeException("该树为空！");
            }
            FOBinaryTreeNode<E> tempNode = root;
            while (tempNode != null) {
                int result = e.compareTo(tempNode.getE());
                if (result == 0) {
                    return tempNode;
                } else if (result < 0) {
                    tempNode = tempNode.getLeftChild();
                } else {
                    tempNode = tempNode.getRightChild();
                }
            }
            return null;
        }
        /**
         * @TODO 二叉排序树插入元素
         * @param e 需要插入的元素
         * @return true or false
         */
        public boolean add(E e) {
            if (root == null) {
                root = new FOBinaryTreeNode<E>();
                root.setE(e);
                return true;
            }
            FOBinaryTreeNode<E> tempInsertNode = root;
            FOBinaryTreeNode<E> insertParentNode = new FOBinaryTreeNode<E>();
            int result = 0;
            while (tempInsertNode != null) {
                insertParentNode = tempInsertNode;
                result = e.compareTo(tempInsertNode.getE());
                if (result < 0) {
                    tempInsertNode = tempInsertNode.getLeftChild();
                } else if (result > 0) {
                    tempInsertNode = tempInsertNode.getRightChild();
                } else {
                    return true;
                }
            }
            FOBinaryTreeNode<E> insertNode = new FOBinaryTreeNode<E>();
            insertNode.setE(e);
            insertNode.setParent(insertParentNode);
            int cmpResult = e.compareTo(insertParentNode.getE());
            if (cmpResult > 0) {
                insertParentNode.setRightChild(insertNode);
            } else {
                insertParentNode.setLeftChild(insertNode);
            }
            return true;
        }
        /**
         * @TODO 二叉排序树删除在数中的输入的元素e
         * @param e 将要删除的输入元素
         * @return true or false
         */
        public boolean remove(E e) {
            FOBinaryTreeNode<E> removeNode = this.search(e);
            if (removeNode == null) {
                return false;
            }
            FOBinaryTreeNode<E> preRemoveNode = this.findPreNode(removeNode);
            if (preRemoveNode != null) {
                removeByPreNode(removeNode, preRemoveNode);
                return true;
            }
            FOBinaryTreeNode<E> nextRemoveNode = this.findNextNode(removeNode);
            if (nextRemoveNode != null) {
                removeByNextNode(removeNode, nextRemoveNode);
                return true;
            }
            if (removeNode.getParent().getLeftChild() == removeNode) {
                removeNode.getParent().setLeftChild(null);
            } else {
                removeNode.getParent().setRightChild(null);
            }
            return true;
        }
        /**
         * @TODO 删除二叉排序树中的结点后将其前驱结点替代
         * @param removeNode 将要删除的结点
         * @param preRemoveNode 将要删除的结点的前驱结点
         */
        private void removeByPreNode(FOBinaryTreeNode<E> removeNode,
                FOBinaryTreeNode<E> preRemoveNode) {
            if (preRemoveNode.getLeftChild() != null) {
                preRemoveNode.getLeftChild().setParent(preRemoveNode.getParent());
                preRemoveNode.getParent().setRightChild(
                        preRemoveNode.getLeftChild());
            } else {
                preRemoveNode.getParent().setRightChild(null);
            }
            preRemoveNode.setParent(removeNode.getParent());
            if (removeNode.getParent().getLeftChild() == removeNode) {
                removeNode.getParent().setLeftChild(preRemoveNode);
            } else {
                removeNode.getParent().setRightChild(preRemoveNode);
            }
            preRemoveNode.setLeftChild(removeNode.getLeftChild());
            if (removeNode.getLeftChild() != null) {
                removeNode.getLeftChild().setParent(preRemoveNode);
            }
            preRemoveNode.setRightChild(removeNode.getRightChild());
            if (removeNode.getRightChild() != null) {
                removeNode.getRightChild().setParent(preRemoveNode);
            }
        }
        /**
         * @TODO 删除二叉排序树中的结点后将其后继结点替代
         * @param removeNode 将要删除的结点
         * @param nextRemoveNode 将要删除的结点的后继结点
         */
        private void removeByNextNode(FOBinaryTreeNode<E> removeNode,
                FOBinaryTreeNode<E> nextRemoveNode) {
            if (nextRemoveNode.getRightChild() != null) {
                nextRemoveNode.getRightChild()
                        .setParent(nextRemoveNode.getParent());
                nextRemoveNode.getParent().setLeftChild(
                        nextRemoveNode.getRightChild());
            } else {
                nextRemoveNode.getParent().setLeftChild(null);
            }
            nextRemoveNode.setParent(removeNode.getParent());
            if (removeNode.getParent().getLeftChild() == removeNode) {
                removeNode.getParent().setLeftChild(nextRemoveNode);
            } else {
                removeNode.getParent().setRightChild(nextRemoveNode);
            }
            nextRemoveNode.setLeftChild(removeNode.getLeftChild());
            if (removeNode.getLeftChild() != null) {
                removeNode.getLeftChild().setParent(nextRemoveNode);
            }
            nextRemoveNode.setRightChild(removeNode.getRightChild());
            if (removeNode.getRightChild() != null) {
                removeNode.getRightChild().setParent(nextRemoveNode);
            }
        }
        /**
         * @TODO 获取输入结点的前驱结点
         * @param node 输入的结点
         * @return 输入结点的前驱结点
         */
        public FOBinaryTreeNode<E> findPreNode(FOBinaryTreeNode<E> node) {
            if (node == null) {
                throw new RuntimeException("传入结点为空！");
            }
            FOBinaryTreeNode<E> tempNode = node.getLeftChild();
            if (tempNode == null) {
                // throw new RuntimeException("传入结点无前驱节点！");
                return null;
            }
            FOBinaryTreeNode<E> preNode = tempNode;
            tempNode = tempNode.getRightChild();
            while (tempNode != null) {
                preNode = tempNode;
                tempNode = tempNode.getRightChild();
            }
            return preNode;
        }
        /**
         * @TODO 获取输入结点的后继结点
         * @param node 输入结点
         * @return 输入结点的后继结点
         */
        public FOBinaryTreeNode<E> findNextNode(FOBinaryTreeNode<E> node) {
            if (node == null) {
                throw new RuntimeException("传入结点为空！");
            }
            FOBinaryTreeNode<E> tempNode = node.getRightChild();
            if (tempNode == null) {
                // throw new RuntimeException("传入结点无后继节点！");
                return null;
            }
            FOBinaryTreeNode<E> nextNode = tempNode;
            tempNode = tempNode.getLeftChild();
            while (tempNode != null) {
                nextNode = tempNode;
                tempNode = tempNode.getLeftChild();
            }
            return nextNode;
        }
        /**
         * @TODO 获取该二叉排序树的最大元素
         * @return 该二叉排序树的最大元素
         */
        public E getMaxE(){
            return this.getMaxE(root);
        }
    
        /**
         * @TODO 获取输入二叉排序树的最大元素的具体实现
         * @param node 输入二叉排序树的根结点 
         * @return 该输入二叉排序树的最大元素
         */
        private E getMaxE(FOBinaryTreeNode<E> node) {
            if(node ==null){
                return null;
            }
            while(node.getRightChild()!=null){
                node = node.getRightChild();
            }
            return node.getE();
        }
        /**
         * @TODO 获取该二叉排序树的最小元素
         * @return 该二叉排序树的最小元素
         */
        public E getMinE(){
            return this.getMinE(root);
        }
        /**
         * @TODO 获取输入二叉排序树的最小元素的具体实现
         * @param node 输入二叉排序树的根结点 
         * @return 该输入二叉排序树的最小元素
         */
        private E getMinE(FOBinaryTreeNode<E> node) {
            if(node ==null){
                return null;
            }
            while(node.getLeftChild()!=null){
                node = node.getLeftChild();
            }
            return node.getE();
        }
        /**
         * @TODO 前序遍历输出二叉排序树中元素
         * @return 二叉排序树中元素的字符串形式
         */
        public String preOrderPrint() {
            StringBuffer sb = new StringBuffer("[");
            this.preOrder(root, sb);
            sb.replace(sb.length() - 2, sb.length() - 1, "]");
            return sb.toString();
        }
        /**
         * @TODO 前序遍历输出二叉排序树中元素的具体实现
         * @param node 二叉排序树的根结点
         * @param sb 将二叉排序树中元素的遍历结果保存在sb中
         * @return 二叉排序树中元素的字符串形式
         */
        private String preOrder(FOBinaryTreeNode<E> node, StringBuffer sb) {
            if (node != null) {
                sb.append(node + ", ");
                preOrder(node.getLeftChild(), sb);
                preOrder(node.getRightChild(), sb);
            } 
            return sb.toString();
        }
        /**
         * @TODO 中序遍历输出二叉排序树中元素
         * @return 二叉排序树中元素的字符串形式
         */
        public String inOrderPrint() {
            StringBuffer sb = new StringBuffer("[");
            this.inOrder(root, sb);
            sb.replace(sb.length() - 2, sb.length() - 1, "]");
            return sb.toString();
        }
        /**
         * @TODO 中序遍历输出二叉排序树中元素的具体实现
         * @param node 二叉排序树的根结点
         * @param sb 将二叉排序树中元素的遍历结果保存在sb中
         * @return 二叉排序树中元素的字符串形式
         */
        private String inOrder(FOBinaryTreeNode<E> node, StringBuffer sb) {
            if (node != null) {
                inOrder(node.getLeftChild(), sb);
                sb.append(node + ", ");
                inOrder(node.getRightChild(), sb);
            }
            return sb.toString();
        }
        /**
         * @TODO 后序遍历输出二叉排序树中元素
         * @return 二叉排序树中元素的字符串形式
         */
        public String postOrderPrint() {
            StringBuffer sb = new StringBuffer("[");
            this.postOrder(root, sb);
            sb.replace(sb.length() - 2, sb.length() - 1, "]");
            return sb.toString();
        }
        /**
         * @TODO 中序遍历输出二叉排序树中元素的具体实现
         * @param node 二叉排序树的根结点
         * @param sb 将二叉排序树中元素的遍历结果保存在sb中
         * @return 二叉排序树中元素的字符串形式
         */
        private String postOrder(FOBinaryTreeNode<E> node, StringBuffer sb) {
            if (node != null) {
                postOrder(node.getLeftChild(), sb);
                postOrder(node.getRightChild(), sb);
                sb.append(node + ", ");
            }
            return sb.toString();
        }
    }

二叉树的结点类：

package com.phn.tree;
    /**
     * @author 潘海南
     * @Email 1016593477@qq.com
     * @TODO 二叉树结点
     * @date 2015年7月27日
     */
    public class FOBinaryTreeNode<E extends Comparable<E>>{
        private E e ;
        private FOBinaryTreeNode<E> parent;
        private FOBinaryTreeNode<E> leftChild;
        private FOBinaryTreeNode<E> rightChild;
    
    
        public FOBinaryTreeNode() {
            super();
        }
        /**
         * @param e
         * @param parent
         * @param leftChild
         * @param rightChild
         */
        public FOBinaryTreeNode(E e, FOBinaryTreeNode<E> parent,
                FOBinaryTreeNode<E> leftChild, FOBinaryTreeNode<E> rightChild) {
            super();
            this.e = e;
            this.parent = parent;
            this.leftChild = leftChild;
            this.rightChild = rightChild;
        }
        public E getE() {
            return e;
        }
        public void setE(E e) {
            this.e = e;
        }
        public FOBinaryTreeNode<E> getParent() {
            return parent;
        }
        public void setParent(FOBinaryTreeNode<E> parent) {
            this.parent = parent;
        }
        public FOBinaryTreeNode<E> getLeftChild() {
            return leftChild;
        }
        public void setLeftChild(FOBinaryTreeNode<E> leftChild) {
            this.leftChild = leftChild;
        }
        public FOBinaryTreeNode<E> getRightChild() {
            return rightChild;
        }
        public void setRightChild(FOBinaryTreeNode<E> rightChild) {
            this.rightChild = rightChild;
        }
        @Override
        public String toString() {
            return e.toString();
        }
    
    }

测试代码：

package com.phn.tree;
    /**
     * @author 潘海南
     * @Email 1016593477@qq.com
     * @TODO 
     * @date 2015年7月29日
     */
    public class FOBinarySearchTreeTest {
        public static void main(String[] args) {
            FOBinarySearchTree<String> fobst = new FOBinarySearchTree<String>();
            fobst.add("f");
            fobst.add("e");
            fobst.add("b");
            fobst.add("a");
            fobst.add("d");
            fobst.add("c");
            fobst.add("i");
            fobst.add("g");
            fobst.add("h");
            fobst.add("j");
    
    
            System.out.println(fobst.preOrderPrint());
            System.out.println(fobst.inOrderPrint());
            System.out.println(fobst.postOrderPrint());
            System.out.println(fobst.contains("a"));
            System.out.println(fobst.contains("v"));
            System.out.println(fobst.remove("a"));
            System.out.println(fobst.preOrderPrint());
            System.out.println(fobst.inOrderPrint());
            System.out.println(fobst.postOrderPrint());
            System.out.println(fobst.remove("e"));
            System.out.println(fobst.preOrderPrint());
            System.out.println(fobst.inOrderPrint());
            System.out.println(fobst.postOrderPrint());
            System.out.println(fobst.remove("k"));
            System.out.println(fobst.preOrderPrint());
            System.out.println(fobst.inOrderPrint());
            System.out.println(fobst.postOrderPrint());
            System.out.println(fobst.getMaxE());
            System.out.println(fobst.getMinE());
        }
    }

测试结果：

![.png][]

[.png]: http://7xionv.com1.z0.glb.clouddn.com/phn/datastructure/二叉排序树.png