欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-06-05 18:22:39
...

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);
	}
}

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

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

相关标签: 二叉树查找