在中序线索树中找到数据域A，并在其左子树中插入数据域为x的结点

有中序线索树T，结点形式为：（lchild,ltag,rchild,rtag,data），编写非递归算法找到数据域为A的结点，并在其左子树中插入数据域为x的结点

思想：利用线索二叉树的遍历方法找到数据域为A的结点。

如果A没有左孩子，将新插入的结点作为A的左孩子。将x的前驱为A的前驱，x的后继为A.

如果A有左孩子，设置x的左孩子为A的左孩子，设置x为A的左孩子，设置x的后继为A，设置x左孩子的最右侧结点的后继为x。

代码：

//求中序线索二叉树的中序序列下的第一个结点 
ThreadNode *FirstNode(ThreadNode *p){
	while(p->ltag==0) p=p->lchild;
	return p; 
}

//求中序线索二叉树的结点p的中序序列下的后继
ThreadNode *nextNode(ThreadNode *p){
	if(p->rtag==0) return FirstNode(p->rchild);//右子树的最左下结点
	else return p->rchild;//直接返回后继线索 
}

//找到数据域为A的结点 
ThreadNode *findNode(ThreadNode A,ElemType A){
	ThreadNode *r;//辅助结点
	for(r=FirstNode(T);r->data!=A;r=nextNode(r)) ;//从中序第一个元素开始找元素A 
	return r;
} 

//将x作为数据域为A的结点的左孩子，并保持线索化
void insertx(ThreadNode T,ElemType A,ThreadNode *x){
	ThreadNode *p=findNode(T,A);//找到数据域为A的结点
	if(p->ltag) {//p没有左孩子 
		x->ltag=true;
		x->lchild=p-lchild;
	}else{
		x->ltag=false;//p有左孩子 
		x->lchild=p-lchild;
		ThreadNode *s=x->lchild;//暂存x的左孩子
		while(s->rtag==0){//找到x的左孩子的最右结点 
			s=s->rchild;
		} 
		s->rchild=x;//设置这个最右结点的后继为x 
	} 
	p->lchild=x;//p的左孩子修改为x
	p->ltag=false;
	
	x->rtag=true;//x的后继修改为p 
	x->rchild=p; 
}