博客

Ⅰ 前言

在前面的文章里，我详细讲解了树与二叉树，也讲解了一种特殊的二叉树——哈夫曼树，这篇文章我们就来继续探讨另一种特殊的二叉树：

二叉查找树

。二叉查找树最大的特点就是，支持动态数据集合的快速插入、删除以及查找操作。

Ⅱ 什么是二叉查找树

二叉查找树是二叉树中最常用的一种类型，也叫

二叉搜索树

。顾名思义，二叉查找树是为了实现快速查找而生的。不过，它不仅仅支持快速查找一个数据，还支持快速插入、删除一个数据，现在我们就来看看二叉查找树的原理。

这些功能的实现其实都依赖于二叉查找树的特殊结构。二叉查找树要求，

在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

上面几个都是二叉查找树，大家可以看看。

Ⅲ 关于二叉查找树的几个操作

A. 查找

我们先来看一下二叉查找树是如何实现查找一个节点的。

首先，我们先取根节点，如果它等于我们要查找的数据，那就直接返回。如果要查找的数据比根节点的值小，那就在左子树中递归查找；如果要查找的数据比根节点的值大，那就在右子树中递归查找。

查找操作的代码如下👇

package com.tyz.bst.core;

public class BinarySearchTree {
   
	private Node tree;
	
	public BinarySearchTree() {
   
	}

	public Node find(int data) {
   
		Node p = tree;
		
		while (p != null) {
   
			if (data < p.data) {
   
				p = p.left;
			} else if (data > p.data) {
   
				p = p.right;
			} else {
   
				return p;
			}
		}
		return null;
	}
	
	public class Node {
   
		private int data;
		private Node left;