首页 > 代码库 > 基于二叉排序树的查找

基于二叉排序树的查找

    导论:首先,沿着二分查找的思路,我们构造一种二叉树来查找,这种二叉树的左子树结点都小于根节点,右子树节点都大于根节点,这样一来,所有结点算是都排好序了,接下来就可以查找

 

基于二叉排序树的查找

 

一.二叉排序树的定义

所谓二叉排序树是一个什么样的东西,我们得弄清楚,以下是二叉排序树的定义:

  1.若它的左子树非空,则左子树上所有节点的值都小于根节点的值

  2.若它的右子树非空,则右子树上所有结点的值都大于根节点的值

  3.它的左子树和右子树也是一颗二叉排序树

 

  有了定义,很多东西就都会显而易见了:

  1.二叉排序树并不是一颗完全二叉树

  2.和二叉判定树的对比:二叉判定树是一种特殊的二叉排序树,二叉判定树多了一个限定条件:左右子树的节点数目相差最多不能超过1个(小雨或等于1)

      3.二叉排序树又名二叉查找树

   

  好了,到这里给出二叉排序树的定义

  

typedef struct  _TreeNode
{
	struct _TreeNode *leftNode;
	struct _TreeNode *rightNode;
	TypeData data;
}TreeNode,*TreeRoot;

  

 

 

 

二.二叉排序树的插入

  和堆的建立和维护类似,我们首先想解决的一个问题就是:已经有了一颗二叉排序树,怎样做到将一个值插入正确的位置,

  给出二叉树的插入定义

  

TreeNode* Insert_Tree(TreeRoot &root,TypeData key)
{
	if (!root)
	{
		TreeNode *node=new TreeNode;
		node->data=http://www.mamicode.com/key;>

  

这里是用递归实现的二叉排序树的插入,要注意以下几点:

 

    递归开始返回的终结点有两个:

                  1.当根节点为null时

                  2.根节点的data值和key相等,这个时候就不需要插入了

    插入完毕返回插入位置的结点

 

三.二叉排序树的建立

    所谓二叉排序树的建立,也就是通过向一个空节点不断地插入结点来建立一颗二叉排序树,通过递归地插入,可得

void Create_Tree(TreeRoot& root)
{
	TypeData key;
	while (std::cin>>key)
	{
		Insert_Tree(root,key);
	}
}

  

四.通过二叉排序树进行查找

    这里,有两种方式,递归和非递归的

    首先是递归的

TreeNode *find_InTree(TreeRoot root,TypeData key)
{
	if (root)
	{
		if (root->data=http://www.mamicode.com/=key)>

  然后是非递归的,用while循环代替递归达到递归的作用

TreeNode *find_InTree2(TreeRoot root,TypeData key)
{
	TreeNode* p=root;
	while (p)
	{
		if (p->data=http://www.mamicode.com/=key)>

  

 

 

最后,简单地分析一下查找的时间复杂度吧!

    二叉排序树的插入过程:很明显,二叉排序树过程最好情况是O(log2(n)),最差情况是O(n),最差的情况时:二叉树变为一颗只有左子树或者只有右子树的二叉树,整个插入过程也退化成为顺序插入

    二叉排序树的创建过程:很明显,假设有n个数,建立二叉排序树就要while循环n次插入过程,也就是说创建过程为O(nlog2(n))~O(n2)之间

    二叉排序树的查找过程:很明显,基于二叉排序树的查找过程和二叉排序树的插入过程类似,时间复杂度也为O(log2(n))到O(n)之间

 

最后,程序执行过程使这样的:

 

排序二叉树的创建过程;

排序二叉树的查找过程;

这样看来,整个过程的时间复杂度为O(nlog2(n)到O(n2))之间,但是实际上表述的时候我们通常忽略创建过程,只考虑二叉树的查找过程,这样看来的话,整个过程的时间复杂度为O(log2(n))到O(n)之间

 

 

 

 

 

 

 

 

 

 

基于二叉排序树的查找