数据结构-二叉查找树(Binary Search Tree)

二叉查找树拥有如下特性:

  • 若左子树不空,则左子树上所有结点的值均小于或等于它的根结点的值;
  • 若右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值;
  • 左、右子树也分别为二叉查找树;
package com.zhuke.datastruct;

import com.alibaba.fastjson.JSON;

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * Created by ZHUKE on 2017/9/6.
 */
public class BSTUtils<T extends Comparable<T>> {

    public static void main(String[] args) throws InterruptedException {
        BSTUtils<Integer> BST = new BSTUtils<>();

        BinaryNode<Integer> rootTree = null;

        rootTree = BST.insert(100, rootTree);
        rootTree = BST.insert(80, rootTree);
        rootTree = BST.insert(120, rootTree);
        rootTree = BST.insert(90, rootTree);
        rootTree = BST.insert(85, rootTree);
        rootTree = BST.insert(95, rootTree);
        rootTree = BST.insert(110, rootTree);
        rootTree = BST.insert(150, rootTree);
        rootTree = BST.insert(115, rootTree);
        rootTree = BST.insert(180, rootTree);
        rootTree = BST.insert(140, rootTree);

        BSTUtils<Integer> BST1 = new BSTUtils<>();
        BinaryNode<Integer> rootTree1 = null;

        rootTree1 = BST1.insertNoRecursive(-1, rootTree1);
        rootTree1 = BST1.insertNoRecursive(31, rootTree1);
        rootTree1 = BST1.insertNoRecursive(81, rootTree1);
        rootTree1 = BST1.insertNoRecursive(-36, rootTree1);
        rootTree1 = BST1.insertNoRecursive(188, rootTree1);
        rootTree1 = BST1.insertNoRecursive(-2, rootTree1);
        rootTree1 = BST1.insertNoRecursive(9, rootTree1);


        System.out.println("Search result = " + BST.search(100, rootTree).data);
        System.out.println("Search with no recursive result = " + BST.searchNoRecursive(100, rootTree).data);

        System.out.println("BST max value = " + BST.findMax(rootTree).data);
        System.out.println("BST min value = " + BST.findMin(rootTree).data);

        System.out.println("BST with no recursive max value = " + BST.findMaxNoRecursive(rootTree).data);
        System.out.println("BST with no recursive min value = " + BST.findMinNoRecursive(rootTree).data);

        ArrayList<Integer> preOrderResult = new ArrayList<>();

        BST.preOrderTraversal(rootTree, preOrderResult);
        System.out.println("PreOrder traversal result = " + JSON.toJSONString(preOrderResult));

        preOrderResult.clear();
        BST.preOrderTraversalNoRecursive(rootTree, preOrderResult);
        System.out.println("PreOrder traversal with no recursive result = " + JSON.toJSONString(preOrderResult));

        ArrayList<Integer> inOrderResult = new ArrayList<>();

        BST.inOrderTraversal(rootTree, inOrderResult);
        System.out.println("InOrder traversal result = " + JSON.toJSONString(inOrderResult));

        inOrderResult.clear();
        BST.inOrderTraversalNoRecursive(rootTree, inOrderResult);
        System.out.println("InOrder traversal with no recursive result = " + JSON.toJSONString(inOrderResult));

        ArrayList<Integer> postOrderResult = new ArrayList<>();

        BST.postOrderTraversal(rootTree, postOrderResult);
        System.out.println("PostOrder traversal result = " + JSON.toJSONString(postOrderResult));

        postOrderResult.clear();
        BST.postOrderTraversalNoRecursive(rootTree, postOrderResult);
        System.out.println("PostOrder traversal with no recursive result = " + JSON.toJSONString(postOrderResult));

        ArrayList<Integer> breadthResult = new ArrayList<>();

        BST.breadthTraversal(rootTree, breadthResult);
        System.out.println("Breadth traversal result = " + JSON.toJSONString(breadthResult));

        BST.delete(120, rootTree);

        Thread.sleep(Integer.MAX_VALUE);

    }


