void LevleOrder(BiTree T)
{ /*层次遍历二叉树T，从第一层开始，每层从左到右*/
BiTree Queue[MAX],b;/*用一维数组表示队列，front和rear分别表示队首和队尾指针*/
int front,rear; front=rear=0;
if(T) /*若树非空*/ {
Queue[rear++]=T; /*根结点入队列*/ while (front!=rear)
{ /*当队列非空*/
b=Queue[front++]; /*队首元素出队列，并访问这个结点*/ printf(\
if(b->lchild!=NULL) Queue[rear++]=b->lchild; /*左子树非空，则入队列*/ if(b->rchild!=NULL) Queue[rear++]=b->rchild; /*右子树非空，则入队列*/ } }
}/*LevelOrder*/ void main() {
BiTree T=NULL,B;
printf(\请读入构造二叉树的字符序列:\
B=CreateBiTree(T); /*建立一棵二叉树T*/ printf(\该二叉树的先序遍历是:\
PreOrderTraverse(B,PrintElement); /*先序遍历二叉树*/ printf(\该二叉树的中序遍历\
InOrderTraverse( B, PrintElement ); /*中序遍历二叉树*/ printf(\该二叉树的后序遍历\
PostOrderTraverse( B,PrintElement); /*后序遍历二叉树*/ printf(\该二叉树的层次遍历是:\
LevleOrder(B); /*层次遍历二叉树*/ getchar(); } }
[实验3]叶子结点统计
实验内容与要求：
统计一棵二叉树的叶子结点的个数 分析： 叶子结点是二叉树中既没有左孩子又没有有孩子的结点。
采用递归方式。求一棵二叉树的叶子结点数的递归模型如下。 f(bt)=0; 若为空树时
6
f(bt)=1; 若只有根结点时,该根结点是叶结点 f(bt)=f(btree->lchild)+f(btree->rchild); 其它 参考程序：
#include
{/*统计二叉树bt中叶子结点数*/ int n;
if(bt==NULL) n=0;
else if(bt->lchild==NULL&&bt->rchild==NULL) n=1; else n=leafcount(bt->lchild)+leafcount(bt->rchild);
/*二叉树叶子结点数等于左、右子树的叶子结点数之和*/ return n; }
void main(){
BiTree T=NULL; int m;
printf(\请输入要构造二叉树的结点序列:\ T=CreateBiTree(T); /*建立一棵二叉树T*/ m=leafcount(T);
printf(\叶子结点数是:%d\ getchar(); getchar(); }
[实验４]二叉树的深度统计
实验内容与要求：
统计一棵二叉树的深度。 分析
若一棵二叉树是空树，则它的深度为０，否则它的深度取值为它的左、右子树中深度最大的深度加１。
int depth(BiTree T){ /*求二叉树的深度*/ int dep1,dep2;
if (T==NULL) return 0; else {
dep1=depth(T->lchild); dep2=depth(T->rchild);
return dep1>dep2?dep1+1:dep2+1; ｝ }//depth 参考程序：
//以下代码存放在文件shiyan6_1_4.c 文件中
7
#include
{ /*求二叉树的深度*/ int dep1,dep2; if (T==NULL) return ERROR; else {
dep1=depth(T->lchild); dep2=depth(T->rchild);
return dep1>dep2?dep1+1:dep2+1; }
}/*depth*/ void main() {
BiTree T=NULL;
printf(\请输入所构造二叉树的结点序列：\ T=CreateBiTree(T); /*建立一棵二叉树T*/ printf(\二叉树的深度是:%d\getchar(); }
[实验5]子树交换
实验内容与要求：
试编写算法，对一棵二叉树根结点不变，将左、右子树进行交换，树中每个结点的左、右子树进行交换。 分析：
子树交换就是将原来的二叉树中每个结点的左、右子树分别交换生成一棵新的二叉树，该二叉树与原来二叉树成对称形状。
先将二叉树根结点的左、右子树交换，然后在将左（右）子树的左、右子树交换直到子树为空树。
void Exchange(BiTree T) {
BiTNode p; if (T) {
p = T->lchild;
T->lchild = T->rchild; T->rchild = p; Exchange(T->lchild); Exchange(T->rchild);
8
}
}
参考程序：
//以下代码存放在文件shiyan6_1_5.c #include
#include \ void Exchange(BiTree T) {
BiTNode *p; if(T) {
p=T->lchild;
T->lchild=T->rchild; T->rchild=p;
Exchange(T->lchild); Exchange(T->rchild); } }
void main() {
BiTree T=NULL;
printf(\请输入要构造二叉树的节点序列:\T=CreateBiTree(T); /*建立一棵二叉树T*/ Exchange( T) ; }
[实验6]线索二叉树
实验内容与要求：
构造一棵二叉链表表示的二叉树，并将其中序遍历线索化。 分析：
在一棵有N个结点的二叉树中，有N+1个指针域为空。把这些空的指针项加以利用，将空的左指针指向其前驱，空的右指针指向后继， 这样的指针九百能了线索。线索化就是通过将空的左指针指向其前驱，空的右指针指向其后继，使非线性的二叉树线性化的过程。
线索二叉树采用线索链表表示，链表结构为图6-2（b）所示，在二叉链表结构(图6-2(a)所示)的基础上增加了两个标志域LTag和RTag。这两个标志域当其值为1时，指向其前驱和后继。值为0时保持其指针指向不变。
具体情况： lchild LTag data RTag rchild lchild data rchild 图6-2链表结构和线索链表结构
9
中序遍历线索化二叉树就是在对线索树中序遍历的过程中为左标志域为1的结点寻找前驱，为由标志域为1的结点寻找后继。结点的后继是中序遍历其右子树时访问的第一个结点，结点的前驱是中序遍历其左子树时最后访问的一个结点。
先构造一棵用线索链表表示的二叉树T，辅设一个全局变量pre用于记录离当前结点p最后“访问”的结点。对该二叉树T进行中序遍历，生成线索化后二叉树的头结点Thrt，如果p的左标志域为空，则将其变为线索，并让其左指针指向pre，pre就是中序遍历二叉树Thrt时p结点的前驱；如果pre的右标志域为空，则p就是pre的后继，将pre的右标志域变为线索。 参考程序：
//以下代码保存在文件shiyan6_1_6.c中 #include
typedef char DataType; /*定义DataType类型*/ typedef enum {Link,Thread} PointerTag; typedef struct node{ DataType data;
struct node *lchild, *rchild; /*左右孩子子树*/ PointerTag LTag,RTag; }BiThrNode; /*结点类型*/
typedef BiThrNode *BiThrTree ; /*二叉树类型*/ /*构造二叉树*/
void CreatBinTree(BiThrTree *T)
{ /*构造二叉链表,注意:输入序列是先序序列*/ char ch;
if ((ch=getchar())==' ') *T=NULL; else
{ /*读入非空格*/
T=(BiThrNode *)malloc(sizeof(BiThrNode)); /*生成结点*/ (*T)->data=ch;(*T)->LTag=Link;(*T)->RTag=Link;
CreatBinTree(&(*T)->lchild); /*构造左子树 */ CreatBinTree(&(*T)->rchild); /*构造右子树*/ }
}
BiThrTree pre;/*全局变量*/ void InThreading(BiThrTree p)
10
0 lchild域指示结点的左孩子 LTag= 1 lchild域指示结点的前驱 0 rchild域指示结点的右孩子 RTag= 1 rchild域指示结点的后继