在一棵已建立中序线索二叉树中，查找指定结点＊Ｐ的前驱，找到后返回Ｑ．

因为中序序列中第一个被访问的结点没有前驱，我不知道怎么表示它的前驱为空，还有就是到底有多少种情况要考

虑，即有多少种类型的结点需要考虑进去！

请大家帮我提提建议，讲讲思路！

谢谢！

对于这样的树来说,做搜索遍历时,它是要判断它的标记指针的.



对任意一个结点,它的前驱就是左指针指向的结点(p->lchild),只是如果它的左标记为1,那说明前驱就是它的左孩子,否则就是穿线后的指针指向.当然只有最左结点是没有前驱的.(要有也是NULL).

什么是“前驱”？

前驱就是某个结点(A)的指针域指向一个结点(B)时,称A是B的前驱,B是A的后继.

哦

程序写在我的树帖里了.
看不懂再问我了.
晓得毛.
自己再到网上找点相关资料看下.

感觉你的程序只是在线索化一棵树，而我的意思是在一棵已经线索化了的树中找指定结点的前驱！

不过在网上已经找到了，但总感觉没那么简单！

void InPre(BiTNode * p, BiTNode * pre)

/* 在中序线索二叉树中查找p的中序前驱, 并用pre指针返回结果 */

{ if(p->Ltag==1) pre= p->LChild; /*直接利用线索*/

else

{ /* 在p的左子树中查找“最右下端”结点 */

for(q= p->LChild;q->Rtag==0;q=q->RChild);

pre=q;

}

}

[此贴子已经被作者于2007-6-26 13:46:18编辑过]

如果是已经线索化好的,那前驱就是->lchild.

每个没有才是那样先线索化,如果是只找一个的话,那就是像你上面说的一样.
你还是先弄清楚什么是线索树吧.

我知道啊!
我就是说在中序序列中第一个访问的结点因为没有前驱,不知道怎么 表示.是不是也包含在那个程序的第二中情况?