    /**
     * 在BST中插入一个数据值为data的节点
     *
     * @param data 数据值
     * @param tree 根节点
     * @return 插入了一个数据值为data的BST根节点
     */
    public BinaryNode<T> insert(T data, BinaryNode<T> tree) {
        if (tree == null) {
            tree = new BinaryNode<>(data, null, null, null);
            return tree;
        }
        int compareResult = data.compareTo(tree.data);
        if (compareResult < 0) {
            tree.leftNode = insert(data, tree.leftNode);
            tree.leftNode.parentNode = tree;
        } else if (compareResult > 0) {
            tree.rightNode = insert(data, tree.rightNode);
            tree.rightNode.parentNode = tree;
        } else {
            tree.count.incrementAndGet();
            return tree;
        }
        return tree;
    }

    /**
     * 使用非递归方式,在BST中插入一个数据值为data的节点
     *
     * @param data 数据值
     * @param tree 根节点
     * @return 插入了一个数据值为data的BST根节点
     */
    public BinaryNode<T> insertNoRecursive(T data, BinaryNode<T> tree) {
        if (tree == null) {
            tree = new BinaryNode<>(data, null, null, null);
            return tree;
        }
        int compareResult = data.compareTo(tree.data);
        if (compareResult == 0) {
            tree.count.incrementAndGet();
            return tree;
        } else {
            BinaryNode<T> targetInsertLocation = compareResult > 0 ? tree.rightNode : tree.leftNode;
            if (targetInsertLocation == null) {
                if (compareResult > 0) {
                    tree.rightNode = new BinaryNode<>(data, null, null, tree);
                } else {
                    tree.leftNode = new BinaryNode<>(data, null, null, tree);
                }
                return tree;
            }
            //循环遍历到树的末端节点,判断处理插入的正确位置
            while (true) {
                compareResult = data.compareTo(targetInsertLocation.data);
                if (compareResult == 0) {
                    targetInsertLocation.count.incrementAndGet();
                    return tree;
                } else {
                    if (compareResult > 0) {
                        if (targetInsertLocation.rightNode != null) {
                            targetInsertLocation = targetInsertLocation.rightNode;
                        } else {
                            targetInsertLocation.rightNode = new BinaryNode<>(data, null, null, targetInsertLocation);
                            return tree;
                        }
                    } else {
                        if (targetInsertLocation.leftNode != null) {
                            targetInsertLocation = targetInsertLocation.leftNode;
                        } else {
                            targetInsertLocation.leftNode = new BinaryNode<>(data, null, null, targetInsertLocation);
                            return tree;
                        }
                    }
                }
            }
        }
    }

    /**
     * 删除节点值为data的节点
     *
     * @param data 数据值
     * @param tree 根节点
     * @return 删除节点值为data后的BST
     */
    public BinaryNode<T> delete(T data, BinaryNode<T> tree) {

        BinaryNode<T> searchedNode = search(data, tree);

        if (searchedNode == null) {
            return tree;
        }

        //叶子节点,直接删除
        if (searchedNode.leftNode == null && searchedNode.rightNode == null) {
            int parentLeftCompareResult = searchedNode.parentNode.leftNode.data.compareTo(data);
            searchedNode.parentNode = null;
            if (searchedNode.count.decrementAndGet() == 0) {
                //只有一个元素,直接删除关联关系
                if (parentLeftCompareResult == 0) {
                    searchedNode.leftNode = null;
                } else {
                    searchedNode.rightNode = null;
                }
            }
        } else if (searchedNode.leftNode != null && searchedNode.rightNode != null) {//同时有左子树和右子树
            //找到替代被删除节点的节点,该节点需要比被删除节点的左子树都大,比右子树都小
            //被删除节点的右子树的最小值,满足上述要求,而且该节点一定是叶子节点
            BinaryNode<T> replacedNode = findMin(searchedNode.rightNode);
            searchedNode.data = replacedNode.data;
            //替换完成后,直接删除
            replacedNode.parentNode.leftNode = null;
            replacedNode.parentNode = null;
        } else {
            /*只有左子树或右子树*/
            if (searchedNode.leftNode != null) {
                //只有左子树,将左子树和父结点相连接
                int searchedNodeCompareToParentNode = searchedNode.data.compareTo(searchedNode.parentNode.data);
                if (searchedNodeCompareToParentNode > 0) {
                    //被删除的节点为父结点的右节点
                    searchedNode.parentNode.rightNode = searchedNode.leftNode;
                } else {
                    searchedNode.parentNode.leftNode = searchedNode.leftNode;
                }
            } else {
                //只有右子树,将右子树和父节点想相连接
                int searchedNodeCompareToParentNode = searchedNode.data.compareTo(searchedNode.parentNode.data);
                if (searchedNodeCompareToParentNode > 0) {
                    //被删除的节点为父结点的右节点
                    searchedNode.parentNode.rightNode = searchedNode.rightNode;
                } else {
                    searchedNode.parentNode.leftNode = searchedNode.rightNode;
                }
            }
        }
        return tree;
    }

