Java数据结构之二叉排序树的实现

目录
  • 1 二叉排序树的概述
  • 2 二叉排序树的构建
    • 2.1 类架构
    • 2.2 查找的方法
    • 2.3 插入的方法
    • 2.4 查找最大值和最小值
    • 2.5 删除的方法
  • 3 二叉排序树的总结

1 二叉排序树的概述

本文没有介绍一些基础知识。对于常见查找算法,比如顺序查找、二分查找、插入查找、斐波那契查找还不清楚的,可以看这篇文章:常见查找算法详解以及Java代码的实现。

假设查找的数据集是普通的顺序存储,那么插入操作就是将记录放在表的末端,给表记录数加一即可,删除操作可以是删除后,后面的记录向前移,也可以是要删除的元素与最后一个元素互换,表记录数减一,反正整个数据集也没有什么顺序,这样的效率也不错。应该说,插入和删除对于顺序存储结构来说,效率是可以接受的,但这样的表由于无序造成查找的效率很低。

如果查找的数据集是有序线性表,并且是顺序存储的,查找可以用折半、插值、斐波那契等查找算法来实现,可惜,因为有序,在插入和删除操作上,为了维持顺序,需要移动大量元素,就需要耗费大量的时间。

有没有一种即可以使得插入和删除效率不错,又可以比较高效率地实现查找的算法呢?这就是二叉排序树。

二叉排序树(Binary Sort Tree),又称为二叉查找树/二叉搜索树(binary search tree)。它是具有下列性质的二叉树:

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

构造一棵二叉排序树的目的,其主要目的并不是为了排序,而是为了提高查找和插入删除关键字的速度,用以提升数据结构的综合能力。不管怎么说,在一个有序数据集上的查找,速度总是要快于无序的数据集的,而二叉排序树这种非线性的结构,也有利于插入和删除的实现。

2 二叉排序树的构建

2.1 类架构

首先,最简单的节点对象还是需要一个数据域和两个引用域。

另外还需要一个比较器的引用,因为需要对元素进行排序,自然需要比较元素的大小,如果外部传递了比较器,那么就使用用户指定的比较器进行比较,否则,数据类型E必须是Comparable接口的子类,否则因为不能比较而报错。

另外,还需要提供中序遍历的方法,该遍历方法对于二叉排序树的结果将会顺序展示。

public class BinarySearchTree<E> {
    /**
     * 外部保存根节点的引用
     */
    private BinaryTreeNode<E> root;

    /**
     * 自定义比较器
     */
    private Comparator<? super E> cmp;

    /**
     * 树节点的数量
     */
    private int size;

    /**
     * 内部节点对象
     *
     * @param <E> 数据类型
     */
    public static class BinaryTreeNode<E> {

        //数据域
        E data;
        //左子节点
        BinaryTreeNode<E> left;
        //右子节点
        BinaryTreeNode<E> right;

        public BinaryTreeNode(E data) {
            this.data = data;
        }

        @Override
        public String toString() {
            return data.toString();
        }

    }

    /**
     * 指定比较器
     *
     * @param cmp 比较器
     */
    public BinarySearchTree(Comparator<? super E> cmp) {
        this.cmp = cmp;
    }

    /**
     * 空构造器
     */
    public BinarySearchTree() {
    }

    /**
     * 是否是空树
     *
     * @return true 是 ;false 否
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 返回节点数
     *
     * @return 节点数
     */
    public int size() {
        return size;
    }

    /**
     * 对元素进行比较大小的方法,如果传递了自定义比较器,则使用自定义比较器,否则则需要数据类型实现Comparable接口
     *
     * @param e1 被比较的第一个对象
     * @param e2 被比较的第二个对象
     * @return 0 相等 ;小于0 e1 < e2 ;大于0 e1 > e2
     */
    private int compare(E e1, E e2) {
        if (cmp != null) {
            return cmp.compare(e1, e2);
        } else {
            return ((Comparable<E>) e1).compareTo(e2);
        }
    }

    /**
     * 保存遍历出来的节点数据
     */
    List<BinaryTreeNode<E>> str = new ArrayList<>();

