本文主要是给c语言初学者或数据结构初学者展示二叉树的构造与遍历，可以作为简单的参考。除了代码外，本文有部分博主自己对代码的简单分析，可以通过下面的链接免费下载。
#include "stdafx.h"
// 各种引用
#include#include#include#include#define NULL 0
int m_nNumOfLeaf=0; // 叶子结点数量
typedef char ElemType; //定义二叉树结点中保存的数据的数据类型
typedef struct BinaryNode //定义二叉树结点的数据类型
{ElemType data; //存放二叉树结点数据
struct BinaryNode *lchild, *rchild; //存放二叉树结点左右子树的指针（指向的数据类型是本身）
} BTNode;
BTNode * m_root= NULL; // 二叉树指针（指向二叉树的根结点）
BTNode * CreatebBinaryTree()
{BTNode *T;
ElemType x;
scanf("%c",&x); // 获取结点数据
if(x=='#') // 空结点
T=NULL;
else // 非空结点
{T=(BTNode*)malloc(sizeof(BTNode)); // 申请空间存储结点
T->data=x; // 存储数据
T->lchild=CreatebBinaryTree(); // 建立以本结点为根的左子树
T->rchild=CreatebBinaryTree(); // 建立以本结点为根的右子树
}
return(T); // 返回根结点
}
void PreOrderPrint(BTNode *t)
{if(t!=NULL) // 根结点不为空
{printf("%c\t",t->data); // 输出根结点
PreOrderPrint(t->lchild); // 前序遍历以本结点为根的左子树
PreOrderPrint(t->rchild); // 前序遍历以本结点为根的右子树
}
}
void InOrderPrint(BTNode *t)
{if(t!=NULL) // 根结点不为空
{InOrderPrint(t->lchild); // 中序遍历以本结点为根的左子树
printf("%c\t",t->data); // 输出根结点
InOrderPrint(t->rchild); // 中序遍历以本结点为根的右子树
}
}
void PostOrderPrint(BTNode *t)
{if(t!=NULL) // 根结点不为空
{
PostOrderPrint(t->lchild); // 后序遍历以本结点为根的左子树
PostOrderPrint(t->rchild); // 后序遍历以本结点为根的右子树
printf("%c\t",t->data); // 输出根结点
}
}
void CalNumOfLeaf(BTNode *t)
{if(t!=NULL) // 根结点不为空
{if((t->lchild!=NULL)||(t->rchild!=NULL)) // 判断该结点是否有左右子树
{ CalNumOfLeaf(t->lchild); // 计算该结点左子树的叶子结点数
CalNumOfLeaf(t->rchild); // 计算该结点右子树的叶子结点数
}
else m_nNumOfLeaf++; // 是叶子结点,则叶子结点数加1
}
}
int main(int argc, char* argv[]) // 主函数
{printf(" ***************************************\n");
printf(" 二叉树操作\n");
printf(" ***************************************\n");
int flag = 1;
while(flag)
{printf("\n\n\t\t 1--建立\n");
printf("\t\t 2--前序遍历\n");
printf("\t\t 3--中序遍历\n");
printf("\t\t 4--后序遍历\n");
printf("\t\t 5--叶子的数量\n");
printf("\t\t 0--退出程序\n");
printf("\t\t 程序编写人<姓名:%s ; 学号:%s>\n","张三","123456789"); // 显示 姓名和学号
scanf("%d",&flag);
switch(flag)
{ case 1: // 建立二叉树
{ getchar(); // 获取输入的回车
printf("请输入二叉树各结点(前序顺序,#代表空结点),形式如(AB###,ABC#####)：\n"); // 输出字符串
m_root = CreatebBinaryTree(); // 构建二叉树(前序)
printf("建立二叉树完毕：\n"); // 输出字符串
}
break;
case 2: // 前序遍历
{ if(m_root == NULL) // 出错判断
{printf("\n还没有建立二叉树,无法进行此操作!\n"); // 输出字符串
}
else
{printf("\n二叉树前序遍历的顺序为：\n"); // 输出字符串
PreOrderPrint(m_root); // 前序遍历输出
printf("\n二叉树前序遍历结束：\n"); // 输出字符串
}
}
break;
case 3: // 中序遍历
{
if(m_root == NULL) // 出错判断
{printf("\n还没有建立二叉树,无法进行此操作!\n"); // 输出字符串
}
else
{printf("\n二叉树中序遍历的顺序为：\n"); // 输出字符串
InOrderPrint(m_root); // 中序遍历输出
printf("\n二叉树中序遍历结束：\n"); // 输出字符串
}
}
break;
case 4: // 后序遍历
{
if(m_root == NULL) // 出错判断
{printf("\n还没有建立二叉树,无法进行此操作!\n"); // 输出字符串
}
else
{printf("\n二叉树后序遍历的顺序为：\n"); // 输出字符串
PostOrderPrint(m_root); // 后序遍历输出
printf("\n二叉树后序遍历结束：\n"); // 输出字符串
}
}
break;
case 5: // 计算叶子结点的数目
{ if(m_root == NULL) // 出错判断
{printf("\n还没有建立二叉树,无法进行此操作!\n"); // 输出字符串
}
else
{m_nNumOfLeaf=0; // 叶子结点数量初始化
CalNumOfLeaf(m_root); // 计算叶子结点数量
printf("\n当前二叉树中叶子数量为:%d\n",m_nNumOfLeaf); // 输出字符串
}
}
break;
case 0: // 退出程序
break;
default: // 输入错误
printf("请输入正确的数字!!!\n");
break;
}
}
return 0;
}
下载
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
