二叉排序树查找算法

[c]代码库

typedef struct NODE
{
	ElemType elem; /*数据元素字段*/
	struct NODE *lc,*rc; /*左、右指针字段*/
} NodeType; /*二叉树结点类型*/



int SearchElem ( NodeType *t,NodeType **p,NodeType **q,KeyType kx )
{ /*在二叉排序树t 上查找关键码为kx 的元素，若找到，返回1，且q 指向该结点，p 指向其父结点；*/
	/*否则，返回0，且p 指向查找失败的最后一个结点*/
	int flag=0;
	*q=t;
	while ( *q ) /*从根结点开始
查找*/
	{
		if ( kx> ( *q )->elem.key ) /*kx 大于当前结点*q 的元素关键码*/
			{ *p=*q; *q= ( *q )->rc; } /*将当前结点*q 的右子女置为新根*/
		else
		{
			if ( kx< ( *q )->elem.key ) /*kx 小于当前结点*q 的元素关键码*/
				{ *p=*q; *q= ( *q )->lc;} /*将当前结点*q 的左子女置为新根*/
			else {flag=1; break;} /*查找成功，返回*/
		}
	}/*while*/
	return flag;
}