在中序线索树中找到数据域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的左孩子修改为xp->ltag=false;x->rtag=true;//x的后继修改为p x->rchild=p; 
}