    /**
     * 中序遍历,提供给外部使用的api
     *
     * @return 遍历的数据
     */
    public String toInorderTraversalString() {

        //如果是空树,直接返回空
        if (isEmpty()) {
            return null;
        }
        //从根节点开始递归
        inorderTraversal(root);
        //获取遍历结果
        String s = str.toString();
        str.clear();
        return s;
    }

    /**
     * 中序遍历 内部使用的递归遍历方法,借用了栈的结构
     *
     * @param root 节点,从根节点开始
     */
    private void inorderTraversal(BinaryTreeNode<E> root) {

        BinaryTreeNode<E> left = getLeft(root);
        if (left != null) {
            //如果左子节点不为null,则继续递归遍历该左子节点
            inorderTraversal(left);
        }
        //添加数据节点
        str.add(root);
        //获取节点的右子节点
        BinaryTreeNode<E> right = getRight(root);
        if (right != null) {
            //如果右子节点不为null,则继续递归遍历该右子节点
            inorderTraversal(right);
        }
    }

    /**
     * 获取左子节点
     *
     * @param parent 父节点引用
     * @return 左子节点或者null--表示没有左子节点
     */
    public BinaryTreeNode<E> getLeft(BinaryTreeNode<E> parent) {
        return parent == null ? null : parent.left;
    }

    /**
     * 获取右子节点
     *
     * @param parent 父节点引用
     * @return 右子节点或者null--表示没有右子节点
     */
    public BinaryTreeNode<E> getRight(BinaryTreeNode<E> parent) {
        return parent == null ? null : parent.right;
    }

    /**
     * 获取根节点
     *
     * @return 根节点 ;或者null--表示空树
     */
    public BinaryTreeNode<E> getRoot() {
        return root;
    }

}

2.2 查找的方法

查找的方法很简单:

  • 若根节点的关键字值等于查找的关键字,成功,返回true;
  • 否则,若小于根节点的关键字值,递归查左子树;
  • 若大于根节点的关键字值,递归查右子树;
  • 最终查找到叶子节点还是没有数据,那么查找失败,则返回false。
/**
 * 查找,开放给外部使用的api
 */
public boolean contains(E e) {
    return contains(e, root);
}

/**
 * 查找,内部调用的方法,从根节点开始查找
 *
 * @param e    要查找的元素
 * @param root 节点
 * @return false 不存在 true 存在
 */
private boolean contains(E e, BinaryTreeNode<E> root) {
    /*null校验*/
    if (root == null) {
        return false;
    }
    /*调用比较的方法*/
    int i = compare(e, root.data);
    /*如果大于0,则说明e>root.date 继续查询右子树*/
    if (i > 0) {
        return contains(e, root.right);
        /*如果小于0,则说明e<root.date 继续查询左子树*/
    } else if (i < 0) {
        return contains(e, root.left);
    } else {
        /*如果等于0,则说明e=root.date 即查询成功*/
        return true;
    }
}

2.3 插入的方法

有了二叉排序树的查找函数,那么所谓的二叉排序树的插入,其实也就是将关键字放到树中的合适位置而已,插入操作就好像在调用查找的操作,如果找到了那么什么都不做,返回false,如果没找到,则将要插入的元素插入到遍历的路径的最后一点上:

  • 若二叉树为空。则单独生成根节点,返回true。
  • 执行查找算法,找出被插节点的父亲节点。
  • 判断被插节点是其父亲节点的左、右儿子。将被插节点作为叶子节点插入,返回true。如果原节点存在那么什么都不做,返回false。注意:新插入的节点总是叶子节点。
/**
 * 插入,开放给外部使用的api
 *
 * @param e 要插入的元素
 */
public void insert(E e) {
    //返回root,但此时新的节点可能已经被插入进去了
    root = insert(e, root);
}

/**
 * 插入,开放给外部使用的api
 *
 * @param es 要插入的元素的数组,注意,数组元素的顺序存储的位置将会影响二叉排序树的生成
 */
public void insert(E[] es) {
    //返回root,但此时新的节点可能已经被插入进去了
    for (E e : es) {
        root = insert(e, root);
    }

}

/**
 * 插入,内部调用的方法,先从根节点开始递归查找要插入的位置,然后插入
 *
 * @param e    要插入的数据
 * @param root 节点
 * @return 原节点或者新插入的节点
 */
