使用Java怎么实现一个二叉搜索树?相信很多没有经验的人对此束手无策,为此本文总结了问题出现的原因和解决方法,通过这篇文章希望你能解决这个问题。
1树
1.1树的定义
<强>树(树)是<代码> 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)即使树中某节点只有一棵子树,也要区分它是左子树还是右子树。
二叉树是动态的数据结构
可以用一下代码来表示一个树节点:
1。二叉树具有天然的递归结构
这是由于,每个节点的左子树与右子树都是二叉树(有的情况下),如图:
类型1:
类型2:
类型3:
类型4:
类型5:
3。二叉搜索树
<编辑> 3.1定义<强>二叉查找树(二叉搜索树)强,也称<强>有序二叉树(有序二叉树),排序二叉树(排序二叉树)强,是指一棵空树或者具有下列性质的二叉树:
1。若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
2。任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
3。任意节点的左、右子树也分别为二叉查找树。
4。没有键值相等的节点(不重复的节点)。
<强>因此使用二叉树存储的元素必须有可比性。
<强> 
二叉查找树本质上是一种二叉树,所以上章讲的二叉树的性质他都有。
<编辑>二3.3分搜索树的思想:二叉排序树的查找过程和次优二叉树类似,通常采取二叉链表作为二叉排序树的存储结构,中序遍历二叉排序树可得到一个关键字的有序序列,一个无序序列可以通过构造一棵二叉排序树变成一个有序序列,构造树的过程即为对无序序列进行排序的过程。每次插入的新的结点都是二叉排序树上新的叶子结点,在进行插入操作时,不必移动其它结点,只需改动某个结点的指针,由空变为非空即可。搜索,插入,删除的复杂度等于树高,
