Java实现常见的查找算法--二叉树

时间:2021-08-22 14:40:56

参考:https://blog.csdn.net/smile_from_2015/article/details/72190562?utm_source=gold_browser_extension

二叉排序树

目标是插入和查找同样高效

假设我们的数据集开始只有一个数{62}, 然后现在需要将88插入数据集,于是数据集成了{62,88},还保持着从小到大有序。再查找有没有58,没有则插入,可此时要想在线性表的顺序存储中有序,就得移动 62 和
88 的位置,如下左图,可不可以不移动呢?那就需要使用二叉树结构。当我们用二叉树的方式时,首先我们将第一个数62定为根结点,88因为比62大,因此让它做62的右子树,58因比62小,所以成为它的左子树。此时58的插入并没有影响到62与88的关系,如下右图所示。
Java实现常见的查找算法--二叉树
也就是说, 若我们现在需要对集合{62,88,58,47,35,73,51,99,37,93}做查找,在我们打算创建此集合时就考虑用二叉树结构,而且是排好序的二叉树来创建。如下图所示,62、88、58创建好后,下一个数 47 因比58小,是它的左子树(见③),35是47的左子树(见④),73比62大,但却比88小,是88的左子树(见⑤),51比62小、比58小、比47大,是 47的右子树(见⑥),99比62、88都大,是它的右子树(见⑦),37比62、58、47都小,但却比35大,是35的右子树(见③) ,93则因比62、88大是99的左子树(见⑨)。
Java实现常见的查找算法--二叉树
这样我们就得到了一棵二叉树,并且当我们对它进行中序遍历时,就可以得到一个有序的序列{35,37,47,51,58,62,73,88,93,99},所以我们通常称它为二叉排序树。

二叉排序树(Binary Sort Tree),又称为二叉查找树。它或者是一棵空树,或者是具有下列性质的二叉树。

  • 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
  • 若它的右子树不空 ,则右子树上所有结点的值均大于它的根结点的值;
  • 它的左、右子树也分别为二叉排序树。

从二叉排序树的定义也可以知道,它前提是二叉树,然后它采用了递归的定义方法,再者,它的结点间满足一定的次序关系,左子树结点一定比其双亲结点小,右子树结点一定比其双亲结点大。
构造一棵二叉排序树的目的,其实并不是为了排序,而是为了提高查找和插入删除关键字的速度。不管怎么说,在一个有序数据集上的查找,速度总是要快于无序的数据集的,而二叉排序树这种非线性的结构,也有利于插入和删除的实现。

二叉排序树查找操作

首先我们提供一个二叉树的结构。

    /** * 二叉树,数据结构 * */
    private static class BinaryTree {
        int data;
        BinaryTree lchild;
        BinaryTree rchild;
    }

然后我们来看看二叉排序树的查找是如何实现的

public class BinarySearchTree {
    public static void main(String[] args) {
        // 主要是表达查询,所以手动构造一棵二叉排序树
        BinaryTree binaryTree1 = new BinaryTree();
        binaryTree1.data = 62;

        BinaryTree binaryTree2 = new BinaryTree();
        binaryTree1.lchild = binaryTree2;
        binaryTree2.data = 58;

        BinaryTree binaryTree3 = new BinaryTree();
        binaryTree2.lchild = binaryTree3;
        binaryTree3.data = 47;

        BinaryTree binaryTree4 = new BinaryTree();
        binaryTree3.lchild = binaryTree4;
        binaryTree4.data = 35;

        BinaryTree binaryTree5 = new BinaryTree();
        binaryTree4.rchild = binaryTree5;
        binaryTree5.data = 37;

        BinaryTree binaryTree6 = new BinaryTree();
        binaryTree3.rchild = binaryTree6;
        binaryTree6.data = 51;

        BinaryTree binaryTree7 = new BinaryTree();
        binaryTree1.rchild = binaryTree7;
        binaryTree7.data = 88;

        BinaryTree binaryTree8 = new BinaryTree();
        binaryTree7.lchild = binaryTree8;
        binaryTree8.data = 73;

        BinaryTree binaryTree9 = new BinaryTree();
        binaryTree7.rchild = binaryTree9;
        binaryTree9.data = 99;

        BinaryTree binaryTree10 = new BinaryTree();
        binaryTree9.lchild = binaryTree10;
        binaryTree10.data = 93;

        boolean search = serachBinaryTree(binaryTree1, 37, null);
        System.out.println(search == true ? "查找成功" + parentNode.data : "查找失败");
    }
    /** * 全局变量,存放查找到的关键字所在的父节点 */
    static BinaryTree parentNode = new BinaryTree();