private BinaryTreeNode<E> insert(E e, BinaryTreeNode<E> root) {
    /*没有查找到,那么直接构建新的节点返回,将会在上一层方法中被赋值给其父节点的某个引用,这个插入的位置肯定是该遍历路径上的最后一点
     * 即插入的元素节点肯定是属于叶子节点*/
    if (root == null) {
        size++;
        return new BinaryTreeNode<>(e);
    }
    /*调用比较的方法*/
    int i = compare(e, root.data);
    /*如果大于0,则说明e>root.date 继续查询右子树*/
    if (i > 0) {
        //重新赋值
        root.right = insert(e, root.right);
        /*如果小于0,则说明e<root.date 继续查询左子树*/
    } else if (i < 0) {
        //重新赋值
        root.left = insert(e, root.left);
    } else {
        /*如果等于0,则说明e=root.date 即存在节点 什么都不做*/
    }
    //没查询到最底层,则返回该节点
    return root;
}

2.3.1 测试

现在我们想要构建如下一颗排序二叉树:

首先要插入根节点47,然后是第二层的节点16、73,然后是第三层的节点1、24、59、88,然后是第四层的节点20、35、62、77。每一层内部节点的顺序可以不一致,但是每一层之间的大顺序一定要保持一致,否则虽然中序遍历输出的时候能够正常输出,但是树的结构不能保证。

public class BinarySearchTreeTest {
    BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>();

    @Test
    public void insert() {
        //首先要插入根节点47,然后是第二层的节点16,73,然后是第三层的节点1,24,59,88,然后是第四层的节点20,35,62,77。
        // 每一层内部节点的顺序可以不一致,但是每一层之间的打顺序一定要保持一致,否则虽然中序遍历输出的时候能够正常输出,但是树的结构不能保证。
        Integer[] es = new Integer[]{47, 16, 73, 1, 24, 59, 88, 20, 35, 62, 77};
        binarySearchTree.insert(es);
        //中序遍历输出
        System.out.println(binarySearchTree.toInorderTraversalString());

        //查找某个数据是否存在
        System.out.println(binarySearchTree.contains(1));
        System.out.println(binarySearchTree.contains(2));
    }
}

在System.out处打上断点,Debug,可以看到树结构和我们预想的一致,如果改变层间的大顺序,那么使用Debug会发现树结构不如预期。

2.4 查找最大值和最小值

很简单,最左边的节点一定是最小的,最右边的节点一定是最大的。因此查找最小的节点只需要向左递归查找,查找最大的节点只需要向右递归查找。

/**
 * 查找最小的节点
 *
 * @param root 根节点
 * @return 最小的节点
 */
private BinaryTreeNode<E> findMin(BinaryTreeNode<E> root) {
    if (root == null) {
        return null;
        /*如果该节点没有左右子节点,那么该节点就是最小的节点,返回*/
    } else if (root.left == null) {
        return root;
    }
    /*如果该节点存在左子节点,那么继续向左递归查找*/
    return findMin(root.left);
}

/**
 * 查找最大的节点
 *
 * @param root 根节点
 * @return 最大的节点
 */
private BinaryTreeNode<E> findMax(BinaryTreeNode<E> root) {
    if (root == null) {
        return null;
        /*如果该节点没有右子节点,那么该节点就是最大的节点,返回*/
    } else if (root.right == null) {
        return root;
    }
    /*如果该节点存在右子节点,那么继续向右递归查找*/
    return findMax(root.right);
}

2.5 删除的方法

对于二叉排序树的删除,就不是那么容易,我们不能因为删除了节点,而让这棵树变得不满足二叉排序树的特性,所以删除需要考虑多种情况。一共有三种情况需要考虑:

如果查找到的将要被删除的节点没有子节点,那么很简单,直接删除父节点对于该节点的引用即可,如下图的红色节点:

例如,删除20之后:

如果查找到的将要被删除的节点具有一个子节点,那么也很简单,直接绕过该节点将原本父节点对于该节点的引用指向该节点的子节点即可,如下图的红色节点:

例如,删除59之后:

如果查找到的将要被删除的节点具有两个子节点,那么就比较麻烦了,如下图的红色节点:

