习题－50.c

来自「本人收集的一些数据结构经典算法实现」· C语言 代码 · 共 38 行

//本程序只给出了算法思想
//读者可以自己完善本程序
Status Insert_BiThrTree(BiThrTree &T,BiThrTree &p,BiThrTree &x)
//在中序线索二叉树T的结点p下插入子树x
{
	if(!p->ltag&&!p->rtag) 
		return INFEASIBLE; //无法插入
	if(p->ltag) //x作为p的左子树
	{
		s=p->lchild; //s为p的前驱
		p->ltag=Link;
		p->lchild=x;
		q=x;
		while(q->lchild) 
			q=q->lchild;
		q->lchild=s; //找到子树中的最左结点,并修改其前驱指向s
		q=x;
		while(q->rchild) 
			q=q->rchild;
		q->rchild=p; //找到子树中的最右结点,并修改其前驱指向p
	}
	else //x作为p的右子树
	{
		s=p->rchild; //s为p的后继
		p->rtag=Link;
		p->rchild=x;
		q=x;
		while(q->rchild) 
			q=q->rchild;
		q->rchild=s; //找到子树中的最右结点,并修改其前驱指向s
		q=x;
		while(q->lchild) 
			q=q->lchild;
		q->lchild=p; //找到子树中的最左结点,并修改其前驱指向p
	}
	return OK;
}//Insert_BiThrTree