    /**
     * 查找指定值在BST中的所在节点
     *
     * @param data 数据值
     * @param tree 根节点
     * @return 节点值为data的节点
     */
    public BinaryNode<T> search(T data, BinaryNode<T> tree) {
        if (tree == null) {
            return null;
        }
        int compareResult = data.compareTo(tree.data);
        if (compareResult > 0) {
            return search(data, tree.rightNode);
        } else if (compareResult < 0) {
            return search(data, tree.leftNode);
        } else {
            return tree;
        }
    }

    /**
     * 非递归方式,查找指定值在BST中的所在节点
     *
     * @param data 数据值
     * @param tree 根节点
     * @return 节点值为data的节点
     */
    public BinaryNode<T> searchNoRecursive(T data, BinaryNode<T> tree) {
        if (tree == null) {
            return null;
        }
        int compareResult = data.compareTo(tree.data);
        if (compareResult == 0) {
            return tree;
        } else {
            BinaryNode<T> targetNodeLocation = compareResult > 0 ? tree.rightNode : tree.leftNode;
            //遍历查找树的各层节点
            while (targetNodeLocation != null) {
                compareResult = data.compareTo(targetNodeLocation.data);
                if (compareResult == 0) {
                    return targetNodeLocation;
                } else {
                    targetNodeLocation = (compareResult > 0 ? targetNodeLocation.rightNode : targetNodeLocation.leftNode);
                }
            }
            return null;
        }
    }

    /**
     * 查找BST的最小值
     *
     * @param tree 根节点
     * @return BST中的最小值
     */
    public BinaryNode<T> findMin(BinaryNode<T> tree) {
        if (tree == null) {
            return null;
        }
        if (tree.leftNode == null) {
            return tree;
        } else {
            return findMin(tree.leftNode);
        }
    }

    public BinaryNode<T> findMinNoRecursive(BinaryNode<T> tree) {
        if (tree == null) {
            return null;
        }
        if (tree.leftNode == null) {
            return tree;
        } else {
            BinaryNode<T> targetNodeLocation = tree.leftNode;
            while (true) {
                if (targetNodeLocation.leftNode == null) {
                    return targetNodeLocation;
                } else {
                    targetNodeLocation = targetNodeLocation.leftNode;
                }
            }
        }
    }

    /**
     * 查找BST的最大值
     *
     * @param tree 根节点
     * @return BST中的最大值
     */
    public BinaryNode<T> findMax(BinaryNode<T> tree) {
        if (tree == null) {
            return null;
        }
        if (tree.rightNode == null) {
            return tree;
        } else {
            return findMax(tree.rightNode);
        }
    }

    public BinaryNode<T> findMaxNoRecursive(BinaryNode<T> tree) {
        if (tree == null) {
            return null;
        }
        if (tree.rightNode == null) {
            return tree;
        } else {
            BinaryNode<T> targetNodeLocation = tree.rightNode;
            while (true) {
                if (targetNodeLocation.rightNode == null) {
                    return targetNodeLocation;
                } else {
                    targetNodeLocation = targetNodeLocation.rightNode;
                }
            }
        }
    }

    /**
     * 前序遍历BST
     *
     * @param tree            BST根节点
     * @param traversalResult 遍历结果
     */
    public void preOrderTraversal(BinaryNode<T> tree, List<T> traversalResult) {
        if (tree != null) {
            addTraversalToResultList(tree, traversalResult);
            preOrderTraversal(tree.leftNode, traversalResult);
            preOrderTraversal(tree.rightNode, traversalResult);
        }
    }

