二叉树的性质与链式存储结构-实验8报告讲解

实验八二叉树的性质与链式存储结构指导老师：朱芳学号：13011432班级：13083414姓名：张杭俊【实验目的】了解树结点和结点间关系的基本概念了解树的结点访问的方法掌握二叉树的链式存储结构掌握二叉树结点的递归访问方法掌握二叉树的遍历【实验内容】1.观察如图所示的二叉树并回答问题1)写出前序、中序和后序的遍历序列前序：ABDECFG中序：DBEAFGC后序：DEBGFCA2)分别写出单支结点和叶子结点单支结点：C、F叶子结点：D、E、G3)以“#”补充所有结点的空分支4)写出补充空分支后二叉树的前序遍历序列前序：ABD##E##CF#G###5)在工程BiTree中添加二叉树的中序或后序遍历接口，并在主函数中将第（4）小题的遍历序列写入main函数的数组A[]中进行验证结果如下：2.验证题函数调用和返回动作发生的顺序调用顺序root结点返回顺序返回值1A932B523D314NULL105NULL206NULL407C818NULL609NULL70调试过程：3.计算题仿照第(2)题，在main函数中，定义数组A[]=“ABD##E##C#F##”;调用函数CreateBTree_Pre(root,A)；根据A[]中的数据建立如图二叉树，调用并验证递归函数intBTreeDepth(BTNode*root)计算该二叉树深度过程函数调用和返回动作发生的顺序调用顺序root结点返回顺序返回值1A1332B723D314NULL105NULL206E617NULL408NULL509C12210NULL8011F11112NULL9013NULL100调试过程：4.二叉树的非递归遍历#头文件#includeiostreamusingnamespacestd;typedefcharDataType;typedefstructNode{DataTypedata;structNode*left,*right;}BTNode;voidTreeInit(BTNode*&root);voidCreateBTree_Pre(BTNode*&root,DataTypeArray[]);voidPreOrder(BTNode*root);voidInOrder(BTNode*root);voidPostOrder(BTNode*root);intBTreeDepth(BTNode*root);voidClearBTree(BTNode*&root);#函数#includeBiTree.hvoidTreeInit(BTNode*&root){root=NULL;}voidCreateBTree_Pre(BTNode*&root,DataTypeArray[]){staticintcount=0;charitem=Array[count];count++;if(item=='#'){root=NULL;return;}else{root=newBTNode;root-data=item;CreateBTree_Pre(root-left,Array);CreateBTree_Pre(root-right,Array);}}voidPreOrder(BTNode*root){if(root!=NULL){coutroot-data;PreOrder(root-left);PreOrder(root-right);}}voidInOrder(BTNode*root){if(root!=NULL){InOrder(root-left);coutroot-data;InOrder(root-right);}}voidPostOrder(BTNode*root){if(root!=NULL){PostOrder(root-left);PostOrder(root-right);coutroot-data;}}intBTreeDepth(BTNode*root){if(root==NULL){return0;}else{intdepl=BTreeDepth(root-left);intdepr=BTreeDepth(root-right);if(depldepr){returndepl+1;}else{returndepr+1;}}}voidClearBTree(BTNode*&root){if(root!=NULL){ClearBTree(root-left);ClearBTree(root-right);deleteroot;root=NULL;}}#主函数#includeBiTree.hintmain(){BTNode*root;DataTypeA[]=ABD##E##CF#G###;TreeInit(root);CreateBTree_Pre(root,A);cout前序遍历序列:;PreOrder(root);coutendl;cout中序遍历序列:;InOrder(root);coutendl;cout后续遍历序列:;PostOrder(root);coutendl;cout深度BTreeDepth(root)endl;return0;}