数据结构实验---二叉树.docx

计算机科学与技术学院实验目的及要求1实验目的：掌握树和二叉树的概念、二叉树的链式存储结构及常用算法；2实验内容及要求：设字符型二叉树采用二叉链表作存储结构，编程实现二叉树的如下基本操作：?二叉树的初始化（构造空树）；以先序序列形式如A(B(C,D),E(F(G,H(,I),)构造该二叉树；以先序和中序序列如ABCDEFGHI与CBDAGFHIE构造该二叉树；求二叉树的高度、结点总数、叶结点数目；交换二叉树各个结点的左右子树。判断该树是否完全二叉树；以层序方式遍历该二叉树进行遍历；编写主函数测试以上各个操作；算法基本思想：程序代码：#include stdio.h#include stdlib.h#include string.h#define Max 100typedef char elemType;typedef struct BTreeNode{ char data; struct BTreeNode *lchild,*rchild;}BTreeNode,*tree;void initBTree(tree *t){//初始化二叉树*t = NULL;return;}tree creatBTree0(tree t){//先序建立树（递归char ch;scanf(%c,ch);initBTree(t);if (ch!= #){if (!(t=(BTreeNode *) malloc(sizeof(BTreeNode)))) exit(1);t-data=ch;//从根节点开始creatBTree0(t-lchild);creatBTree0(t-rchild);}elset=NULL;return t;}void createBTree(tree *t, char *a){//建立二叉树(根据a所指向的二叉树字符串建立)tree p;tree s[Max];//定义s数组为存储根结点指针的栈使用int top = -1; //定义top作为栈的栈顶指针，初值为-1,为空栈int k; //用k作为标记结点的左子树和右子树，k = 1表示左子树，k = 2表示右子树int i = 0; // 用i扫描数组a中存储的二叉树字符串，初值为0*t = NULL; //把树根指针置为空while(a[i] != \0){ // 每循环一次处理一个字符，直到扫描到字符串结束符‘\0’为止switch(a[i]){case :break; //对空格不作处理case (://左括号后边的数据存入栈if(top == Max- 1){printf(空间小！\n);exit(1);}top++;s[top] = p;k = 1;break;case )://扫描到右括号时，栈顶指针减一if(top == -1){printf(二叉树广义表字符串错误!\n);exit(1);}top--;break;case ,://扫描到,，表示要放入到右子树中，即k赋值为2k = 2;break;default:p = malloc(sizeof(struct BTreeNode));//结点分配空间p-data = a[i];p-lchild = p-rchild= NULL;//左右节点赋空if(*t == NULL){*t = p;}else{if( k == 1){//“（”右边的元素置入左子树s[top]-lchild = p;}else{//其他情况下元素置入右子树s[top]-rchild = p;}}}i++; //为扫描下一个字符修改i值}return;}int emptyBTree(tree t){//检查二叉树是否为空，为空则返回1,否则返回0if(t == NULL){return 1;}else{return 0;}}int fullBiTree(tree t){//是否为满二叉树return count_nodenum(t) == ((1 BTreeDepth(t)) - 1);}int completeBTree(tree t){//判断完全二叉树,其左右子树均为完全二叉树// 空树是完全二叉树int hl = 0;int hr = 0;if (t == NULL){//空树为完全二叉树return 1;}hl = BTreeDepth(t-lchild);//左子树深度hr =BTreeDepth(t-rchild);//右子树深度if ((hl ==hr fullBiTree(t-lchild))|| (hl - hr == 1 fullBiTree(t-rchild))){//若左子树深度与右子树深度相同，且左子树为满二叉树；或者，若左子树深度减右子树深度等于1，且右子树为满二叉树return