比如我们需要删除73,那么我们就必须要找出一个已存在的能够替代73的节点,然后删除该节点。实际上该73节点的左子树的最大节点62和右子树的最小节点77都能够替代73节点,即它们正好是二叉排序树中比它小或比它大的最接近73的两个数。

一般我们选择一种方式即可,我们这次使用右子树的最小节点替代要删除的节点,使用77替代73之后的结构如下:

完整的代码如下:

    /**
     * 删除,开放给外部使用的api
     *
     * @param e 要删除的元素
     */
    public void delete(E e) {
        //返回root,但此时可能有一个节点已经被删除了
        root = delete(e, root);
    }

    /**
     * 删除,内部调用的方法,删除分为三种情况: 1、该节点没有子节点 2、该字节仅有一个子节点 3、该节点具有两个子节点
     *
     * @param e    要删除的数据
     * @param root 根节点
     * @return 该节点
     */
    private BinaryTreeNode<E> delete(E e, BinaryTreeNode<E> root) {
        /*没有查找到,那么什么都不做*/
        if (root == null) {
            return null;
        }
        /*调用比较的方法*/
        int i = compare(e, root.data);
        /*如果大于0,则说明e>root.date 继续查询右子树*/
        if (i > 0) {
            //从新赋值
            root.right = delete(e, root.right);
            /*如果小于0,则说明e<root.date 继续查询左子树*/
        } else if (i < 0) {
            //从新赋值
            root.left = delete(e, root.left);
        } else {
            /*如果等于0,则说明e=root.date 即查询成功 开始执行删除*/
            /*如果两个子节点都不为null*/
            if (root.left != null && root.right != null) {
                /*方法1、递归查找最小的节点,然后递归删除  该方法不推荐使用*/
                //root.data = findMin(root.right).data;
                //root.right = delete(root.data, root.right);
                /*方法2、递归查找并删除最小的节点 推荐*/
                root.data = findAndDeleteMin(root.right, root);
                size--;
            } else {
                /*如果一个子节点不为null,则返回该子节点;或者两个子节点都为null,则返回null
                 * 此时该root节点已经被"绕过了"*/
                root = (root.left != null) ? root.left : root.right;
                size--;
            }
        }
        //没查询到最底层,则返回该节点
        return root;
    }

    /**
     * 查找最小的节点并删除
     * 最小的节点肯定不存在两个子节点,有可能没有子节点,有可能存在右子节点
     *
     * @param root   节点
     * @param parent 节点的父节点
     * @return 被删除的最小的节点
     */
    private E findAndDeleteMin(BinaryTreeNode<E> root, BinaryTreeNode<E> parent) {
        //如果节点为null,返回
        if (root == null) {
            return null;
            /*如果节点的左子节点为null,那么该节点就是最小的节点*/
            /*1、该最小节点肯定没有左子节点,因为左子节点比父节点小,但是可能有右子节点*/
            /*2、此时该节点可能作为某个节点的左子节点,也可能作为原父节点的右子节点(即右子树是一颗右斜树),这里需要分开讨论*/
        } else if (root.left == null) {
            //如果该节点是父节点的右子节点,说明还没进行递归或者第一次递归就找到了最小节点.
            //那么此时,应该让该节点的父节点的右子节点指向该节点的右子节点,并返回该节点的数据,该节点由于没有了强引用,会被GC删除
            if (root == parent.right) {
                parent.right = root.right;
            } else {
                //如果该节点不是父节点的右子节点,说明进行了多次递归。
                //那么此时,应该让该节点的父节点的左子节点指向该节点的右子节点,并返回该节点的数据,该节点由于没有了强引用,会被GC删除
                parent.left = root.right;
            }
            //返回最小节点的数据
            return root.data;
        }
        //递归调用,注意此时是往左查找
        return findAndDeleteMin(root.left, root);
    }

2.5.1 测试

public class BinarySearchTreeTest {
    BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>();

