#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define True 1
// 定义二叉树的节点类型
typedef
struct BiTNode{
char data;
struct BiTNode *lchild;
// 定义节点的左孩子指针，有孩子指针
struct BiTNode *
rchild;
}BiTNode,*
BiTree;
//先序遍历构造二叉链表表示对二叉树T
int CreateBiTree(BiTree &
T)
{
char ch;
scanf("%c",&
ch);
fflush(stdin); // 对键盘缓冲区的处理
if(ch==
'#'){
//如果输入#，创建空节点
T=
NULL;
}else{
if(!(T=(BiTNode*)
malloc(
sizeof(BiTNode)))){
//申请根节点的空间
printf(
"申请节点空间失败！！");
exit(OVERFLOW);
}else{
T->data=ch;
//生成根节点
CreateBiTree(T->lchild);
//构建左子树
CreateBiTree(T->rchild);
//构建右子树
}
return OK;
}
return ERROR;
}
//先序遍历二叉树
int DLR(BiTree T)
{
if(T!=NULL)
// 如果树不为空
{
printf("%c\n",T->
data);
DLR(T->lchild);
// 递归遍历
DLR(T->
rchild);
}else{
return ERROR;
//树为空
}
return OK;
// 遍历成功
}
//中序遍历二叉树
int LDR(BiTree T)
{
if(T!=
NULL)
{
LDR(T->lchild);
// 递归遍历
printf(
"%c\n",T->
data);
LDR(T->
rchild);
}else{
return ERROR;
//树为空
}
return OK;
// 遍历成功
}
//后序遍历二叉树
int LRD(BiTree T)
{
if(T!=
NULL)
{
LRD(T->lchild);
// 递归遍历
LRD(T->
rchild);
printf("%c\n",T->
data);
}else{
return ERROR;
//树为空
}
return OK;
// 遍历成功
}
// 树的叶子数
void yezi(BiTree T){
if(T!=
NULL){
if(!T->lchild&&!T->
rchild){
printf("%c\n",T->data);
// 打印叶子节点
}
yezi(T->
lchild);
yezi(T->
rchild);
}
}
// 树的深度
int shendu(BiTree T){
int h=
0,h1,h2;
if(T==
NULL)
return h;
else{
h1=shendu(T->
lchild);
h2=shendu(T->
rchild);
if(h1>=h2)
// 最后加的数为树的最深
h=h1+
1;
else
h=h2+
1;
}
return h;
}
void OperateMenu()
{
printf("\n--------------请选择元素处理方式---------\n\n");
printf("\n注：请输入数字\n");
printf("0>:退出操作\n");
printf("1>:先序遍历二叉树\n");
printf("2>:中序遍历二叉树\n");
printf("3>:后序遍历二叉树\n");
printf("4>:树的叶子节点\n");
printf("5>:树的深度\n");
printf("请选择对元素的处理：");
}
void zushi(){
printf("注：此过程为二叉树的建立及其对其的相关操作\n\t以下为树的大致模型\t\n");
printf(" 1 \n");
printf(" / \\ \n");
printf(" 2 3 \n");
printf(" / \\ / \\ \n");
printf(" # # # # \n");
printf("\n 注！！！楼上输入 # 表示无孩子为空\n故输入序列为12##3###\n");
printf("实际形成序列形成的树为为：\n");
printf(" 1 \n");
printf(" / \\ \n");
printf(" 2 3 \n");
}
int main(){
int w=
0,k,n,boo=
1;
BiTree T;
printf("请用户选择创建二叉树或退出程序：\n\n");
printf("创建二叉树请输入：'1'\n\n");
printf("退出请选择'0'或 其它！！\n\n");
printf("请选择：");
scanf("%d",&
w);
if(w==
1){
zushi();
printf("\n请输入树节点元素（请回车输入下一个数）：\n");
fflush(stdin);
boo=
CreateBiTree(T);
if(!
boo){
//printf("\n构建成功！！\n");
while(!
boo){
printf("\n构建树为空树，请重新构建：");
printf("\n请输入树节点元素（请回车输入下一个数）：\n");
boo=
CreateBiTree(T);
}
}else{
printf("\n构建成功！！\n");
}
OperateMenu();
scanf("%d",&
k);
while(k){
switch(k){
case 0:
break;
case 1:
printf("先序遍历结果为：\n");
boo=
DLR(T);
if(boo)
printf("\n先序遍历成功！！\n");
else
printf("\n先序遍历失败！！\n");
break;
case 2:
printf("中序遍历结果为：\n");
boo=
LDR(T);
if(boo)
printf("\n中序遍历成功！！\n");
else
printf("\n中序遍历失败！！\n");
break;
case 3:
printf("后序遍历结果为：\n");
boo=
LRD(T);
if(boo)
printf("\n后序遍历成功！！\n");
else
printf("\n后序遍历失败！！\n");
break;
case 4:
printf("其中是叶子节点的是：\n");
yezi(T);
break;
case 5:n=
shendu(T);
printf("树的深度为：%d",n);
break;
}
OperateMenu();
scanf("%d",&
k);
}
}
return OK;
}
转载于:https://www.cnblogs.com/Vera-y/p/11491635.html
相关资源：数据结构（C语言版）--二叉树的遍历
