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

实验八 二 叉 树 的 性 质 与 链 式 存 储 结 构 指导老师：朱芳 学号班级姓名：张杭俊 【实验目的】 了解树结点和结点间关系的基本概念 了解树的结点访问的方法 掌握二叉树的链式存储结构 掌握二叉树结点的递归访问方法 掌握二叉树的遍历 【实验内容】 观察如图所示的二叉树并回答问题 写出前序、中序和后序的遍历序列 前序：ABDECFG 中序：DBEAFGC 后序：DEBGFCA 分别写出单支结点和叶子结点 单支结点：C、F 叶子结点：D、E、G 以“#”补充所有结点的空分支 写出补充空分支后二叉树的前序遍历序列 前序：ABD##E##CF#G### 在工程BiTree中添加二叉树的中序或后序遍历接口，并在主函数中将第（4）小题的遍历序列写入main函数的数组A[]中进行验证 结果如下： 验证题 函数调用和返回动作发生的顺序 调用顺序 root结点 返回顺序 返回值 1 A 9 3 2 B 5 2 3 D 3 1 4 NULL 1 0 5 NULL 2 0 6 NULL 4 0 7 C 8 1 8 NULL 6 0 9 NULL 7 0 调试过程： 计算题 仿照第(2)题，在main函数中，定义数组A[]=“ABD##E##C#F##”;调用函数CreateBTree_Pre(root,A)；根据A[]中的数据建立如图二叉树，调用并验证递归函数int BTreeDepth(BTNode *root)计算该二叉树深度过程 函数调用和返回动作发生的顺序 调用顺序 root结点 返回顺序 返回值 1 A 13 3 2 B 7 2 3 D 3 1 4 NULL 1 0 5 NULL 2 0 6 E 6 1 7 NULL 4 0 8 NULL 5 0 9 C 12 2 10 NULL 8 0 11 F 11 1 12 NULL 9 0 13 NULL 10 0 调试过程： 二叉树的非递归遍历 #头文件 #includeiostream using namespace std ; typedef char DataType ; typedef struct Node { DataType data ; struct Node *left , *right ; }BTNode ; void TreeInit(BTNode *root) ; void CreateBTree_Pre(BTNode *root , DataType Array[]) ; void PreOrder(BTNode *root) ; void InOrder(BTNode *root) ; void PostOrder(BTNode *root) ; int BTreeDepth(BTNode *root) ; void ClearBTree(BTNode *root) ; #函数 #includeBiTree.h void TreeInit(BTNode *root) { root = NULL ; } void CreateBTree_Pre(BTNode *root , DataType Array[]) { static int count = 0 ; char item = Array[count] ; count++ ; if(item == #) { root = NULL ; return ; } else { root = new BTNode ; root-data = item ; CreateBTree_Pre(root-left , Array) ; CreateBTree_Pre(root-right , Array) ; } } void PreOrder(BTNode *root) { if(root != NULL) { cout root-data ; PreOrder(root-left) ; PreOrder(root-right) ; } } void InOrder(BTNode *root) { if(root != NULL) { InOrder(root-left) ; cout root-data ; InOrder(root-right) ; } } void PostOrder(BTNode *root) { if(root != NULL) { PostOrder(