使用Java怎么实现一个二叉搜索树

使用Java怎么实现一个二叉搜索树？相信很多没有经验的人对此束手无策，为此本文总结了问题出现的原因和解决方法，通过这篇文章希望你能解决这个问题。

成都创新互联致力于互联网品牌建设与网络营销，包括成都网站建设、网站设计、SEO优化、网络推广、整站优化营销策划推广、电子商务、移动互联网营销等。成都创新互联为不同类型的客户提供良好的互联网应用定制及解决方案，成都创新互联核心团队十载专注互联网开发，积累了丰富的网站经验，为广大企业客户提供一站式企业网站建设服务，在网站建设行业内树立了良好口碑。

1 树

1.1 树的定义

树（Tree）是n（n>=0)个节点的有限集。n=0时称为空树。在任意一颗非空树中：

（1）有且仅有一个特定的称为根（Root）的节点；
（2）当n>1时，其余节点可分为m(m>0)个互不相交的有限集T1、T2、......、Tn，其中每一个集合本身又是一棵树，并且称为根的子树。
此外，树的定义还需要强调以下两点：
（3）n>0时根节点是唯一的，不可能存在多个根节点，数据结构中的树只能有一个根节点。
（4）m>0时，子树的个数没有限制，但它们一定是互不相交的。

下图为一棵有10个节点的一般树的结构：

由树的定义可以看出，树的定义使用了递归的方式。递归在树的学习过程中起着重要作用。

2 二叉树

2.1 二叉树定义

二叉树是n(n>=0)个节点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树组成。
图2.1展示了一棵一般二叉树结构：

2.2 二叉树特点

 由二叉树定义以及图示分析得出二叉树有以下特点:

（1）每个节点最多有两颗子树，所以二叉树中不存在度大于2的节点。
（2）左子树和右子树是有顺序的，次序不能任意颠倒。
（3）即使树中某节点只有一棵子树，也要区分它是左子树还是右子树。
二叉树是动态的数据结构

可以用一下代码来表示一个树节点：

class Node{
  E e;
 Node left;
 Node right;
}

2.2.1 特性

1.二叉树具有天然的递归结构

这是由于，每个节点的左子树与右子树都是二叉树（有的情况下），如图：

2.2.2 二分树类型（展示）
类型1：

类型2：

类型3：

类型4：

类型5：

3.二叉搜索树

3.1 定义

二叉查找树（Binary Search Tree），也称有序二叉树（ordered binary tree）、排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

1.若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2.任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3.任意节点的左、右子树也分别为二叉查找树。
4.没有键值相等的节点（no duplicate nodes）。

因此使用二叉树存储的元素必须有可比性。

3.2二叉搜索树的性质：

二叉查找树本质上是一种二叉树，所以上章讲的二叉树的性质他都有。

3.3二分搜索树的思想：

二叉排序树的查找过程和次优二叉树类似，通常采取二叉链表作为二叉排序树的存储结构。中序遍历二叉排序树可得到一个关键字的有序序列，一个无序序列可以通过构造一棵二叉排序树变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。每次插入的新的结点都是二叉排序树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。搜索,插入,删除的复杂度等于树高，O(log(n)),后续逐一进行学习。

4.编程实现二叉搜索树

4.1 基础代码

由于使用二叉树存储的元素必须有可比性，因此在实现时需要BST类继承Comparable。

package BST;

public class BST> {

  //定义树节点
  private class Node {
    public E e;
    public Node left, right;

    public Node(E e) {
      this.e = e;
      left = null;
      right = null;
    }
  }

  private Node root;//根节点
  private int size;

  public BST() {
    root = null;
    size = 0;
  }

  //二分搜索树存储元素个数
  public int size() {
    return size;
  }

  //二分搜索树存储元素是否为空
  public boolean isEmpty() {
    return size == 0;
  }
}

看完上述内容，你们掌握使用Java怎么实现一个二叉搜索树的方法了吗？如果还想学到更多技能或想了解更多相关内容，欢迎关注创新互联行业资讯频道，感谢各位的阅读！