美文网首页@IT·互联网
手撸二叉树——二叉查找树

手撸二叉树——二叉查找树

作者: 牛初九 | 来源:发表于2024-10-12 10:39 被阅读0次

二叉树是数据结构中非常重要的一种数据结构,它是的一种,但是每个节点的子节点不能多余两个,可以是0,1,2个子节点,0个子节点代表没有子节点。常见的二叉树结构如下图所示:

image-20241012100212420.png

每个节点的子节点不多于2个,其中3,4,5没有子节点,2有一个子节点,0,1都有两个子节点。

基础概念

根节点:树的其实节点,没有父节点。

叶子节点:没有子节点的节点叫做叶子节点。

节点深度:从根节点到该节点的距离叫做深度,如上图:节点3的深度是2,节点1的深度是1。

节点高度:该节点到距离最长的叶子节点的距离。

二叉查找树

二叉树最重要的一个应用是在查询方面的应用,很多的索引结构都是二叉查找树,还有向HashMap里也使用到了红黑树,红黑树也是二叉查找树的一种。二叉查找树的一个重要性质,就是任何一个节点,它的左子树中的节点都小于该节点,它的右子树中的节点都大于该节点。最开始我们的例图它不是一棵二叉查找树,它不符合我们刚才说的性质。我们再看看下面的例图:

image-20241012103245333.png

这是一棵二叉查找树,它的任何一个节点的子节点都小于该节点,右子树的节点都大于该节点。这样我们在查找数据的时候,就可以从根节点开始查找,如果查找的值小于该节点,就去左子树中查找,如果大于该节点,就去右子树中查找,如果等于,那就不用说了,直接返回就可以了。这种可以大大提升我们的查找效率,它的时间复杂度是O(logN)。

手撸二叉查找树

首先我们要抽象出节点类,每个节点可以有左子节点,和右子节点,当然节点要存储一个值,这个值的类型我们不做限制,可以是数字型,也可以是字符串,还可以是自己定义的类,但是这里要加一个前提条件,就是这个值是可比较的,因为两个节点比较后才能确定位置,所以节点值的类型要实现Comparable接口。好了,满足上面的条件,我们就可以抽象出二叉树节点的类了,如下:

public class BinaryNode<T extends Comparable<T>> {
    //节点数据
    @Setter@Getter
    private T element;
    //左子节点
    @Setter@Getter
    private BinaryNode<T> left;
    //右子节点
    @Setter@Getter
    private BinaryNode<T> right;

    //构造函数
    public BinaryNode(T element) {
        this(element,null,null);
    }
    //构造函数
    public BinaryNode(T element, BinaryNode<T> left, BinaryNode<T> right) {
        if (element == null) {
            throw new RuntimeException("二叉树节点元素不能为空");
        }
        this.element = element;
        this.left = left;
        this.right = right;
    }
}

我们定义二叉树节点的类为BinaryNode,我们注意一下后面的泛型,它要实现Comparable接口。然后我们定义节点数据element,左子节点left,和右子节点right,并且使用@Setter@Getter注解实现其set和get方法。接下来就是定义两个构造方法,一个是只传入节点元素的,另一个是传入节点元素和左右子树的。节点的元素是不能为空的,如果是空则抛出异常。

然后,我们再定义二叉查找树类,类中包括一些二叉查找树的基本操作方法,这些基本的操作方法我们后面讲,先看定义的基本元素,如下:

public class BinarySearchTree<T extends Comparable<T>> {
    //根节点
    private BinaryNode<T> root;

    public BinarySearchTree() {
        this.root = null;
    }
    
    //将树变为空树
    public void makeEmpty() {
        this.root = null;
    }

    //判断树是否为空
    public boolean isEmpty() {
        return this.root == null;
    }
}

类的名字定义为:BinarySearchTree,同样我们注意一下这里的泛型,它和BinaryNode的泛型是一样的,因为这个类型我们传递给BinaryNode。类中定义了树的根节点root,以及构造方法,构造方法只是定义了一棵空树,根节点为空。然后是两个比较基础的树的操作方法makeEmptyisEmpty,将树变为空树和判断树是否为空。

  1. 现在我们要编写一些树的操作方法了,首先我们要编写的就是contains方法,它会判断树中是否包含某个元素,比如上面例图中,我们判断树中是否包含3这个元素。具体实现如下:
/**
 * 二叉树是否包含某个元素
 *
 * @param element 检查的元素
 * @return true or false
 */
public boolean contains(T element) {
    return contains(root, element);
}

/**
 * 二叉树是否包含某个元素
 *
 * @param tree    整棵树或左右子树
 * @param element 检查的元素
 * @return true or false
 */
private boolean contains(BinaryNode<T> tree, T element) {
    if (tree == null) {
        return false;
    }

    int compareResult = element.compareTo(tree.getElement());

    if (compareResult > 0) {
        return contains(tree.getRight(), element);
    }
    if (compareResult < 0) {
        return contains(tree.getLeft(), element);
    }
    return true;
}

