左子树的根。到后序序列中查找这个左子树的根，它将后序序列分成左、右两部分：左部分(包括所查到的结点)是二叉树的左子树(可能为空)，右部分(除去最后的根结点)则是右子树(可能为空)。这样，在确定根结点后，可递归确定左、右子树。 【算法6.55】
void creat(BiTree *BT,char pre[n],char post[n],int l1,int h1,int l2,int h2)
∥由严格二叉树的前序序列pre(l1:h1)和后序序列post(l2:h2)建立二叉树 { BiTree p=*BT; if(l1<=h1)
{p=(BiNode *)malloc(sizeof(BiNode));
p->data=pre[l1];∥前序序列的第一个元素是根 if(l1==h1) {p->lchild=p->rchild=null; }∥叶子结点 else ∥分支结点
{for(int i=l2;i<=h2;i++) ∥到后序序列中查左子树的根 if(post[i]==pre[l1+1] break;
L=i-l2+1; ∥左子树结点数
creat(&(p->lchild), pre,post,l1+1,l1+L,l2,i); creat(&(p->rchild), pre,post,l1+L+1,h1,i+1,h2-1); }∥else }∥if }∥结束
6.56编写一个递归算法，利用叶结点中空的右链指针域rchild，将所有叶结点自左至右链接成一个单链表，算法返回最左叶结点的地址（链头）。
【题目分析】叶子结点只有在遍历中才能知道，这里使用中序递归遍历。设置前驱结点指针pre，初始为空。第一个叶子结点由指针head指向，遍历到叶子结点时，就将它前驱的rchild指针指向它，最后叶子结点的rchild为空。 【算法6.56】
LinkedList head,pre=null; ∥全局变量 LinkedList InOrder(BiTree bt)
∥中序遍历二叉树bt，将叶子结点从左到右链成一个单链表，表头指针为head {if(bt){InOrder(bt->lchild); ∥中序遍历左子树 if(bt->lchild==null && bt->rchild==null)∥叶子结点
{if(pre==null) {head=bt; pre=bt;} ∥处理第一个叶子结点 else{pre->rchild=bt; pre=bt; } ∥将叶子结点链入链表 }
InOrder(bt->rchild); ∥中序遍历右子树 }
pre->rchild=null; ∥设置链表尾 return(head); } ∥InOrder
6.57已知有一棵二叉链表表示的二叉树，编写算法，输出从根结点到叶子结点的最长一枝上的所有结点。
【题目分析】后序遍历时栈中保留当前结点的祖先的信息，用一变量保存栈的最高栈顶指针，每当退栈时，栈顶指针大于已保存的最高栈顶指针的值时，则将该栈倒入辅助栈中，辅助栈始终保存最长路径长度上的结点，直至后序遍历完毕，则辅助栈中内容即为所求。 【算法6.57】
void LongestPath(BiTree bt)
∥求二叉树从根结点到叶子结点的最长一枝上的所有结点 {BiTree p=bt,l[],s[];
∥l, s是栈，元素是二叉树结点指针，l中保留当前最长路径中的结点 int i，top=0,tag[],longest=0; while(p || top>0)
{while(p){s[++top]=p；tag[top]=0; p=p->lchild;}∥沿左分枝向下 if(tag[top]==1) ∥当前结点的右分枝已遍
历
{if(!s[top]->lchild && !s[top]->rchild) ∥只有到叶子结点时，才查看路径长度 if(top>longest)
{for(i=1;i<=top;i++) l[i]=s[i]; longest=top; top--; }
}∥保留当前最长路径到l栈，记住最高栈顶指针，退栈 while(top>0 && tag[top]==1) top--; ∥退栈 if(top>0)
{tag[top]=1; p=s[top].rchild;} ∥沿右子分枝向下 }∥while(p!=null||top>0) }∥结束LongestPath
6.58试编写一算法对二叉树进行前序线索化。
【题目分析】线索化是在遍历中完成的，因此，对于二叉树进行前序、中序、后序遍历，在“访问根结点”处进行加线索的改造，就可实现前序，中序和后序的线索化。 【算法6.58】
BiThrTree pre=null;∥设置前驱 void PreOrderThreat(BiThrTree BT)
∥对以线索链表为存储结构的二叉树BT进行前序线索化 {if(BT!=null)
{if(BT->lchild==null){BT->ltag=1; BT->lchild=pre;}∥设置左线索 if(pre!=null && pre->rtag==1) pre->rchild=BT; ∥设置前驱的右线索； if(BT->rchild==null) BT->rtag=1; ∥为建立右链作准备 pre=BT; ∥前驱后移
if(BT->ltag==0) PreOrderThreat(BT->lchild); ∥左子树前序线索化
PreOrderThreat(BT->rchild); ∥右子树前序线索化 }∥if(BT!=null) }∥结束PreOrderThreat
6.59试编写一算法对二叉树进行中序线索化。 【算法6.59】 BiThrTree pre==null;
void InOrderThreat(BiThrTree T)∥对二叉树进行中序线索化 {if(T)
{InOrderThreat(T->lchild); ∥左子树中序线索化 if(T->lchild==null){T->ltag=1; T->lchild=pre;} ∥左线索为pre if(pre!=null && pre->rtag==1) pre->rchild=T;} ∥给前驱加后继线索 if(T->rchild==null) T->rtag=1; ∥置右标记，为右线索作准备
pre=BT; ∥前驱指针后移 InOrderThreat(T->rchild); ∥右子树中序线索化 }∥if
}∥结束InOrderThreat
6.60设p指向前序线索二叉树t的某结点，编写算法求*p结点的后继结点。 【题目分析】在前序线索二叉树中，求*p结点的后继结点，若*p结点有左子女，则左子女是其后继结点；若*p结点无左子女而有右子女，则右子女是其后继；若*p结点无左、右子女，线索p->rchild指向其后继。 【算法6.60】
BiThrTree PreorderNext(BiThrTree p) {if (p->ltag==0) // 结点有左子女
return(p->lchild); //结点的左子女为其前序后继 else
return(p->rchild);//p->rchild为其前序后继 } // PreorderNext
6.61设p指向后序线索二叉树t的某结点，编写算法求*p结点的前驱结点。 【题目分析】在后序线索二叉树中，求*p结点的前驱结点，若*p结点有右子女，则右子女是其前驱结点；若*p结点无右子女而有左子女，则左子女是其前驱；若*p结点既无右子女又无左子女，线索p->lchild指向其前驱。 【算法6.61】
BiThrTree PostorderPre(BiThrTree p) { if (p->rtag==0) // 结点有右子女
return(p->rchild); //结点的右子女为其后序前驱 else
return(p->lchild) ;//p->lchild为其后序前驱 } // PreorderPre
6.62设计算法求中序线索二叉树中指针P所指结点的前驱结点的指针。 【题目分析】中序线索二叉树中，指针P所指结点的前驱结点的特征是：若p->ltag=1,p->lchild指向其前驱，否则，P的左子树上按中序遍历的最后结点是其中序前驱。 【算法6.62】
BiThrTree InPre(BiThrTree T, BiThrTree p) ∥在中序线索树T中，查找给定结点p的中序前驱
{if（p->ltag==1）q=p->lchild; ∥若p的左标志为1，用其左指针指向前驱 else {q=p->lchild; while(q->rtag==0)
q=q->rchild; ∥p的前驱为其左子树中最右下的结点 }
return (q); }∥结束InPre
6.63设计算法求中序线索二叉树中指针P所指结点的后继结点的指针。
【题目分析】中序线索二叉树中，指针P所指结点的后继结点的特征是：若p->rtag=1,p->rchild指向其后继，否则，P的右子树上按中序遍历的第一个结点是其中序后继。 【算法6.63】
BiThrTree InSucc(BiThrTree T, BiThrTree p) ∥在中序线索二叉树T中，查找给定结点p的中序后继 {if（p->rtag==1）
q=p->rchild; ∥若p的右标志为1，用其右指针指向后继 else {q=p->rchild; while(q->ltag==0)
q=q->lchild; ∥p的后继为其右子树中最左下的结点 }
return (q); }∥结束InSucc