因为知道先序遍历后，第一个根是唯一确定的.然后在中序遍历里这个根将它分为两个部分，第一个根的两棵子树的根也会唯一确定，依次此类推，所有子树的根都唯一确定，二叉树就是唯一的.
解题步骤
1.由先序序列确定根结点(就是第一个字母了)
2.按根结点把中序序列分为两段，前面的是左子树，后面的是右子树
后面的步骤就基本是前面两步的重复
注意先序序列和中序序列的概念这题目就很容易的搞定
#include<stdio.h>
#include<stdlib.h>
typedef  char TElemType;
//Status是函数的类型，其值是函数结果状态码
typedef int status;
//函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
int w=0;
#define Link 0
#define Thread 1
typedef struct BiThrNode
{
TElemType data;
struct BiThrNode *lchild,*rchild; //左右孩子指针
int LTag,RTag;
}BiThrNode,*BiThrTree;
//构造二叉链表表示的二叉树
status createbitree(BiThrTree &T)
{
char ch;
scanf("%c",&ch);
if(ch=='$') T=NULL;
else
{
if(!(T=(BiThrNode *)malloc(sizeof(BiThrNode))))exit(OVERFLOW);
T->data =ch;
T->LTag=Link;
T->RTag=Link;
createbitree(T->lchild);
createbitree(T->rchild);
}
return OK;
}
void InThreading(BiThrTree &p,BiThrTree &pre) {  // 算法6.7
//BiThrTree pre;
if (p)
{
InThreading(p->lchild,pre);    // 左子树线索化
if (!p->lchild)  // 建前驱线索
{ p->LTag = Thread;  p->lchild = pre; }
if (!pre->rchild) // 建后继线索
{ pre->RTag = Thread;  pre->rchild = p; }
先序中序后序遍历二叉树pre = p;                  // 保持pre指向p的前驱
InThreading(p->rchild,pre);    // 右子树线索化
}
} // InThreading
//输出元素
status visit(TElemType e)
{
printf("%c",e);
return OK;
}
status InOrderTraverse_Thr(BiThrTree T, status (*Visit)(TElemType)) {
// 中序遍历二叉树T，并将其中序线索化，Thrt指向头结点。
BiThrTree Thrt,pre;
if (!(Thrt = (BiThrTree)malloc(sizeof(BiThrNode)))) exit(OVERFLOW);
Thrt->LTag = Link;  Thrt->RTag =Thread;  // 建头结点
Thrt->rchild = Thrt;              // 右指针回指
if (!T) Thrt->lchild = Thrt;      // 若二叉树空，则左指针回指
else {
Thrt->lchild = T;    pre = Thrt;
InThreading(T,pre);  // 算法6.7：中序遍历进行中序线索化
pre->rchild = Thrt;  pre->RTag = Thread; // 最后一个结点线索化
Thrt->rchild = pre; 
}
//*************************************************
/
/Thrt指向头结点，若树不空，头结点的ltag为0，lchild指向根结点
BiThrTree p;
printf("前序遍历线索二叉树：");
if(Thrt->LTag==0)
{
p=Thrt->lchild;
while(true)
{
while(p)
{
visit(p->data);
if(p->LTag==0)p=p->lchild; 
else break;
}
while(p->RTag&&p->rchild!=T){ p=p->rchild;}
if(p->rchild==T)break;
p=p->rchild;
}
}
printf("\n");
//**************************************************
// Thrt指向头结点，头结点的左链lchild指向根结点，头结点的右链lchild指向
/
/ 中序遍历的最后一个结点。中序遍历二叉线索链表表示的二叉树T，
// 对每个数据元素调用函数Visit。
printf("中序遍历线索二叉树:");
p = Thrt->lchild;                            // p指向根结点
while (p != Thrt) {                          // 空树或遍历结束时，p==T
while (p->LTag==Link) p = p->lchild;
if (!visit(p->data)) return ERROR;    // 访问其左子树为空的结点
while (p->RTag==Thread && p->rchild!=Thrt) {
p = p->rchild;  visit(p->data);    // 访问后继结点
}
p = p->rchild;  // p进至其右子树根
}
printf("\n");
return OK;
} // InOrderTraverse_Thr
//后序遍历
status b(BiThrTree T,status(* visit)(TElemType e))
{
if(T)
{
if(b(T->lchild ,visit))
if(b(T->rchild ,visit))
if(visit(T->data))
{
if(T->rchild==NULL&&T->lchild==NULL) w++;
return OK;
}
return ERROR;
}else
return OK;
}
void main()
{ 
BiThrTree T;
createbitree(T);
printf("后序遍历线索二叉树:");
b(T,visit);
printf("\n");
InOrderTraverse_Thr(T,visit);  //中序线索二叉树
printf("\n");
printf("叶子节点个数：");
printf("%d\n",w);
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。