习题－28.c

这个是数据结构经典算法实现

//本程序只给出了算法思想
//读者可以自己完善本程序
void BSTree_Insert_Key(BiThrTree &T,int x)//在后继线索二叉搜索树T中插入元素x
{
	if(T->data<x) //插入到右侧
	{
		if(T->rtag) //T没有右子树时,作为右孩子插入
		{
			p=T->rchild;
			q=(BiThrNode*)malloc(sizeof(BiThrNode));
			q->data=x;
			T->rchild=q;
			T->rtag=0;
			q->rtag=1;
			q->rchild=p; //修改原线索
		}
		else 
			BSTree_Insert_Key(T->rchild,x);//T有右子树时,插入右子树中
	}//if
	else if(T->data>x) //插入到左子树中
	{
		if(!T->lchild) //T没有左子树时,作为左孩子插入
		{
			q=(BiThrNode*)malloc(sizeof(BiThrNode));
			q->data=x;
			T->lchild=q;
			q->rtag=1;
			q->rchild=T; //修改自身的线索
		}
		else BSTree_Insert_Key(T->lchild,x);//T有左子树时,插入左子树中
	}//if
}//BSTree_Insert_Key