[题目] 建立二叉树并求指定结点路径、深度、叶子个数和左右子树交换。
[问题描述]
要求能够按先序遍历次序输入二叉树 中结点的值来构造二叉树T；然后用递归和非递归算法实现二叉树T 的中序遍历；接着编写算法实现求二叉树T中指定结点的路径，即从键盘输入二叉树T 的任一结点，可以输出从根结点到该 结点所经历的结点；最后编写二叉树的三个应用算法（求二叉树的深度、求二叉树的叶子结点个数、将二叉树左右子树交换）。
[基本要求]
分别建立二叉树存储结构的输入输出函数、输出中序遍历函数、指定节点路径函数、求深度函数、求叶子个数函数和将二叉树左右子树交换函数
一、需求与规格说明
1、定义二叉树的存储结构，每个结点中设置三个域，即值域、左指针域、右指针域。要建立二叉树T的链式存储结构，即建立二叉链表。根据输入二叉树结点的形式不同，建立的方法也不同，本系统采用先序序列递归建立二叉树，建立如下图所示的二叉树。应该在程序运行窗口的主控菜单后，先选择“1”并回车，紧接着在程序运行窗口中提示信息“输入二叉树的先序序列结点值:”之后，采用以下字符序列：abc@@de@g@@f@@@ （以@替代空格，但是程序中直接输入空格就是，详细见代码注释）作为建立二叉树T的输入字符序列并回车，窗口出现：二叉树的链式存储结构建立完成!
图1 二叉树的图形结构
2、二叉树的遍历。本系统采用非递归中序遍历算法进行中序遍历，这意味着遍历右子树时不再需要保存当前层的根指针，可直接修改栈顶记录中的指针即可。需要在程序运行窗口的主控菜单中选择“2” 并回车，程序运行窗口会出现以下中序遍历序列：
该二叉树
的中序遍历序列是: cbegdfa
3、求二叉树的指定结点路径。在程序运行窗口的主控菜单中选择“3” 并回车，在程序运行窗口中提示信息“输入要求路径的结点值:”输入“g” 并回车，会得到结果为： →a→b→d→e→g如果输入“i” 并回车，会得到结果为：没有要求的结点！
4、求二叉树的深度。在程序运行窗口的主控菜单中选择“4” 并回车，在会得到结果为： 该二叉树的深度为：5
5、求二叉树的叶子结点个数。在程序运行窗口的主控菜单中选择“5” 并回车，在会得到结果为：该二叉树的叶子结点数为：3
6、将二叉树左右子树交换（此处我用交换后的中序遍历来检验是否成功）。在程序运行窗口的主控菜单中选择“6” 并回车.得到结果为：该二叉树的左右节点已交换成功，其中序遍历序列是：afdgebc
7、退出程序。在程序运行窗口的主控菜单中选择“0” 并回车。退出程序。
二、设计
1、设计思想
在二叉树上无论采用哪种遍历方法，都能够访问遍树中的所有结点。由于访问结点的顺序不同，前序遍历和中序遍历都很难达到设计的要求（求路径）；但采用后序遍历二叉树是可行的，因为后序遍历是最后访问根结点，按这个顺序将访问过的结点存储到一个顺序栈中，然后再输出即可。因此，我们可以非递归地后序遍历二叉树T，当后序遍历访问到结点*p时，此时栈中存放的所有结点均为给定结点*p的祖先，而由这些祖先便构成了一条从根结点到结点*p之间的路径。而求二叉树的深度和叶子结点数可以直接判断结点孩子的数目来完成，将二叉树的左右子树交换也可以利用递归的方法，交换左右孩子来实现。
2、设计表示
为实现上述的设计思想，首先要定义二叉树的链式存储结构，我们采用二叉链表的方式，相应的类型说明为：
typedef char DataType;
typedef struct node{
DataType data; struct node *lchild,*rchild;
}BinTNode,*BinTree;
函数接口说明:
Status CreateBiTree(BinTree &bt) //1,按照先序遍历次序递归建立二叉树
Status Inorder(BinTree bt) //2,二叉树非递归中序遍历算法*/
BinTree NodePath(BinTree bt, BinTNode *ch) //3,求二叉树根结点到给定结点*p的路径 int Depth(BinTree bt) //4.求二叉树的深度
int Leaf(BinTree bt)// 5.求二叉树的叶子结点个数
BinTNode *huhuan(BinTNode *p)// 将p指针指向的二叉树的左右子树进行互换
函数调用关系如图所示：
三、实现注释
二叉树的创建模块: 按照先序遍历次序递归建立二叉树,通过读入的字符，分配存储空间生成新结点后再逐个构建根结点、左子树和右子树。
二叉树中序遍历模块：采用非递归中序遍历算法，先逐步扫描二叉树的左子树，并压入堆栈，如果栈不为空，左子树为空，则弹出栈顶的一个元素并输出。然后再扫描右子树，然后再重复上面的步骤扫描该分支的左子树，直至整棵二叉树都扫描完成。此时输出的序列便是该二叉树的中序遍历序列。语句注释见代码。
二叉树指定结点路径模块：该模块由NodePath、FindBT、Findx三个函数体构成，main函数通过先调用Findx 函数来查找结点，Findx又通过逐步调用FindBT函数遍历查找结点的路径，最后main函数再通过调用NodePath函数得到给定结点的路径。该模块需定义全局变量p和found以方便查找，否则容易出错，出错情况见调试报告。语句注释见代码。
求二叉树的深度模块：通过判断左右孩子结点是否存在，如存在（h不等于零），则
有一个孩子h加一，然后比较左右孩子结点数大小，较大的为树的深度。具体见代码。
求二叉树的叶子结点个数模块：判断左右子树的叶子结点是否存在，如存在，则记下，左后返回左右子树叶子结点的和。具体见代码。
二叉树的左右子树进行互换模块：通过指针p指定结点，然后用递归的方法将其孩子结点互换。具体见代码。
四、调试报告
编程的最初阶段，在case4语句中，缺少break，使得每次执行case4的时候，自动弹出该二叉树的叶子节点数，经过调试后发现，原来是缺少了break，补上之后，程序正常运行。其实这只是很小的问题！在调试中，还有很多的问题，如果在这里一一列举，恐怕很难写完。具体的看运行结果吧。
五、程序清单
#include
#include
#define num 100
#define OK 1
typedef int Status;
typedef char DataType;
typedef struct node{
DataType data; struct node *lchild,*rchild;
}BinTNode,*BinTree;
int found;
BinTNode *p;
Status CreateBiTree(BinTree &bt) //1.按照先序遍历次序递建立二叉树。
{ //ABC@@DE@G@@F@@@ 以@代替空格。但是程序中直接输入空格。
char ch; printf("ch="); scanf("%c",&ch); getchar(); if (ch==' ') bt=NULL; //程序中直接输入空格，不用以@代替空格。
} else { bt=(BinTNode *)malloc(sizeof(BinTNode)); bt->data=ch; //生成根结点 CreateBiTree(bt->lchild); //构造左子树 CreateBiTree(bt->rchild); //构造右子树 } return OK;
Status Inorder(BinTree bt) //二叉树非递 中序遍历算法
{ BinTNode *stack[num]; //定义栈数组
}
BinTree NodePath(BinTree bt, BinTNode *ch) //3.求二叉树指定结点的路径 { typedef enum{FALSE,TRUE}boolean;
BinTNode *stack[num];//定义栈
int i,top,tag[num];
boolean find;
BinTNode *s;
find=FALSE;//初始化
int top=0; //初始化栈 stack[top]=bt; do { while(NULL!=stack[top]) //扫描根结点及其所有的左结点并入栈 { top=top+1; } top=top-1; //退栈 if(top>=0) //判断栈是否为空 { printf("%c",stack[top]->data); //访问结点 } stack[top]=stack[top]->rchild; //扫描右子树 stack[top]=stack[top-1]->lchild; }while(top>=0); return OK;
top=0;
s=bt;
do
{while(s!=NULL)
{ top++; } if(top>0) {s=stack[top]; if(tag[top]==1) { if(s==ch) {for(i=1;i%c",stack[i]->data); stack[top]=s; tag[top]=0; s=s->lchild; find=TRUE; top--; }else s=stack[top]; }//endif if(top>0&&!find) { if(tag[top]!=1) { s=s->rchild;//扫描右子树 tag[top]=1; } else s=NULL; }//end if } //endif
}while(!find&&top!=0);
return s;
}
void FindBT(BinTree bt,DataType x)
{ if((bt!=NULL)&&!found)
} { if(bt->data==x) } { p=bt; found=1; } else { FindBT(bt->lchild,x); FindBT(bt->rchild,x); }
BinTNode *Findx(BinTree bt,DataType x)
{ int found=0;
}
int Depth(BinTree bt) //4.求二叉树的深度
{ int h,lh,rh;
if (bt==NULL) h=0; else { lh=Depth(bt->lchild); rh=Depth(bt->rchild); if (lh>=rh) h=lh+1; else h=rh+1; BinTree p=NULL; FindBT(bt,x); return(p); } return h;
}//Depth
int Leaf(BinTree bt) //5.求二叉树的叶子结点个数
{ if (bt==NULL) return 0;
else if (bt->lchild==NULL&&bt->rchild==NULL) return 1; else return Leaf(bt->lchild)+Leaf(bt->rchild);
}//Leaf
BinTNode *huhuan(BinTNode *p)
//将p指针指向的二叉树的左右子树进行互换。
{BinTNode *stack[num];//指针类型的堆栈
int k=0;
stack[k]=NULL;
if(p!=NULL)//交换p结点的左右孩子
{ k++;
stack[k]=p->lchild;
p->lchild=p->rchild;
p->rchild=stack[k];
p->lchild=huhuan(p->lchild);
p->rchild=huhuan(p->rchild);
} return (p);
}
void main()
{ BinTree bt;
//BinTNode *root; char ch1; int xz=1,sd=0,yz=0; while(xz) { printf(" 建立二叉树并求指定结点路径 \n"); printf("============================\n"); printf(" 1.建立二叉树的存储结构 \n"); printf(" 2.求解二叉树的中序遍历 \n"); printf(" 3.求二叉树指定结点的路径 \n"); printf(" 4.求二叉树的深度 \n"); printf(" 5.求二叉树的叶子结点个数 \n"); printf(" 6.将二叉树左右子树交换 \n"); printf(" 0.退出系统 \n"); printf("============================\n"); printf(" 请选择：(0-6) \n");
getchar(); switch(xz)
{ // 输入:ABC@@DE@G@@F@@@ 输出: CBEGDFA case 1:printf("输入二叉树的先序序列结点值:\n");
CreateBiTree(bt); printf( "二叉树的链式存储结构建立完成!\n"); break; case 2:printf("该二叉树的中序遍历序列是:\n"); Inorder(bt); printf( "\n"); break; case 3:printf( "请输入要求路径的结点值：\n" ); ch1=getchar(); p=NULL; found=0; Findx(bt,ch1); if(p!=NULL) NodePath(bt,p); else printf( "没有要求的节点！ \n" ); printf( "\n" ); break; case 4:sd=Depth(bt); printf( "该二叉树的深度为：%d \n ",sd ); printf("\n"); break; case 5:yz=Leaf(bt); printf( "该二叉树的叶子节点数为：\n%d \n",yz ); printf( "\n" ); break;
printf( "该二叉树的左右结点已交换成功，其中序遍历序列
是:\n" );
Inorder(bt);
printf( "\n" );
break;
}// switch
}// while
}
六、运行结果截图
11
参考文献：
[1]严蔚敏,吴伟民.数据结构(C 语言版).北京:清华大学出版社,2010
[2]严蔚敏,吴伟民等.数据结构题集(C 语言版).北京:清华大学出版社,2010
[3]苏仕华等.数据结构 程设计.北京:机械工业出版社,2008
12
[题目] 建立二叉树并求指定结点路径、深度、叶子个数和左右子树交换。
[问题描述]
要求能够按先序遍历次序输入二叉树 中结点的值来构造二叉树T；然后用递归和非递归算法实现二叉树T 的中序遍历；接着编写算法实现求二叉树T中指定结点的路径，即从键盘输入二叉树T 的任一结点，可以输出从根结点到该 结点所经历的结点；最后编写二叉树的三个应用算法（求二叉树的深度、求二叉树的叶子结点个数、将二叉树左右子树交换）。
[基本要求]
分别建立二叉树存储结构的输入输出函数、输出中序遍历函数、指定节点路径函数、求深度函数、求叶子个数函数和将二叉树左右子树交换函数
一、需求与规格说明
1、定义二叉树的存储结构，每个结点中设置三个域，即值域、左指针域、右指针域。要建立二叉树T的链式存储结构，即建立二叉链表。根据输入二叉树结点的形式不同，建立的方法也不同，本系统采用先序序列递归建立二叉树，建立如下图所示的二叉树。应该在程序运行窗口的主控菜单后，先选择“1”并回车，紧接着在程序运行窗口中提示信息“输入二叉树的先序序列结点值:”之后，采用以下字符序列：abc@@de@g@@f@@@ （以@替代空格，但是程序中直接输入空格就是，详细见代码注释）作为建立二叉树T的输入字符序列并回车，窗口出现：二叉树的链式存储结构建立完成!
图1 二叉树的图形结构
2、二叉树的遍历。本系统采用非递归中序遍历算法进行中序遍历，这意味着遍历右子树时不再需要保存当前层的根指针，可直接修改栈顶记录中的指针即可。需要在程序运行窗口的主控菜单中选择“2” 并回车，程序运行窗口会出现以下中序遍历序列：
该二叉树
的中序遍历序列是: cbegdfa
3、求二叉树的指定结点路径。在程序运行窗口的主控菜单中选择“3” 并回车，在程序运行窗口中提示信息“输入要求路径的结点值:”输入“g” 并回车，会得到结果为： →a→b→d→e→g如果输入“i” 并回车，会得到结果为：没有要求的结点！
4、求二叉树的深度。在程序运行窗口的主控菜单中选择“4” 并回车，在会得到结果为： 该二叉树的深度为：5
5、求二叉树的叶子结点个数。在程序运行窗口的主控菜单中选择“5” 并回车，在会得到结果为：该二叉树的叶子结点数为：3
6、将二叉树左右子树交换（此处我用交换后的中序遍历来检验是否成功）。在程序运行窗口的主控菜单中选择“6” 并回车.得到结果为：该二叉树的左右节点已交换成功，其中序遍历序列是：afdgebc
7、退出程序。在程序运行窗口的主控菜单中选择“0” 并回车。退出程序。
二、设计
1、设计思想
在二叉树上无论采用哪种遍历方法，都能够访问遍树中的所有结点。由于访问结点的顺序不同，前序遍历和中序遍历都很难达到设计的要求（求路径）；但采用后序遍历二叉树是可行的，因为后序遍历是最后访问根结点，按这个顺序将访问过的结点存储到一个顺序栈中，然后再输出即可。因此，我们可以非递归地后序遍历二叉树T，当后序遍历访问到结点*p时，此时栈中存放的所有结点均为给定结点*p的祖先，而由这些祖先便构成了一条从根结点到结点*p之间的路径。而求二叉树的深度和叶子结点数可以直接判断结点孩子的数目来完成，将二叉树的左右子树交换也可以利用递归的方法，交换左右孩子来实现。
2、设计表示
为实现上述的设计思想，首先要定义二叉树的链式存储结构，我们采用二叉链表的方式，相应的类型说明为：
typedef char DataType;
typedef struct node{
DataType data; struct node *lchild,*rchild;
}BinTNode,*BinTree;
函数接口说明:
Status CreateBiTree(BinTree &bt) //1,按照先序遍历次序递归建立二叉树
Status Inorder(BinTree bt) //2,二叉树非递归中序遍历算法*/
BinTree NodePath(BinTree bt, BinTNode *ch) //3,求二叉树根结点到给定结点*p的路径 int Depth(BinTree bt) //4.求二叉树的深度
int Leaf(BinTree bt)// 5.求二叉树的叶子结点个数
BinTNode *huhuan(BinTNode *p)// 将p指针指向的二叉树的左右子树进行互换
函数调用关系如图所示：
三、实现注释
二叉树的创建模块: 按照先序遍历次序递归建立二叉树,通过读入的字符，分配存储空间生成新结点后再逐个构建根结点、左子树和右子树。
二叉树中序遍历模块：采用非递归中序遍历算法，先逐步扫描二叉树的左子树，并压入堆栈，如果栈不为空，左子树为空，则弹出栈顶的一个元素并输出。然后再扫描右子树，然后再重复上面的步骤扫描该分支的左子树，直至整棵二叉树都扫描完成。此时输出的序列便是该二叉树的中序遍历序列。语句注释见代码。
二叉树指定结点路径模块：该模块由NodePath、FindBT、Findx三个函数体构成，main函数通过先调用Findx 函数来查找结点，Findx又通过逐步调用FindBT函数遍历查找结点的路径，最后main函数再通过调用NodePath函数得到给定结点的路径。该模块需定义全局变量p和found以方便查找，否则容易出错，出错情况见调试报告。语句注释见代码。
求二叉树的深度模块：通过判断左右孩子结点是否存在，如存在（h不等于零），则
有一个孩子h加一，然后比较左右孩子结点数大小，较大的为树的深度。具体见代码。
求二叉树的叶子结点个数模块：判断左右子树的叶子结点是否存在，如存在，则记下，左后返回左右子树叶子结点的和。具体见代码。
二叉树的左右子树进行互换模块：通过指针p指定结点，然后用递归的方法将其孩子结点互换。具体见代码。
四、调试报告
编程的最初阶段，在case4语句中，缺少break，使得每次执行case4的时候，自动弹出该二叉树的叶子节点数，经过调试后发现，原来是缺少了break，补上之后，程序正常运行。其实这只是很小的问题！在调试中，还有很多的问题，如果在这里一一列举，恐怕很难写完。具体的看运行结果吧。
五、程序清单
#include
#include
#define num 100
#define OK 1
typedef int Status;
typedef char DataType;
typedef struct node{
DataType data; struct node *lchild,*rchild;
}BinTNode,*BinTree;
int found;
BinTNode *p;
Status CreateBiTree(BinTree &bt) //1.按照先序遍历次序递建立二叉树。
{ //ABC@@DE@G@@F@@@ 以@代替空格。但是程序中直接输入空格。
char ch; printf("ch="); scanf("%c",&ch); getchar(); if (ch==' ') bt=NULL; //程序中直接输入空格，不用以@代替空格。
} else { bt=(BinTNode *)malloc(sizeof(BinTNode)); bt->data=ch; //生成根结点 CreateBiTree(bt->lchild); //构造左子树 CreateBiTree(bt->rchild); //构造右子树 } return OK;
Status Inorder(BinTree bt) //二叉树非递 中序遍历算法
{ BinTNode *stack[num]; //定义栈数组
}
BinTree NodePath(BinTree bt, BinTNode *ch) //3.求二叉树指定结点的路径 { typedef enum{FALSE,TRUE}boolean;
BinTNode *stack[num];//定义栈
int i,top,tag[num];
boolean find;
BinTNode *s;
find=FALSE;//初始化
int top=0; //初始化栈 stack[top]=bt; do { while(NULL!=stack[top]) //扫描根结点及其所有的左结点并入栈 { top=top+1; } top=top-1; //退栈 if(top>=0) //判断栈是否为空 { printf("%c",stack[top]->data); //访问结点 } stack[top]=stack[top]->rchild; //扫描右子树 stack[top]=stack[top-1]->lchild; }while(top>=0); return OK;
top=0;
s=bt;
do
{while(s!=NULL)
{ top++; } if(top>0) {s=stack[top]; if(tag[top]==1) { if(s==ch) {for(i=1;i%c",stack[i]->data); stack[top]=s; tag[top]=0; s=s->lchild; find=TRUE; top--; }else s=stack[top]; }//endif if(top>0&&!find) { if(tag[top]!=1) { s=s->rchild;//扫描右子树 tag[top]=1; } else s=NULL; }//end if } //endif
}while(!find&&top!=0);
return s;
}
void FindBT(BinTree bt,DataType x)
{ if((bt!=NULL)&&!found)
} { if(bt->data==x) } { p=bt; found=1; } else { FindBT(bt->lchild,x); FindBT(bt->rchild,x); }
BinTNode *Findx(BinTree bt,DataType x)
{ int found=0;
}
int Depth(BinTree bt) //4.求二叉树的深度
{ int h,lh,rh;
if (bt==NULL) h=0; else { lh=Depth(bt->lchild); rh=Depth(bt->rchild); if (lh>=rh) h=lh+1; else h=rh+1; BinTree p=NULL; FindBT(bt,x); return(p); } return h;
}//Depth
int Leaf(BinTree bt) //5.求二叉树的叶子结点个数
{ if (bt==NULL) return 0;
else if (bt->lchild==NULL&&bt->rchild==NULL) return 1; else return Leaf(bt->lchild)+Leaf(bt->rchild);
}//Leaf
BinTNode *huhuan(BinTNode *p)
//将p指针指向的二叉树的左右子树进行互换。
{BinTNode *stack[num];//指针类型的堆栈
int k=0;
stack[k]=NULL;
if(p!=NULL)//交换p结点的左右孩子
{ k++;
stack[k]=p->lchild;
p->lchild=p->rchild;
p->rchild=stack[k];
p->lchild=huhuan(p->lchild);
p->rchild=huhuan(p->rchild);
} return (p);
}
void main()
{ BinTree bt;
//BinTNode *root; char ch1; int xz=1,sd=0,yz=0; while(xz) { printf(" 建立二叉树并求指定结点路径 \n"); printf("============================\n"); printf(" 1.建立二叉树的存储结构 \n"); printf(" 2.求解二叉树的中序遍历 \n"); printf(" 3.求二叉树指定结点的路径 \n"); printf(" 4.求二叉树的深度 \n"); printf(" 5.求二叉树的叶子结点个数 \n"); printf(" 6.将二叉树左右子树交换 \n"); printf(" 0.退出系统 \n"); printf("============================\n"); printf(" 请选择：(0-6) \n");
getchar(); switch(xz)
{ // 输入:ABC@@DE@G@@F@@@ 输出: CBEGDFA case 1:printf("输入二叉树的先序序列结点值:\n");
CreateBiTree(bt); printf( "二叉树的链式存储结构建立完成!\n"); break; case 2:printf("该二叉树的中序遍历序列是:\n"); Inorder(bt); printf( "\n"); break; case 3:printf( "请输入要求路径的结点值：\n" ); ch1=getchar(); p=NULL; found=0; Findx(bt,ch1); if(p!=NULL) NodePath(bt,p); else printf( "没有要求的节点！ \n" ); printf( "\n" ); break; case 4:sd=Depth(bt); printf( "该二叉树的深度为：%d \n ",sd ); printf("\n"); break; case 5:yz=Leaf(bt); printf( "该二叉树的叶子节点数为：\n%d \n",yz ); printf( "\n" ); break;
printf( "该二叉树的左右结点已交换成功，其中序遍历序列
是:\n" );
Inorder(bt);
printf( "\n" );
break;
}// switch
}// while
}
六、运行结果截图
11
参考文献：
[1]严蔚敏,吴伟民.数据结构(C 语言版).北京:清华大学出版社,2010
[2]严蔚敏,吴伟民等.数据结构题集(C 语言版).北京:清华大学出版社,2010
[3]苏仕华等.数据结构 程设计.北京:机械工业出版社,2008
12