    /** * 二叉排序树 * * @param bt * 待查询的二叉排序树 * @param key * 查找关键字 * @param parent * 指向bt的双亲,其初始调用值为null * @return 查找成功返回true,并将树节点赋值给全局变量result,查找失败返回false */
    public static boolean serachBinaryTree(BinaryTree bt, int key, BinaryTree parent) {
        if (bt == null || bt.data == 0) { // 树节点不存在,返回
            parentNode = parent;
            return false;
        } else if (key == bt.data) { // 查找成功
            parentNode = bt;
            return true;
        } else if (key < bt.data) { // 关键字小于根节点查找左子树
            return serachBinaryTree(bt.lchild, key, bt);
        } else { // 关键字大于根节点查找右子树
            return serachBinaryTree(bt.rchild, key, parent);
        }
    }
    /** * 二叉树,数据结构 * */
    private static class BinaryTree {
        int data;
        BinaryTree lchild;
        BinaryTree rchild;
    }
}

二叉排序树插入操作

有了二叉排序树的查找函数,那么所谓的二叉排序树的插入,其实也就是将关键字放到树中的合适位置而已,来看代码。

package com.wzl.binary;

public class BinarySearchTree {
    public static void main(String[] args) {
        // 主要是表达查询,所以手动构造一棵二叉排序树
        BinaryTree binaryTree1 = new BinaryTree();
        binaryTree1.data = 62;

        BinaryTree binaryTree2 = new BinaryTree();
        binaryTree1.lchild = binaryTree2;
        binaryTree2.data = 58;

        BinaryTree binaryTree3 = new BinaryTree();
        binaryTree2.lchild = binaryTree3;
        binaryTree3.data = 47;

        BinaryTree binaryTree4 = new BinaryTree();
        binaryTree3.lchild = binaryTree4;
        binaryTree4.data = 35;

        BinaryTree binaryTree5 = new BinaryTree();
        binaryTree4.rchild = binaryTree5;
        binaryTree5.data = 37;

        BinaryTree binaryTree6 = new BinaryTree();
        binaryTree3.rchild = binaryTree6;
        binaryTree6.data = 51;

        BinaryTree binaryTree7 = new BinaryTree();
        binaryTree1.rchild = binaryTree7;
        binaryTree7.data = 88;

        BinaryTree binaryTree8 = new BinaryTree();
        binaryTree7.lchild = binaryTree8;
        binaryTree8.data = 73;

        BinaryTree binaryTree9 = new BinaryTree();
        binaryTree7.rchild = binaryTree9;
        binaryTree9.data = 99;

        BinaryTree binaryTree10 = new BinaryTree();
        binaryTree9.lchild = binaryTree10;
        binaryTree10.data = 93;

        insertBinaryTree(binaryTree1, 68);
    }

    /** * 全局变量,存放查找到的关键字所在的父节点 */
    static BinaryTree parentNode = new BinaryTree();

    /** * 二叉排序树 * * @param bt * 待查询的二叉排序树 * @param key * 查找关键字 * @param parent * 指向bt的双亲,其初始调用值为null * @return 查找成功返回true,并将树节点赋值给全局变量result,查找失败返回false */
    public static boolean serachBinaryTree(BinaryTree bt, int key, BinaryTree parent) {
        if (bt == null || bt.data == 0) { // 树节点不存在,返回
            parentNode = parent;
            return false;
        } else if (key == bt.data) { // 查找成功
            parentNode = bt;
            return true;
        } else if (key < bt.data) { // 关键字小于根节点查找左子树
            return serachBinaryTree(bt.lchild, key, bt);
        } else { // 关键字大于根节点查找右子树
            return serachBinaryTree(bt.rchild, key, parent);
        }
    }

