实验四二叉树的基本操作(7页).doc

《实验四二叉树的基本操作(7页).doc》由会员分享，可在线阅读，更多相关《实验四二叉树的基本操作(7页).doc（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-实验四 二叉树的基本操作一、 实验目的1 进一步掌握指针变量的含义。2 掌握二叉树的结构特征，以及各种存储结构的特点及使用范围。3 掌握用指针类型描述、访问和处理二叉树的运算。二、 实验要求1、 设计二叉树的基本操作；2、 写出相应程序；3、 保存和打印出程序的运行结果，并结合程序进行分析。三、实验内容给出一个可进行二叉树基本操作的完整程序，具有以下功能：（1）根据输入字符序列，建立二叉树；（2）用递归算法实现输出二叉树的前序、中序、后序遍历序列；（3）求二叉树的高度。附加题: （有时间可继续完成下面内容）(4)用非递归算法实现输出二叉树的前序、中序遍历序列；（5）求二叉树的叶子个数；（6）

2、求度为1的结点的个数；算法：四、程序代码建树，遍历，求树高#include#include#includetypedef struct Nodechar data;struct Node * lchild;struct Node * rchild;Node,*Tree;void a(Tree & t)/构造二叉树 char ch;scanf(%c,&ch);if(ch=.)t=NULL;elset=(Tree)malloc(sizeof(Node);t-data=ch;a(t-lchild);a(t-rchild);return;void b(Tree & t)/先序遍历 if(t)print

3、f(%c,t-data);b(t-lchild);b(t-rchild);void c(Tree & t)/中序遍历 if(t)c(t-lchild);printf(%c,t-data);c(t-rchild);void d(Tree & t)/后序遍历 if(t)d(t-lchild);d(t-rchild);printf(%c,t-data);int max(int x,int y) return xy?x:y; int high(Tree & t) if(t=NULL) return 0; else return max(high(t-lchild),high(t-rchild)+1;

4、int main()Tree t;printf(请输入二叉树：n);a(t);printf(n先序遍历 nn);b(t);printf(nn中序遍历 nn);c(t);printf(nn后序遍历 nn);d(t);printf(nn树高为：%d,high(t);非递归先序，中序遍历，求叶子节点的个数，求度为1的节点的个数#include#include#includetypedef struct Nodechar data;struct Node * lchild;struct Node * rchild;Node,*Tree;void a(Tree & t)/构造二叉树 char ch;sc

5、anf(%c,&ch);if(ch=.)t=NULL;elset=(Tree)malloc(sizeof(Node);t-data=ch;a(t-lchild);a(t-rchild);return;void b(Tree t) Tree stack20, p; int top = -1; if (t != NULL) top+; stacktop = t; while (top -1) p = stacktop; top-; printf(%c , p-data); if (p-rchild != NULL) top+; stacktop = p-rchild; if (p-lchild !

6、= NULL) top+; stacktop = p-lchild; printf(n); void c(Tree t) Tree stack20, p; int top = -1; if (t != NULL) p = t; while (top -1 | p != NULL) while (p != NULL) top+; stacktop = p; p = p-lchild; if (top -1) p = stacktop; top-; printf(%c , p-data); p = p-rchild; printf(n); void d(Tree & t,int & n)if(t)

7、if(!t-lchild&!t-rchild)n+;d(t-lchild,n);d(t-rchild,n);void e(Tree & t,int & n)if(t)if(!t-lchild&t-rchild)|(t-lchild&!t-rchild)n+;e(t-lchild,n);e(t-rchild,n);int main()Tree t;int n1=0,n2=0;printf(请输入二叉树：n);a(t);printf(先序非递归遍历：n);b(t); printf(中序非递归遍历：n);c(t);d(t,n1);printf(叶子节点的个数：%dn,n1);e(t,n2);printf(度为1的点的个数：%dn,n2);五、结果及分析递归遍历，树高非递归遍历，叶子节点个数，度为1的节点个数-第 7 页-