问题
问答题
假设以带双亲指针的二叉链表作为-二叉树的存储结构，其结点结构的类型说明如下所示：
typedef char DataType;
typedef struct node
DataType data;
struct node*lchild,*rchild; //左右孩子指针
struct node*parent; //指向双亲的指针
BinTNode;
typedef BinTNode*BinTree;
若px为指向非空二叉树中某个结点的指针，可借助该结构求得px所指结点在二叉树的中序序列中的后继。
编写算法求px所指结点的中序序列后继，并在算法语句中加注注释。
答案
参考答案：BinTree f34(BinTree px)
{
BinTree q=px—＞rchild;
if(q!=NULL){ //沿左孩子往下查找
px=q;
while(px—＞lchild!=NULL)
px=px—＞lchild;
}
else{ //沿双亲指针链向上查找
while(px!=NULL&&px—＞rchild==q){
q=px;
px=px—＞parent;
}
}
retun px； //返回所找到的中序序列后继结点的指针
//或者无后继结点时返回空指针
}