    /**
     * 非递归方式前序遍历BST
     *
     * @param tree            BST根节点
     * @param traversalResult 遍历结果
     */
    public void preOrderTraversalNoRecursive(BinaryNode<T> tree, List<T> traversalResult) {
        if (tree != null) {
            //使用一个栈,暂存访问左右子树的顺序
            Stack<BinaryNode<T>> stack = new Stack<>();
            BinaryNode<T> node = tree;

            while (node != null || !stack.isEmpty()) {

                //首先访问根节点,并将根节点入栈,因为需要通过根节点进入相应的左右子树
                while (node != null) {
                    addTraversalToResultList(node.clone(), traversalResult);
                    stack.push(node);
                    node = node.leftNode;
                }
                //上面的循环全部访问左子树的所有根节点,直到BST的最左下角,此时情况如下
                /*
                        x                   top_node

                        /                   /       \

                     top_node          node=null    right_node

                     /     \

                node=null   null

                */
                //因此无论何种情况都需要出栈,因为此时top_node的根节点和左叶子节点都已经完全访问,
                // 所以按照相同步骤遍历访问其右子树
                if (!stack.isEmpty()) {
                    node = stack.pop();
                    node = node.rightNode;
                }
            }
        }
    }

    /**
     * 中序遍历BST
     *
     * @param tree            BST根节点
     * @param traversalResult 遍历结果
     */
    public void inOrderTraversal(BinaryNode<T> tree, List<T> traversalResult) {
        if (tree != null) {
            inOrderTraversal(tree.leftNode, traversalResult);
            addTraversalToResultList(tree, traversalResult);
            inOrderTraversal(tree.rightNode, traversalResult);
        }
    }

    /**
     * 非递归方式中序遍历BST
     *
     * @param tree            BST根节点
     * @param traversalResult 遍历结果
     */
    public void inOrderTraversalNoRecursive(BinaryNode<T> tree, List<T> traversalResult) {
        if (tree != null) {
            //使用一个栈,暂存访问左右子树的顺序
            Stack<BinaryNode<T>> stack = new Stack<>();
            BinaryNode<T> node = tree;

            while (node != null || !stack.isEmpty()) {

                //一直遍历到左子树最左下角,边遍历边保存根节点到栈中
                //需要借助保存的根节点进入右节点的遍历过程
                while (node != null) {
                    stack.push(node);
                    node = node.leftNode;
                }
                //此时位于栈顶的元素有如下两种情况,无论哪种情况都应将栈顶节点出栈,访问该节点
                /*
                        x                   top_node

                        /                   /       \

                     top_node          node=null    right_node

                     /     \

                node=null   null

                */

                // 此时可以进行访问栈顶元素
                if (!stack.isEmpty()) {
                    node = stack.pop();
                    addTraversalToResultList(node.clone(), traversalResult);
                    //如果访问节点的根节点有右子树,则进行上层循环,中序遍历访问右子树的节点
                    node = node.rightNode;
                }
            }

        }
    }

    /**
     * 后序遍历BST
     *
     * @param tree            BST根节点
     * @param traversalResult 遍历结果
     */
    public void postOrderTraversal(BinaryNode<T> tree, List<T> traversalResult) {
        if (tree != null) {
            postOrderTraversal(tree.leftNode, traversalResult);
            postOrderTraversal(tree.rightNode, traversalResult);
            addTraversalToResultList(tree, traversalResult);
        }
    }

    /**
     * 非递归方式,后序遍历BST
     *
     * @param tree            BST根节点
     * @param traversalResult 遍历结果
     */
    public void postOrderTraversalNoRecursive(BinaryNode<T> tree, List<T> traversalResult) {
        if (tree != null) {
            //记录原BST的左右子树访问顺序
            Stack<BinaryNode<T>> stack = new Stack<>();
            //记录后续遍历的遍历顺序
            Stack<BinaryNode<T>> output = new Stack<>();

            stack.push(tree);
            while (!stack.isEmpty()) {
                BinaryNode<T> pop = stack.pop();

                //将根节点首先入栈到output栈底,根节点最后访问
                output.push(pop);
                if (pop.leftNode != null) {
                    //leftNode节点先入栈stack,后入output栈,符合left-right-root的访问顺序
                    stack.push(pop.leftNode);
                }
                if (pop.rightNode != null) {
                    //right节点后入栈stack,先入output栈,符合left-right-root的访问顺序
                    stack.push(pop.rightNode);
                }
            }

            while (!output.isEmpty()) {
                addTraversalToResultList(output.pop(), traversalResult);
            }
        }
    }