    @Test
    public void test() {
        //首先要插入根节点47,然后是第二层的节点16,73,然后是第三层的节点1,24,59,88,然后是第四层的节点20,35,62,77。
        // 每一层内部节点的顺序可以不一致,但是每一层之间的打顺序一定要保持一致,否则虽然中序遍历输出的时候能够正常输出,但是树的结构不能保证。
        Integer[] es = new Integer[]{47, 16, 73, 1, 24, 59, 88, 20, 35, 62, 77};
        binarySearchTree.insert(es);
        //中序遍历输出
        System.out.println(binarySearchTree.toInorderTraversalString());

        //查找是否存在
        System.out.println(binarySearchTree.contains(1));
        System.out.println(binarySearchTree.contains(2));

        //移除
        binarySearchTree.delete(73);
        //中序遍历输出
        System.out.println(binarySearchTree.toInorderTraversalString());
    }
}

3 二叉排序树的总结

总之,二叉排序树是以链接的方式存储,保持了链接存储结构在执行插入或删除操作时不用移动元素的优点,只要找到合适的插入和删除位置后,仅需修改链接指针即可。

插入删除的时间性能比较好。而对于二叉排序树的查找,走的就是从根节点到要查找的节点的路径,其比较次数等于给定值的节点在二叉排序树的层数。极端情况,最少为1次,即根节点就是要找的节点,最多也不会超过树的深度。也就是说,二叉排序树的查找性能取决于二叉排序树的形状。可问题就在于,二叉排序树的形状是不确定的。

例如{47, 16, 73, 1, 24, 59, 88}这样的数组,我们可以构建下图左的二叉排序树。但如果数组元素的次序是从小到大有序,如{1, 16, 24, 47, 59, 73, 88},则二叉排序树就成了极端的右斜树,注意它依然是一棵二叉排序树,如下图右。此时,同样是查找节点88,左图只需要3次比较,而右图就需要7次比较才可以得到结果,二者差异很大。

也就是说,我们希望二叉排序树是比较平衡的,即其深度与完全二叉树相同,均为|log2n+1|(|x|表示不大于x的最大整数),那么查找的时间复杂也就为O(logn),近似于折半查找,事实上,上图的左图也不够平衡,明显的左重右轻。而极端情况下的右图,则完全退化成为链表,查找的时间复杂度为O(n),这等同于顺序查找。

因此,如果我们希望对一个集合按二叉排序树查找,最好是把它构建成一棵平衡的二叉排序树,防止极端情况的发生。这样我们就引申出另一个问题,如何让二叉排序树平衡的问题。关于这个问题,在后续的平衡二叉树(AVL树)的部分将会详细解释!

以上就是Java数据结构之二叉排序树的实现的详细内容,更多关于Java二叉排序树的资料请关注我们其它相关文章!

(0)

