{ Telemtype data;/*数据域*/
struct Bitnode *lchild, *rchild;
/*指针域,分别指向该结点的左、右孩子*/
}Bitnode,*Bitree;
【核心算法提示】
二叉树的遍历是指按某条搜索路径周游二叉树，对树中每个结点访问一次且仅访问一次。其中先序、中序和后序遍历操作步骤分别为：
（1）先序遍历：若二叉树为空树，则空操作；否则先访问根结点，再先序遍历左子树，最后先序遍历右子树。
（2）先序遍历：若二叉树为空树，则空操作；否则先中序遍历左子树，再访问根结点，最后中序遍历右子树。
（3）先序遍历：若二叉树为空树，则空操作；否则先后序遍历左子树，再后序遍历右子树，最后访问根结点。
注意：这里的“访问”的含义可以很广，几乎可以含盖对结点的任何一种操作。如：输出结点的信息、判断结点是否为叶子结点等等。
由于二叉树是一种递归定义，所以，要根据二叉树的某种遍历序列来实现建立一棵二叉树的二叉链表存储结构，则可以模仿对二叉树遍历的方法来加以实现。如：如果输入的是一棵二叉树的完整先序遍历序列，则可利用先序遍历方法先生成根结点，再用递归函数调用来实现左子树和右子树的建立。所谓完整的先序遍历序列就是在先序遍历序列中加入空树信息。
【核心算法描述】
void createbitree(Bitree &T)
/*根据输入的完整先序遍历序列建立一棵二叉树*/
{ scanf(\读取完整先序序列中的一个字符*/ if(x==‘#’) T=NULL; else
{ T=(Bitree)malloc(sizeof(Bitnode));/*生成根结点*/ T->data=x;
createbitree(T->lchild);/*递归建立左子树*/ createbitree(T->rchild); /*递归建立右子树*/ } }
void preorder(Bitree T) /*先序遍历二叉树*/ { if(T!=NULL)/*若二叉树非空*/
{ visit(T->data); /*访问根结点*/
preorder(T->lchild); /*递归先序遍历左子树*/ preorder(T->rchild); /*递归先序遍历右子树*/ }
}
void inorder(Bitree T) /*中序遍历二叉树*/ { if(T!=NULL) /*若二叉树非空*/
{ inorder(T->lchild); /*递归中序遍历左子树*/
31
visit(T->data); /*访问根结点*/
inorder(T->rchild); /*递归中序遍历右子树*/
}
}
void postorder(Bitree T) /*后序遍历二叉树*/ { if(T!=NULL) /*若二叉树非空*/
{ postorder(T->lchild); /*递归后序遍历左子树*/ postorder(T->rchild); /*递归后序遍历右子树*/ visit(T->data); /*访问根结点*/ } }
3．源程序代码参考
#include
struct Bitnode *lchild,*rchild; }Bitnode,*Bitree;
Bitree creat(Bitree T)/*建立二叉树函数*/ { char x;
scanf(\ if (x=='#') T=NULL; else
{T=(Bitree)malloc(sizeof(Bitnode)); if (!T)
{printf(\ exit(-1); } else
{T->data=x;
T->lchild=creat(T->lchild); T->rchild=creat(T->rchild); } } return T; }
Bitree preorder(Bitree T)/*先序遍历二叉树函数*/ { if (T!=NULL)
{ printf(\ preorder(T->lchild); preorder(T->rchild);
32
} }
void midorder(Bitree T) /*中序遍历二叉树函数*/ { if (T!=NULL)
{ midorder(T->lchild); printf(\ midorder(T->rchild); } }
void backorder(Bitree T) /*后序遍历二叉树函数*/ { if (T!=NULL)
{ backorder(T->lchild); backorder(T->rchild); printf(\ } }
main()/*主函数*/
{ Bitree T=NULL; char x;
printf(\请求输入二叉树中各个元素*/ T=creat(T);/*调用建立二叉树函数*/ while(1)
{ printf(\ printf(\ printf(\ printf(\
printf(\请求选择遍历方式*/ scanf(\ switch(x)
{case 1: printf(\
preorder(T); /*调用先序遍历二叉树函数*/ break;
case 2: printf(\
midorder(T); /*调用中序遍历二叉树函数*/ break;
case 3: printf(\
backorder(T); /*调用后序遍历二叉树函数*/ break; case 4: return;
33
default:printf(\ }
printf(\ } }
4．运行结果参考如图5-1所示：
图5-1： 验证性实验运行结果
说明：上述对应的二叉树如图5-2所示。
七、设计性实验(以下两个设计题目学生可根据自己的掌握程度或兴趣自行选择完成) 1．编程实现根据二叉树的先序遍历序列和中序遍历序列来建立两棵二叉树，并判断这两棵二叉树是否相等。
⑴ 实验要求
① 假设二叉树的结点值是字符，请分别根据输入的两棵二叉树的先序遍历序列和中序遍历序列来建立二叉链表表示的两棵二叉树。
图5-2：建立的二叉树
a b c e df 34
② 分别利用先序、中序和后序遍历方法来实现判断两棵二叉树是否相等的操作。 ③ 主程序中要求设计一个菜单，允许用户通过菜单来多次选择执行利用哪一种遍历方法来判断两棵二叉树是否相等。
⑵ 核心算法提示 1）二叉树的建立
二叉树的先序遍历序列：
根 左子树先序序列 右子树先序序列 二叉树的中序遍历序列：
左子树先序序列 根 右子树先序序列 图5-3： 二叉树的先序、中序遍历序列特征图
假设二叉树的先序遍历序列和中序遍历序列已经存储在数组Pre和Mid中，其序列分列具有如图5-3所示的特征。
根据此特征，建立二叉树的基本步骤可归纳为：
① 建立根结点，取先序先序遍历序列中的第一个字符作为根结点的数据域值； ② 在中序遍历序列中查找确定这个根结点在中序遍历序列中的位置，由此得到在根结点左边的序列即为此根结点左子树的中序遍历序列，而右边的序列即为此根结点右子树的中序遍历序列。
③ 根据左、右子树中序遍历序列中的字符个数再在先序遍历序列中确定左、右子树的先序遍历序列。
④ 根据（2）、（3）确定的左、右子树的先序和中序遍历序列采用递归调用的方法建立根结点的左、右子树。
2）判断两棵二叉树是否相等
假设T1和T2是两棵二叉树，如果两棵二叉树都是空树；或者两棵树的根结点的值相等，并且根结点的左、右子树分别也相等，则称二叉树T1与T2是相等的。所以，也可以利用先序、中序和后序遍历方法，采用递归函数来判断两棵树是否相等。假设两棵树相等，函数返回1，否则返回0。下面以用先序遍历方法为例，说明其基本操作步骤为：
① 如果两棵二叉树都为空，则函数返回1；
② 如果两棵二叉树都不为空，则先判断两棵树的根结点值是否相等，如果相等，则再采用递归调用的方法判断它的左、右子树是否相等，如果都相等则函数返回1；
③ 其它情况都返回0。 ⑶ 核心算法描述
char Pre[100],Mid[100]; /*存储先序和中序序列的字符数组，定义为全局变量*/ Bitree creat_sub(Bitree T,int Pre_start,int Pre_end,int Mid_start,int Mid_end) /*已知二叉树的先序序列和中序序列，建立此二叉树*/ { int i,ltreelen,rtreelen;
T=(Bitree)malloc(sizeof(Bitnode)); /*建立根结点*/
35