    /**
     * 广度优先遍历
     *
     * @param tree            BST
     * @param traversalResult 遍历结果
     */
    public void breadthTraversal(BinaryNode<T> tree, List<T> traversalResult) {
        Queue<BinaryNode<T>> queue = new LinkedList<>();
        queue.add(tree);
        while (!queue.isEmpty()) {
            BinaryNode<T> node = queue.remove();
            addTraversalToResultList(node, traversalResult);
            if (node.leftNode != null) {
                queue.add(node.leftNode);
            }
            if (node.rightNode != null) {
                queue.add(node.rightNode);
            }
        }
    }

    /**
     * 对二叉排序树进行升序排序,即是对BST进行中序遍历的结果
     *
     * @param tree       根节点
     * @param sortedData 升序排序的结果
     */
    public void sort(BinaryNode<T> tree, List<T> sortedData) {
        inOrderTraversal(tree, sortedData);
    }


    private void addTraversalToResultList(BinaryNode<T> node, List<T> traversalResult) {
        for (int i = 0; i < node.count.intValue(); i++) {
            traversalResult.add(node.data);
        }
    }

}

/**
 * 二叉查找树的节点数据结构
 *
 * @param <T> 数据节点的类型,必须实现Comparable接口
 */
class BinaryNode<T extends Comparable<T>> {
    /**
     * 数据类型
     */
    T data;

    /**
     * 左节点
     */
    BinaryNode<T> leftNode;

    /**
     * 右节点
     */
    BinaryNode<T> rightNode;

    /**
     * 父节点
     */
    BinaryNode<T> parentNode;

    /**
     * 数据data出现的次数,
     * 用于支持BST可以插入相同data的值,
     * 以便节点数据值的比较
     */
    AtomicInteger count;


    public BinaryNode(T data) {
        this.data = data;
    }

    public BinaryNode(T data, BinaryNode<T> leftNode, BinaryNode<T> rightNode, BinaryNode<T> parentNode) {
        this.data = data;
        this.leftNode = leftNode;
        this.rightNode = rightNode;
        this.parentNode = parentNode;
        this.count = new AtomicInteger(1);
    }

    @Override
    protected BinaryNode<T> clone() {
        BinaryNode<T> clonedNode = new BinaryNode<>(this.data, null, null, null);
        clonedNode.count = new AtomicInteger(this.count.intValue());
        return clonedNode;
    }
}

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 201,552评论 5 474
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 84,666评论 2 377
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 148,519评论 0 334
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,180评论 1 272
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,205评论 5 363
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,344评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,781评论 3 393
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,449评论 0 256
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,635评论 1 295
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,467评论 2 317
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,515评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,217评论 3 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,775评论 3 303
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,851评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,084评论 1 258
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,637评论 2 348
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,204评论 2 341

推荐阅读更多精彩内容

  • 数据结构与算法--从平衡二叉树(AVL)到红黑树 上节学习了二叉查找树。算法的性能取决于树的形状,而树的形状取决于...
    sunhaiyu阅读 7,637评论 4 32
  • 数据结构与算法--二叉查找树 上节中学习了基于链表的顺序查找和有序数组的二分查找,其中前者在插入删除时更有优势,而...
    sunhaiyu阅读 1,818评论 0 9
  • 定义 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值; 若任意节点的右子树不空,则右子树上所有...
    None_Ling阅读 639评论 0 1
  • 第一章 绪论 什么是数据结构? 数据结构的定义:数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 第二章...
    SeanCheney阅读 5,726评论 0 19
  • 是非止于智者 一言折尽平生福 总有为活跃气氛而充当喜感角色的,而喜剧的本质就是故意显得又蠢又笨,...
    贺氏育发堂阅读 262评论 0 0