实验四 二叉树的建立与遍历
- 格式：docx
- 大小：105.09 KB
- 文档页数：7
实验四 二叉树的建立与遍历
【实验目的】
掌握二叉树的定义、性质及存储方式，各种遍历算法。
【实验内容】
１．采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序遍历
的递归操作。
２．分别求所有叶子结点及结点总数的操作。
提示：设计一颗二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针），
如ABD###CE##F##，建立二叉树，求出先序、中序和后序遍历序列，求所有叶
子及结点总数。
【程序源代码】
#include
#include
typedef char TElemType;
typedef int Status;
#define OK 1
#define ERROR 0
#define OVERFLOW 0
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode , *BiTree;
Status CreateBiTree(BiTree &BT);
void CountLeaves(BiTree BT, int &count);
int NodeCount(BiTree BT);
void PreOrder(BiTree BT);
void InOrder(BiTree BT);
void PostOrder(BiTree BT);
int main()
{
BiTree BT;
int choice,cho;
int logo = 1;
printf("输入二叉树结点，以'#'为空指针\n");
CreateBiTree(BT);
do{
printf("\t 1:遍历二叉树\n");
printf("\t 2：二叉树总结点数及叶子节点数\n");
printf("\t 3：退出程序\n ");
printf("\t 输入选项: ");
scanf("%2d",&choice);
switch(choice)
{
case 1:
printf("1:先序遍历\n");
printf("2:中序遍历\n");
printf("3:后序遍历\n");
scanf("%2d",&cho);
switch(cho)
{
case 1:
PreOrder(BT);
printf("\n");
break;
case 2:
InOrder(BT);
printf("\n");
break;
case 3:
PostOrder( BT);
printf("\n");
break;
default:
printf("输入错误!\n");
}
break;
case 2:
int count;
printf("总结点数为:%2d\n", NodeCount(BT));
CountLeaves(BT, count);
printf("叶子结点数为:%2d\n", count);
break;
case 3 :
exit(0);
break;
default:
printf("输入错误!\n");
}
} while(logo==1);
return 0;
}
Status CreateBiTree(BiTree &BT)
{
char ch;
scanf("%c", &ch);
if (ch == '#')
BT = NULL;
else
{
if (!(BT = (BiTree)malloc(sizeof(BiTNode))))exit(OVERFLOW);
BT->data = ch;
CreateBiTree(BT->lchild);
CreateBiTree(BT->rchild);
}
return OK;
}
void PreOrder(BiTree BT)
{
if (BT != NULL)
{
printf("%c ", BT->data);
PreOrder(BT->lchild);
PreOrder(BT->rchild);
}
}
void InOrder(BiTree BT)
{
if (BT != NULL)
{
PreOrder(BT->lchild);
printf("%c ", BT->data);
PreOrder(BT->rchild);
}
}
void PostOrder(BiTree BT)
{
if (BT != NULL)
{
PreOrder(BT->lchild);
PreOrder(BT->rchild);
printf("%c ", BT->data);
}
}
void CountLeaves(BiTree BT,int &count)
{
if (BT)
{
if (!BT->lchild && !BT->rchild)
count++;
CountLeaves(BT->lchild, count);
CountLeaves(BT->rchild, count);
}
}
int NodeCount(BiTree BT)//统计总结点数
{
if (BT == NULL)
return 0;
else
return (NodeCount(BT->lchild) + NodeCount(BT->rchild) + 1);
}
【运行结果分析】
【实验收获与心得】
在本次实验中，我对递归这个概念有了较为深刻的认识，对二叉树的建立、
遍历也掌握得较为透彻，通过对书本上知识的运用，我对本章的部分知识的掌握
程度得到了提高，通过将各个算法运用到编程中，也使我对原本不是太懂的算法
的理解有了质的提高。
