逐点插入法【二叉查找（排序）树的插入算法】

问题描述：利用逐点插入法建立序列{50，72，43，85，75，20，35，45，65，30}对应的二叉树排序后，查找元素30要进行多少次元素间的比较？

首先我来解释以下什么是二叉查找树：

二叉查找树是一棵空树，或者是具有如下性质的二叉树：
（1）若它的左子树非空，则左子树中所有结点的值均小于根节点的值
（2）若它的右子树非空，则右子树中所有结点的值均大于根节点的值
（2）左右子树也是二叉查找树

换一种说法，对于每个结点，左子树（包括左子树中的所有结点）要小于该结点，右子树（包括右子树中的所有结点）大于该点。

因此，二叉查找树的中序遍历结果是一个递增有序的序列

接下来我来解释一下什么是逐点插入法

逐点插入法，对于二叉树序列的建立来说，其实就是按照二叉查找树的的定义来进行排序

也就是说，对于本题，分析如下：
创建根节点50，因为72>50，将72作为50所在结点的右子树的关键码值

关键码值：数据结构中，数据元素中能起标识作用的数据项

对于43，43<50，作为50所在结点的左子树的关键码值，根结点此时已经有了左右子树，也就是说第二层已经“满了”，现在应该讨论下一层（第二层）了，85>72,放入72所在结点右子树，75>72,理应放入72所在结点右子树，但是72已经有了右子树，所以应作为85所在结点的子结点，与关键码值85比较，75<85,所以应放入85所在结点的左子树，依次类推将后面所有树排序，二叉树的直观形式应该如下图所示：

二叉查找树查找算法如下：

typedef struct Tnode{
	int key;
	struct Tnode *lchild, *rchild;
}BSTnode, *Bitree;

int searchBST(Bitree root,int x,Bitree *father)
//若找到，返回所找到的结点的指针，否则返回NULL，由father带回父结点指针
{
Bitree p=root;
*father=NULL;//初始父结点指针为NULL

	while(p&&p->key!=x){//判断根结点不为空且不是要找的结点
	*father=p;//父结点指向该结点
		if(x<p->key)
		p->lchild;//根据定义判断，小的数应该从左子树查找
		else p=p->rchild;//大的数从右子树查找
	}//一旦查找到，循环停止
	return p;
}

二叉查找树的插入算法

int insertBST(Bitree *root,int newkey){
//插入键值为newkey的结点，插入成功返回0，否则返回-1
	Bitree s,p,father;
	s=(BSTnode *)malloc(sizeof(BSTnode));
		if(!s) return -1;//若分配内存失败，返回-1
	s->key=newkey;//键值为待插入数字
	s->lchild=NULL;
	s->rchild-NULL;
	p=searchBST(*root,newkey,&father);//调用查找函数，找到插入位置
		if(p) return -1;//找到了相同结点，p非空，返回-1
		if(!father) *root=s;
		//父结点为空，说明根结点为空，newkey直接作为树根
			else if(newkey<father->key)
				father->lchild=s;
					else father->rchild=s;
					//按定义放入父结点子树中
	return 0;
}

对于该问题，若要查找到30，应该与50，43，20，35，30分别比较才能得到，因此要进行5次元素间的比较