《数据结构二叉树C语言实现》由会员分享，可在线阅读，更多相关《数据结构二叉树C语言实现（8页珍藏版）》请在金锄头文库上搜索。
1、数学与信息技术学院 20162017（下）学年计科专业 2015 级数据结构实验报告 5 学号：2015201018 姓名：汪继超实验名称 树的操作实现与应用 完成时间 2017.05.10一实验目的和要求：1掌握树特别是二叉树的基本概念、定义和性质。2掌握二叉树的基本结构、内部逻辑和三种遍历算法的基本思想，熟悉二叉树的存储结构和指针链接的变化。3通过对二叉树的建立和三种遍历算法的实现，学会编程的方法。二 .实验原理 树是一种应用极为广泛的数据结构，也是本门课程的重点，它的特点在于非线性。遍历操作是树众多操作的基础，所以本次实验主要强调突出二叉树的三种基本遍历操作的实现。三 .实验内容(1)
2、根据屏幕提示输入二叉树的各个结点，并建立该二叉树；(2)选择某种遍历方式输出该二叉树；(3)求该二叉树的叶子结点数；(4)求该二叉树的高度；(5)将该二叉树中所有结点的左、右子树相互换，并输出。实验过程：/*注：此程序为二叉树树的操作实现与应用 */#include#include#include#includetypedef int TElemType;typedef struct BiTNodeTElemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;BiTNode * CreatBiTree()BiTree T;int c
3、h;scanf(%d,if(ch=0) T=NULL;elseT=(BiTNode *)malloc(sizeof(BiTNode);if(!T) exit(0);T-data=ch;printf(请输入%d 的左结点：,ch);T-lchild=CreatBiTree();printf(请输入%d 的右结点：,ch);T-rchild=CreatBiTree();return T;void PreOrderTraverse(BiTNode *P)if(P!=NULL)printf(%-2d,P-data);PreOrderTraverse(P-lchild);PreOrderTraverse
4、(P-rchild);else printf();void InOrderTraverse(BiTNode *P)if(P!=NULL)InOrderTraverse(P-lchild);printf(%-2d,P-data);InOrderTraverse(P-rchild);else printf();void PostOrderTraverse(BiTNode *P)if(P!=NULL)PostOrderTraverse(P-lchild);PostOrderTraverse(P-rchild);printf(%-2d,P-data);else printf();void exchan
5、ge(BiTNode *P)BiTNode *q;if(P)q=P-lchild;P-lchild=P-rchild;P-rchild=q;exchange(P-lchild);exchange(P-rchild);int count_leaves(BiTNode *P)if(!P) return 0;else if(!P-lchildelse return count_leaves(P-lchild)+count_leaves(P-rchild);int TreeHigh(BiTNode *T)int lh=0,rh=0;if(!T) return 0;lh=TreeHigh(T-lchil
6、d);rh=TreeHigh(T-rchild);return lhrh?lh+1:rh+1;void Menu() printf( 欢迎使用树的操作实现与应用系统 nn);printf( *菜单*n); printf( * 1.创建树 2.先序遍历二叉树 *n);printf( * 3.中序遍历二叉树 4.后序遍历二叉树 *n);printf( * 5.左右子树交换 6.求叶子数 *n);printf( * 7.求树的深度 0.退出 *n);printf( *n); void main()int n,f,high,count1;char b;BiTNode *P=NULL;system(co
7、lor 0A);SetConsoleTitle(汪继超:2015201018);doMenu();printf(n 请选择您需要操作的步骤(0-7): );fflush(stdin); scanf(%d,if(n=0 elsef=0;system(cls);printf(您输入有误，请重新选择!n);while(f=0);while(f=1)switch(n)case 1:printf(n 请输入根节点：);P=CreatBiTree();break;case 2:printf(n 先序遍历：);PreOrderTraverse(P);break;case 3:printf(n 中序遍历：);
8、InOrderTraverse(P);break;case 4:printf(n 后序遍历：);PostOrderTraverse(P);break;case 5:exchange(P);printf(n 交换左右孩子后先序遍历：);PreOrderTraverse(P);break;case 6:count1=count_leaves(P);printf(n 二叉树的叶子结点数为：%d,count1);break;case 7:printf(n 树的深度为:);high=TreeHigh(P);printf(%d,high);break;case 0:printf(n 谢谢使用，欢迎下次光临
9、！n);exit(0);default:printf(n 输入错误！);system(pause);break;printf(nn 是否继续进行(y or n): );fflush(stdin);scanf(%c,if(b=y|b=Y)f=1;system(cls);Menu();printf(请再次选择你需要操作的步骤(0-6): );scanf(%d,elseexit(0);实验结果：主菜单：1.创建树：2-1.先序遍历二叉树：2-2.中序遍历二叉树：2-3.后序遍历二叉树：注：“”表示树结点为空。3.左右孩子交换后先序遍历检验：4.求树的叶子数：5.求树的深度：问题讨论：1. 二叉树遍历是其所有操作的基础，遍历操作中复杂的递归问题，可以通过 0-5 个结点的二叉树基本模型进行深度分析，总结扩展 n 个结点。注：文件名为：学号+（次数）