这里我们定义了两个contains方法,第一个contains方法调用第二个contains方法,第二个contains方法是私有的,外部不能访问。在调用第二个contains方法时,我们将root传进去,也就是整棵树传入去查找。在第二个contains方法中,我们先判断树是否为空,如果为空,肯定不会包含我们要查找的元素,则直接返回false。然后我们用查找的元素和当前节点的元素作比较,这里我们使用compareTo方法,它是Comparable接口中定义好的方法,这也是我们定义泛型时要实现Comparable接口的原因了。比较结果大于0,说明查找的值大于当前节点值,我们递归调用contains方法,将右子树和查找的值传入;比较结果小于0,说明查找的值小于当前节点值,我们同样递归调用contains方法,将左子树和查找的值传入进行查找。最后如果比较结果等于0,说明查找的值和当前节点值是一样的,我们返回true就可以了。

contains方法算是一个开胃小菜,其中用到了递归,这也让我们对二叉树的编写方法有了一个初步的了解。

  1. 接下来我们要编写的是findMinfindMax方法,分别是找出树中最小值和最大值的方法。由于我们的树是一棵二叉查找树,左子树的值要小于当前节点,右子树的值大于当前节点,所以,最左侧节点的值就是最小值,最右侧的值则是最大值。我们用代码实现一下,
/**
 * 找出二叉树的最小元素
 *
 * @return
 */
public T findMin() {
    if (isEmpty()) throw new RuntimeException("二叉树为空");
    return findMin(root);
}

private T findMin(BinaryNode<T> tree) {
    if (tree.getLeft() != null) {
        return findMin(tree.getLeft());
    }
    return tree.getElement();
}

/**
 * 找出二叉树的最大元素
 *
 * @return
 */
public T findMax() {
    if (isEmpty()) throw new RuntimeException("二叉树为空");
    return findMax(root);
}

private T findMax(BinaryNode<T> tree) {
    while (tree.getRight() != null) {
        tree = tree.getRight();
    }
    return tree.getElement();
}

我们先来看findMin方法,先判断树是否为空,空树没有最小值,也没有最大值,所以我们这里抛出异常。然后我们将整棵树传入第二个findMin方法,在第二个findMin方法中,我们一直去寻找左子节点,如果左子节点不为空,我们就递归的再去寻找,直到节点的左子节点为空,那么当前节点就是整棵树的最左节点,那么它的值就是最小的,我们返回就可以了。

我们再来看findMax方法,和findMin方法一样,先判断树是否为空,为空则抛出异常。我们要重点看的是第二个findMax方法,这个方法中,我们没有使用递归去寻找最右侧的节点,而是使用了一个while循环,去找到最右侧的节点。这里我们使用了两种不同的方法实现了findMinfindMax,一个使用了递归,另一个使用了while循环,其实这两种方式也是互通的,能用递归的方法也可以用while循环去实现,反之亦然。

  1. 接下来我们再来看一下二叉查找树的一个非常重要的方法,那就是insert插入方法了。当我们向二叉查找树中添加一个节点时,要和当前节点做比较,如果小于当前节点值,则在左侧插入,如果大于则在右侧插入,这里我们不讨论等于的情况。具体代码如下:
/**
 * 插入元素
 *
 * @param element
 */
public void insert(T element) {
    if (root == null) {
        root = new BinaryNode<>(element);
        return;
    }
    insert(root, element);
}

private void insert(BinaryNode<T> tree, T element) {
    int compareResult = element.compareTo(tree.getElement());
    if (compareResult > 0) {
        if (tree.getRight() == null) {
            tree.setRight(new BinaryNode<>(element));
        } else {
            insert(tree.getRight(), element);
        }
    }

    if (compareResult < 0) {
        if (tree.getLeft() == null) {
            tree.setLeft(new BinaryNode<>(element));
        } else {
            insert(tree.getLeft(), element);
        }
    }
}

在插入节点的过程中,我们先判断根节点是否为空,如果为空,说明是一棵空树,我们直接将插入元素给到根节点就可以了。如果根节点不为空,我们进入到第二个insert方法,在第二个insert方法中,我们先将插入的值和当前节点做比较,比较结果如果大于0,说明插入的值比当前节点大,所以我们要在右侧插入,如果当前节点的右子节点为空,我们直接插入就可以了;如果右子节点不为空,还要和右子节点作比较,这里我们用递归的方法实现,逻辑比较清晰。同理,如果比较结果小于0,我们对左侧节点做操作就可以了,这里不再赘述。

  1. 上面我们做了节点的插入,最后再来看看节点的删除remove。要删除一个节点,首先我们要找到这个节点,找到这个节点后,要分情况对这个节点进行处理,如下:
  • 删除节点没有子节点:我们直接将该节点删除,也就是将节点置为null;

  • 删除节点只有左子节点或右子节点:这种只有一个子节点的情况,我们直接将要删除的节点改为它的唯一的子节点就可以了。这里等于是用子节点覆盖掉当前节点;

  • 删除节点有两个子节点:这种是最复杂的情况,要解决这个问题,我们还是要利用二叉查找树的特性,就是当前节点的左子树的值都比当前节点小,右子树的值都比当前节点大。那么我们把当前节点删除后,用哪个节点代替当前节点呢?这里我们可以在左子树中找到最大的值,或者从右子树中找到最小的值,代替当前要删除的节点。这样替换后,还是可以保证左子树的值比当前值小,右子树的值比当前值大。然后我们再把替换的值,也就是左子树中的最大值,或者右子树中的最小值,在左或右子树中删掉就可以了。这一段逻辑比较绕,小伙伴们可以多读几遍,理解一下。具体实现如下:

