数据结构------二叉树查找

1.

/*递归查找j二叉排序树T 中是否存在key */
/*指针f 指向T的双亲，其初始调用值为NULL*/
/*若查找成功， 则指针p 指向该数据元素节点，并返回TRUE */
/* 否则指针p 指向查找路径*问的最后一个节点.并返回FALSE */

status searchBST(BiTree T, int key, BiTree f, BiTree &p)
{
	if (!T)
	{
		p = f;
		return FALSE;
	}
	else if (key == T->data)
	{
		p = T;
		return TRUE;
	}
	else if (key < T->data)
		return searchBST(T->lchild, key, T, p);
	else
		return searchBST(T->rchild, key, T, p);
}

插入：

status InsertBST(BiTree &T, int key)
{
	BiTNode *s;
	BiTNode *f = NULL;
	if (!searchBST(T, key, f, s))
	{
		s = (BiTree)malloc(sizeof(BiTNode));
		s->data = key;
		s->lchild = s->rchild = NULL;
		if (!s)
			T = s;//插入根节点
		else if (key < f->data)
			f->lchild = s;
		else
			f->rchild = s;
		return TRUE;
	}
	else
		return FALSE;
}

删除：

//删除
status Delete(BiTree &p)
{
	BiTNode *q, *s;
	if (p->rchild == NULL)//右子树为空
	{
		q = p; p = q->lchild; free(q);
	}
	else if (p->lchild == NULL)//zuo子树为空
	{
		q = p; p = q->rchild; free(q);
	}
	else //左右子树都不为空
	{
		q = p; s = s->rchild;
		while (s->rchild)//转做，向右到尽头
		{
			q = s; s = s->rchild;
		}
		p->data = s->data;//s指向被删除的直接前驱
		if (q != p)
		{
			q->rchild = s->lchild;//重接q的右子树
		}
		else
			q->lchild = s->lchild;
		free(s);
	}
	return TRUE;
}

status DeleteBST(BiTree &T, int key)
{
	if (!T)
		return FALSE;
	else
	{
		if (key == T->data)
			return Delete(T);
		else if (key < T->data)
			return Delete(T->lchild);
		else
			return Delete(T->rchild);
	}
}