    /** * 在二叉树中插入关键字key * * @param bt * 二叉排序树 * @param key * 插入的关键字 * @return 插入成功返回true,失败返回false */
    public static boolean insertBinaryTree(BinaryTree bt, int key) {
        BinaryTree binaryTree;
        if (!serachBinaryTree(bt, key, null)) {
            binaryTree = new BinaryTree();
            binaryTree.data = key;
            binaryTree.lchild = binaryTree.rchild = null;
            if (null == parentNode) {// 不存在,证明是父节点,将binaryTree指向bt成为新的根节点
                bt = binaryTree;
            } else if (key < parentNode.data) { // 当key小于子根节点,插入为左孩子
                parentNode.lchild = binaryTree;
            } else { // 当key大于子根节点,插入为右孩子
                parentNode.rchild = binaryTree;
            }

            preOrderTraverse(bt);
            return true;
        } else {
            System.out.println("该节点已存在");
        }

        return false;
    }
    /** * 中序遍历打印线索二叉树 * * @param t */
    static void preOrderTraverse(BinaryTree t) {
        if (null == t || t.data == 0) {
            return;
        }
        if (t.lchild != null) {
            preOrderTraverse(t.lchild); // 中序遍历左子树
        }
        if (t.data != 0) {
            System.out.println("[" + t.data + "]"); // 显示当前节点的数据
        }

        if (t.rchild != null) {
            preOrderTraverse(t.rchild); // 最后遍历右子树
        }
    }

    /** * 二叉树,数据结构 * */
    private static class BinaryTree {
        int data;
        BinaryTree lchild;
        BinaryTree rchild;
    }
}

有了二叉排序树的插入代码,我们要实现二叉排序树的构建就非常容易了。下面的代码就可以创建一棵如下图所示的树。

package com.wzl.binary;

public class BinarySearchTree {
    public static void main(String[] args) {
        int[] a = { 62, 88, 58, 47, 35, 73, 51, 99, 37, 93 };  
        for (int i = 0; i < a.length; i++) {  
            System.out.println("第" + i+"次");  
            generateBinaryTree(a[i]);  
        }  

    }

     static BinaryTree newTree = new BinaryTree();  

    /** * 全局变量,存放查找到的关键字所在的父节点 */
    static BinaryTree parentNode = new BinaryTree();

    /** * 二叉排序树 * * @param bt * 待查询的二叉排序树 * @param key * 查找关键字 * @param parent * 指向bt的双亲,其初始调用值为null * @return 查找成功返回true,并将树节点赋值给全局变量result,查找失败返回false */
    public static boolean serachBinaryTree(BinaryTree bt, int key, BinaryTree parent) {
        if (bt == null || bt.data == 0) { // 树节点不存在,返回
            parentNode = parent;
            return false;
        } else if (key == bt.data) { // 查找成功
            parentNode = bt;
            return true;
        } else if (key < bt.data) { // 关键字小于根节点查找左子树
            return serachBinaryTree(bt.lchild, key, bt);
        } else { // 关键字大于根节点查找右子树
            return serachBinaryTree(bt.rchild, key, parent);
        }
    }

    /** * 生成二叉树 * @param key * @return */
    public static boolean generateBinaryTree(int key) {
        BinaryTree binaryTree;
        if (!serachBinaryTree(newTree, key, null)) {
            binaryTree = new BinaryTree();
            binaryTree.data = key;
            binaryTree.lchild = binaryTree.rchild = null;
            if (null == parentNode) {// 不存在,证明是父节点,将binaryTree指向bt成为新的根节点
                newTree = binaryTree;
            } else if (key < parentNode.data) { // 当key小于子根节点,插入为左孩子
                parentNode.lchild = binaryTree;
            } else { // 当key大于子根节点,插入为右孩子
                parentNode.rchild = binaryTree;
            }
            preOrderTraverse(newTree);
            return true;
        } else {
            System.out.println("该节点已存在");
        }

        return false;
    }
    /** * 中序遍历打印线索二叉树 * * @param t */
    static void preOrderTraverse(BinaryTree t) {
        if (null == t || t.data == 0) {
            return;
        }
        if (t.lchild != null) {
            preOrderTraverse(t.lchild); // 中序遍历左子树
        }
        if (t.data != 0) {
            System.out.println("[" + t.data + "]"); // 显示当前节点的数据
        }

        if (t.rchild != null) {
            preOrderTraverse(t.rchild); // 最后遍历右子树
        }
    }

    /** * 二叉树,数据结构 * */
    private static class BinaryTree {
        int data;
        BinaryTree lchild;
        BinaryTree rchild;
    }

}

Java实现常见的查找算法--二叉树