相关推荐

  • C#实现二叉排序树代码实例

    二叉排序树,又称为二叉查找树.它或者是一颗空树,或者是具有下列性质的二叉树: 若它的左子树不为空.则左子树上所有的结点的值均小于跟的结点值 若它的右子树部位空,则右子树的所有结点值均大于它的根结点的值 它的左右子树也分别是二叉排序树 1,排序方便 2,查找方便 3,便于插入和删除 C#链式存储二叉排序树,实现简单的排序,以及查找,具体代码如下: namespace _2_1_3二叉排序树 { /// <summary> /// 结点类 /// </summary> class BS

  • 详解Java二叉排序树

    一.二叉排序树定义 1.二叉排序树的定义 二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree).其定义为:二叉排序树或者是空树,或者是满足如下性质的二叉树: ①若它的左子树非空,则左子树上所有结点的值均小于根结点的值: ②若它的右子树非空,则右子树上所有结点的值均大于根结点的值: ③左.右子树本身又各是一棵二叉排序树. 上述性质简称二叉排序树性质(BST性质),故二叉排序树实际上是满足BST性质的二叉树. 2.二叉排序树的性质 按中序遍历二

  • C语言实现BST二叉排序树的基本操作

    本文实例为大家分享了C语言实现BST二叉排序树的基本操作代码,供大家参考,具体内容如下 BST-二叉排序树的几个基本操作. 头文件声明与函数定义 #include <stdio.h> #include <stdlib.h> typedef int ElemType; /** * 定义节点 */ typedef struct BSTNode{ ElemType data;//数据域 struct BSTNode *lchild,//左孩子 *rchild;//右孩子 }BSTNode

  • python实现二叉排序树

    目录 方法一(粗暴) 方法二(递归) 方法一(粗暴) #二叉排序树 class BTree():     def __init__(self,data):         self.left = None         self.right = None         if type(data) == list:             self.data = data[0]             for d in data[1:]:                 self.insert

  • Python数据结构之二叉排序树的定义、查找、插入、构造、删除

    前言   本篇章主要介绍二叉树的应用之一------二叉排序树,包括二叉排序树的定义.查找.插入.构造.删除及查找效率分析. 1. 二叉排序树的定义   二叉排序树 ( B i n a r y (Binary (Binary S o r t Sort Sort T r e e , B S T ) Tree,BST) Tree,BST),也称为二叉查找树,具有以下性质:   (1) 若左子树非空,则左子树上所有结点的值均小于根结点的值:   (2) 若右子树非空,则右子树上所有结点的值均大于根结点

  • C语言二叉排序树的创建,插入和删除

    目录 一.二叉排序树(二叉查找树)的概念 二.二叉排序树的判别 三.二叉排序树的创建(creat.insert) 四.二叉排序树的插入 五.二插排序树的删除 六.完整代码(可以运行) 总结 一.二叉排序树(二叉查找树)的概念 (1)若左子树非空,则左子树上所有结点的值均小于根节点的值 (2)若右子树非空,则右子树上所有结点的值均大于根节点的值 (3)左右子树分别也是一棵二叉排序树 tip:可以是一棵空树 二.二叉排序树的判别 (1)因为二叉排序树的中序遍历是一个有序递增序列,可以对已经建立的二叉

  • 二叉排序树的实现与基本操作

    二叉排序树又称二叉查找树.它或者是一颗空树,或者是具有以下性质的二叉树: ①如果左子树不空,那么左子树上所有结点的值均小于它的根结点的值: ②如果右子树不空,那么右子树上所有结点的值均大于它的根结点的值: ③左右子树也分别为二叉排序树. 以下代码实现了: 二叉树的构建 二叉树的中.前.后.层序遍历 二叉树中结点的最大距离 import java.util.LinkedList; import java.util.Queue; class Node{ public int data; public

  • Java数据结构之二叉排序树的实现

    目录 1 二叉排序树的概述 2 二叉排序树的构建 2.1 类架构 2.2 查找的方法 2.3 插入的方法 2.4 查找最大值和最小值 2.5 删除的方法 3 二叉排序树的总结 1 二叉排序树的概述 本文没有介绍一些基础知识.对于常见查找算法,比如顺序查找.二分查找.插入查找.斐波那契查找还不清楚的,可以看这篇文章:常见查找算法详解以及Java代码的实现. 假设查找的数据集是普通的顺序存储,那么插入操作就是将记录放在表的末端,给表记录数加一即可,删除操作可以是删除后,后面的记录向前移,也可以是要删

  • Java数据结构之链表、栈、队列、树的实现方法示例

    本文实例讲述了Java数据结构之链表.栈.队列.树的实现方法.分享给大家供大家参考,具体如下: 最近无意中翻到一本书,闲来无事写几行代码,实现几种常用的数据结构,以备后查. 一.线性表(链表) 1.节点定义 /**链表节点定义 * @author colonel * */ class Node { public int data; Node next=null; public Node(int data){ this.data=data; } } 2.链表操作类 /**链表操作类 * @auth

  • Java数据结构与算法入门实例详解

    第一部分:Java数据结构 要理解Java数据结构,必须能清楚何为数据结构? 数据结构: Data_Structure,它是储存数据的一种结构体,在此结构中储存一些数据,而这些数据之间有一定的关系. 而各数据元素之间的相互关系,又包括三个组成成分,数据的逻辑结构,数据的存储结构和数据运算结构. 而一个数据结构的设计过程分成抽象层.数据结构层和实现层. 数据结构在Java的语言体系中按逻辑结构可以分为两大类:线性数据结构和非线性数据结构. 一.Java数据结构之:线性数据结构 线性数据结构:常见的

  • Java数据结构学习之树

    一.树 1.1 概念 与线性表表示的一一对应的线性关系不同,树表示的是数据元素之间更为复杂的非线性关系. 直观来看,树是以分支关系定义的层次结构. 树在客观世界中广泛存在,如人类社会的族谱和各种社会组织机构都可以用树的形象来表示. 简单来说,树表示的是1对多的关系. 定义(逻辑结构): 树(Tree)是n( n>=0 )个结点的有限集合,没有结点的树称为空树,在任意一颗非空树中: 有且仅有一个特定的称为根(root)的结点 . 当n>1的时,其余结点可分为 m( m>0 ) 个互不相交的

  • Java数据结构之散列表详解

    目录 介绍 1 散列表概述 1.1 散列表概述 1.2 散列冲突(hash collision) 2 散列函数的选择 2.1 散列函数的要求 2.2 散列函数构造方法 3 散列冲突的解决 3.1 分离链接法 3.2 开放定址法 3.3 再散列法 4 散列表的简单实现 4.1 测试 介绍 本文详细介绍了散列表的概念.散列函数的选择.散列冲突的解决办法,并且最后提供了一种散列表的Java代码实现. 数组的特点是寻址容易,插入和删除困难:而链表的特点是寻址困难,插入和删除容易.而对于tree结构,它们

  • Java数据结构之平衡二叉树的原理与实现

    目录 1 平衡二叉树的概述 2 平衡二叉树的实现原理 2.1 单旋转 2.2 双旋转 2.3 总结 3 平衡二叉树的构建 3.1 类架构 3.2 查找的方法 3.3 检查是否平衡的方法 3.4 插入的方法 3.5 查找最大值和最小值 3.6 删除的方法 4 平衡二叉树的总结 平衡二叉树(AVL树),顾名思义,是一颗很“平衡”的树,它的平衡是相对于排序二叉树来说的.为了避免极端情况下二叉搜索树节点分布不均匀,甚至退化为链表,影响查找效率,我们引入了平衡二叉树,即让树的结构看起来尽量“均匀”,左右子

  • Java数据结构超详细分析二叉搜索树

    目录 1.搜索树的概念 2.二叉搜索树的简单实现 2.1查找 2.2插入 2.3删除 2.4修改 3.二叉搜索树的性能 1.搜索树的概念 二叉搜索树是一种特殊的二叉树,又称二叉查找树,二叉排序树,它有几个特点: 如果左子树存在,则左子树每个结点的值均小于根结点的值. 如果右子树存在,则右子树每个结点的值均大于根结点的值. 中序遍历二叉搜索树,得到的序列是依次递增的. 二叉搜索树的左右子树均为二叉搜索树. 二叉搜索树的结点的值不能发生重复. 2.二叉搜索树的简单实现 我们来简单实现以下搜索树,就不

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

    目录 定义 节点结构 查找算法 插入算法 删除算法 完整代码 定义 二叉查找树(亦称二叉搜索树.二叉排序树)是一棵二叉树,且各结点关键词互异,其中根序列按其关键词递增排列. 等价描述:二叉查找树中任一结点 P,其左子树中结点的关键词都小于 P 的关键词,右子树中结点的关键词都大于 P 的关键词,且结点 P 的左右子树也都是二叉查找树 节点结构 :one: key:关键字的值 :two: value:关键字的存储信息 :three: left:左节点的引用 :four: right:右节点的引用

  • Java数据结构之有效队列定义与用法示例

    本文实例讲述了Java数据结构之有效队列定义与用法.分享给大家供大家参考,具体如下: /** * @描述 有序对列 * 从任何位置插入数据都是有序的 * @项目名称 Java_DataStruct * @包名 com.java.stack * @类名 Queue * @author chenlin */ public class SequeQueue { private long[] arr; private int maxSize;// 最大空间 private int len;// 有效长度

  • Java数据结构之链表(动力节点之Java学院整理)

    单链表: insertFirst:在表头插入一个新的链接点,时间复杂度为O(1) deleteFirst:删除表头的链接点,时间复杂度为O(1) find:查找包含指定关键字的链接点,由于需要遍历查找,平均需要查找N/2次,即O(N) remove:删除包含指定关键字的链接点,由于需要遍历查找,平均需要查找N/2次,即O(N) public class LinkedList { private class Data{ private Object obj; private Data next =

随机推荐