树和二叉树sz.doc

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

1、实验三 树和二叉树一、 实验目的1、 掌握二叉树的结构特征，以及各种存储结构的特点和适用范围2、 掌握用指针类型描述、访问和处理二叉树的运算二、 实验要求1、 认真阅读和掌握本实验的程序2、 上机运行本程序3、 保存和打印出程序的运行结构，并结合程序进行分析4、 按照二叉树的操作需要，重新改写主程序并运行，打印出文件清单和运行结果。三、 实验内容1、 输入二叉树的先序序列字符，建立二叉链表。注意：输入时，必须加入虚结点以示空指针的位置；假设虚结点输入时用空格字符表示。2、 按先序、中序和后序遍历二叉树3、 求二叉树结点总数，观察输出结果。4、 求二叉树叶子数，观察输出结果。5、 求二叉树的深度

2、（或称高度），观察输出结果。6、 交换二叉树的左右子树7、 在主函数中设计一个简单的菜单，分别调试上述算法。8、 （）二叉树采用链接存储结构，其根结点指针为T，设计一个算法对这棵二叉树的每个结点赋值：（注意要修改DataType类型）a) 叶结点的值为3b) 只有左孩子或右孩子的结点则其值分别等于左孩子或右孩子的值c) 左、右孩子均有的结点，则其值等于左、右孩子结点的值之和【参考程序清单】#include #include #include Datahead.h/*二叉树的链式存储表示*/typedef char TElemType; /*由用户定义的实际数据类型*/typedef struc

3、t BiTNode TElemType data; struct BiTNode *lchild, *rchild; /*左右孩子指针*/ BiTNode, *BiTree; /*结点类型*/int a;void main() void CreateBiTree(BiTree *T); /*构造二叉链表*/ Status PrintChar(TElemType e); /*Visit 函数*/ Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e); /*前序遍历二叉树*/ Status InOrderTraverse(BiTr

4、ee T,Status(*Visit)(TElemType e); /*中序遍历二叉树*/ void Postorder(BiTree T); /*后序遍历二叉树*/ int nodes(BiTree T); /*计算总结点数*/ int leafs(BiTree T); /*计算总叶子数*/ void swap(BiTree T); /*交换左右子树*/ BiTree T; printf(input preorder nodes:(xu jie dian yong kong ge biao shi :n); CreateBiTree(&T); if (PreOrderTraverse(T,P

5、rintChar) printf(:PreOrderTraverse OK n); printf(zong de jie dian shu :%dn,nodes(T); printf(ye zi jie dian shu :%dn,leafs(T); swap(T); printf(jiao huan zuo you zi shu yi hou :n); if (PreOrderTraverse(T,PrintChar) printf(:PreOrderTraverse OK againn); getch();/*构造二叉链表*/void CreateBiTree(BiTree *T) /*

6、P131 算法6.4*/ char ch; scanf(%c,&ch); if(ch= ) *T=NULL; else if(!(*T=(BiTNode*)malloc(sizeof(BiTNode)exit(0); (*T)-data=ch; CreateBiTree(&(*T)-lchild); CreateBiTree(&(*T)-rchild); Status PrintChar(TElemType e) /*Visit 函数*/ printf(%c,e); return OK;/*前序遍历二叉树*/Status PreOrderTraverse(BiTree T,Status (*V

7、isit)(TElemType e) /* P129 算法6.1*/ if(T) if(Visit(T-data) if(PreOrderTraverse(T-lchild,Visit) if(PreOrderTraverse(T-rchild,Visit) return OK; return ERROR; else return OK;/*中序遍历二叉树的简单写法 */void Inorder(BiTree T) if(T) Inorder(T-lchild); printf(%c,T-data); Inorder(T-rchild); /*后序遍历二叉树*/void Postorder(B

8、iTree T) if(T)/*请补充代码*/ /*计算总结点数*/int nodes(BiTree T) if(T) return(nodes(T-lchild)+nodes(T-rchild)+1); else return(0);/*计算总叶子数*/int leafs(BiTree T) if(T=NULL)return(0); else if(T-lchild=NULL&T-rchild=NULL)return(1); else return(leafs(T-lchild)+leafs(T-rchild); /*交换左右子树*/void swap(BiTree T) BiTree p;

9、 if(T) p=T-lchild; T-lchild=T-rchild; T-rchild=p; swap(T-lchild); swap(T-rchild); /*计算二叉树的深度或者称为高度*/int depth(BiTree T) int hl,hr,max; if(T) if (T-lchild=NULL & T-rchild=NULL) return 1; else hl=depth(T-lchild); hr=depth(T-rchild); max=(hlhr)?hl:hr; return max+1; else return 0;/*结点赋值 叶结点的值为3 只有左孩子或右孩子的结点则其值分别等于左孩子或右孩子的值 左、右孩子均有的结点，则其值等于左、右孩子结点的值之和*/int ChangeValue(BiTree T) if(T) if (T-lchild=NULL & T-rchild=NULL) T-data=3;/*请补充代码*/ return T-data; 四、 程序调试和结果输出五、 实验小结