在后序线索二叉树T中，查找给定结点*p在后序序列中的前驱。
(1)编写二叉链表方式存储的二叉树建立函数；
(2)编写在二叉树上加后序线索函数；
(3)编写求前驱结点函数；参考下面代码段
BiTNode * PostPre(BiTNode *p)
{ BiTNode *pre=NULL;
if(p->Rtag==0) pre=p->Rchild;
else pre= p->Lchild;
return pre;
}
（4）要求程序通过一个主菜单进行控制，通过选择菜单项序号调用各功能函数。
代码实现
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ERROR 0
#define OK 1
#define FALSE -1
#define TRUE 1
#define SIZE 10
typedef struct Node
{
char data;
short int Ltag,Rtag;
struct Node * LChild;
struct Node * RChild;
}BitNode, *BiTree;
typedef struct
{
BitNode * a[SIZE];
int i;
}Array;
int menu_select(); //菜单驱动程序
void CreateBiTree(BiTree * bt);
void Inthread(BiTree root);
BitNode * InPre(BitNode * p);
void PostOrder(BiTree root, Array * store);
void Search(BiTree bt);
int menu_select()
{
int sn;
printf(“在后序线索树中查找前驱结点\n”); //显示菜单
printf(“==============================\n”);
printf(“1.先序创建二叉树\n”);
printf(“2.后序线索化\n”);
printf(“3.求前驱结点\n”);
printf(“0.退出系统\n”);
printf(“==============================\n”);
printf(“请选择0–3:”);
for (;;) //菜单功能选择
{
scanf(“%d”, &sn);
getchar();
if (sn < 0 || sn>3)
printf(“输入选择错误，请重新选择 0–3:\n”);
else
break;
}
return sn;
}
/*
TODO: 用扩展先序遍历序列创建二叉树
功能描述：用扩展先序遍历序列创建二叉树，空结点使用“.”表示。
比如录入AB..CD…则树根为A，A有两个子结点B,C，B无子结点，C有一个子结点D，D无子结点
参数：BiTree *bt 是需要操作的结点
返回值：无。
*/
void CreateBiTree(BiTree *bt)
{
char ch;
ch=getchar();
if(ch==’.’) *bt=NULL;
else
{
*bt=(BiTree)malloc(sizeof(BitNode));
if(*bt==NULL) return 0;
(*bt)->data=ch;
CreateBiTree(&(*bt)->LChild);
CreateBiTree(&(*bt)->RChild);
}
return;
}
/*
TODO: 后序线索化二叉树
功能描述：使用递归算法，完成后序线索化二叉树。
若结点有左子树，则其LChild域指向左孩子，否则LChild指向其前驱结点，
若结点有右子树，则其RChild域指向右孩子，否则RChild指向其后继结点，
其中Ltag/Rtag=0 域指示结点对应的孩子，Ltag/Rtag=1域指示结点的遍历前驱/后继
参数：BiTree root 是需要操作的结点
返回值：无。
*/
void Inthread(BiTree root)
{
BitNode *pre;
if (root!=NULL) {
if (NULL == root->LChild)
Inthread(root->LChild);
if (NULL == root->RChild)
Inthread(root->RChild);
if (NULL==root->LChild) {
root->Ltag = 1;
root->LChild = pre;
}
else root->Ltag = 0;
if (NULL==root->RChild) {
root->Rtag = 1;
root->RChild = pre;
}
else root->Rtag = 0;
pre = root;
}
}
/*
TODO: 查找前驱节点
功能描述：根据线索二叉树的基本概念和存储结构可知，对于节点P不为null时，当P->Ltag=1时，P->LChild指向P的前驱
如果P的Ltag不为1，则判断P->Rtag是否等于0，如果等于0，则P->RChild指向前驱，否则P->LChild指向前驱节点
参数：BitNode *p 是需要操作的结点
返回值：前驱节点的值。
*/
BitNode * InPre(BitNode *p)
{
BitNode *pre=NULL;
if(p->Rtag==0) pre=p->RChild;
else pre= p->LChild;
return pre;
}
void Search(BiTree bt)
{
Array *store;
BitNode *pre;
int n;
store = (Array *)malloc(sizeof(Array));
store->i = -1;
PostOrder(bt, store);
printf(“\n”);
printf(“请输入查找节点的序号”);
scanf(“%d”, &n);
if (n > store->i)
{
printf(“节点序号错误\n”);
return;
}
pre = InPre(store->a[n]);
if (pre != NULL)
printf(“前驱节点值为%c\n”, pre->data);
else
printf(“无前驱节点\n”);
}
void PostOrder(BiTree root, Array *store)
{
if (root != NULL)
{
if (root->Ltag == 0)
PostOrder(root->LChild, store);
if (root->Rtag == 0)
PostOrder(root->RChild, store);
store->i++;
store->a[store->i] = root;
printf(“第%d号对应的节点是%c\n”, store->i, root->data);
}
}
int main()
{
BiTree *bt;
bt=(BiTree *)malloc(sizeof(BiTree *));
for(;;) // 无限循环,选择0 退出
{
switch(menu_select()) // 调用菜单函数，按返回值选择功能函数
{
case 1:
printf(“先序建立二叉树\n”);
CreateBiTree(bt);
break;
case 2:
printf(“后序二叉树线索化\n”);
Inthread(*bt);
break;
case 3:
printf(“查找前驱节点\n”);
Search(*bt);
break;
case 0:
printf(“再见!\n”); //退出系统
return 0;
} // switch语句结束
} // for循环结束
return 0;
} // main()函数结束