/**
 * 删除元素
 * @param element
 */
public void remove(T element) {
    remove(root, element);
}

private void remove(BinaryNode<T> tree, T element) {
    if (tree == null) {
        return;
    }
    int compareResult = element.compareTo(tree.getElement());
    if (compareResult > 0) {
        remove(tree.getRight(), element);
        return;
    }
    if (compareResult < 0) {
        remove(tree.getLeft(), element);
        return;
    }
    if (tree.getLeft() != null && tree.getRight() != null) {
        tree.setElement(findMin(tree.getRight()));
        remove(tree.getRight(), tree.getElement());
    } else {
        tree = tree.getLeft() != null ? tree.getLeft() : tree.getRight();
    }
}

第一个remove方法不说了,我们重点看第二个。方法进来后,节点是否为空,为空则说明是空树,或者要删除的节点没有找到,那么直接返回就可以了。然后再用删除的元素和当前节点作比较,如果大于0,我们用递归方法在右子树中继续执行删除方法。同理如果小于0,用左子树递归。再下面就是等于0的情况,也就是找到了要删除的节点。我们先处理最复杂的情况,就是删除节点左右子节点都存在的情况,我们使用上面的逻辑,使用右子树中最小的节点覆盖当前节点,然后再在右子树中,将这个值删掉,我们也是递归的调用了remove方法。当然这里也可以使用左子树中的最大值,小伙伴们自己实现吧。最后就是处理没有子节点和只有一个子节点的情况,这两种情况在代码中可以合并,如果左子节点不为空,就用左子节点覆盖掉当前节点,否则使用右子节点覆盖。如果右子节点也为空,也就是没有子节点,那么当前节点也就变为空了。

问题

到这里,二叉查找树的基本的操作方法就编写完了。这里引申一个问题,如果我们顺序的向一棵树中插入1,2,3,4,5,这个树会是什么形状?这个也不难想象,如下:

image-20241013100457665.png

这和链表没有什么区别了呀,查找的性能和链表一样了,并没有提升。这就引出了下一篇的内容:平衡二叉树,小伙伴们,敬请期待~~

相关文章

  • 6. 二叉树创建-查找

    1. 递归方式实现二叉树的构建2. 树、二叉树、二叉查找树3. 二叉树排序树的理解4. 二叉查找树5. 二叉树的查找

  • 树与二叉树

    **树 ** 二叉树 满二叉树 完全二叉树 三种遍历方法 树与二叉树的区别 二叉查找树 平衡二叉树 红黑二叉树

  • 二叉树 堆 2019-04-17

    二叉树 实现一个二叉查找树,并且支持插入、删除、查找操作 实现查找二叉查找树中某个节点的后继、前驱节点 实现二叉树...

  • 数据结构3:二叉树详细介绍

    9.二叉树 9.1 二叉树的定义 9.2 满二叉树与完全二叉树 9.3 二叉查找树(也叫二叉搜索树,二...

  • 数据结构——二叉查找树(C语言)

    二叉查找树,也称作二叉搜索树,有序二叉树,排序二叉树,而当一棵空树或者具有下列性质的二叉树,就可以被定义为二叉查找...

  • 极客时间数据结构与算法之美笔记25~26

    二叉树到二叉查找树,是为了查找数据的效率接近logN。 二叉查找树到平衡二叉查找树,是为了防止二叉查找树沦为链表。...

  • 7天练|Day5:二叉树和堆

    关于二叉树和堆的7个必知必会的代码实现二叉树实现一个二叉查找树,并且支持插入、删除、查找操作实现查找二叉查找树中某...

  • 24| 二叉树基础(下)

    上一节我们学习了树、二叉树以及二叉树的遍历,今天我们再来学习一种特殊的的二叉树,二叉查找树。二叉查找树最大的特点就...

  • 二叉查找树的查找和排序方法的实现

    定义二叉树 二叉查找树的查找和排序方法的实现

  • 二叉树、2-3 树、红黑树

    二叉树、2-3 树、红黑树一、满二叉树二、完全二叉树三、二叉查找树四、平衡二叉树4.1 插入原理4.2 旋转问题4...

网友评论

    本文标题:手撸二叉树——二叉查找树

    本文链接:https://www.haomeiwen.com/subject/vmbnrjtx.html