《二叉树的性质与链式存储结构》由会员分享，可在线阅读，更多相关《二叉树的性质与链式存储结构（8页珍藏版）》请在金锄头文库上搜索。
1、实验八叉树的性质与链式存储结构指导老师：朱芳 学号：13011432 班级：13083414姓名：张杭俊【实验目的】 了解树结点和结点间关系的基本概念 了解树的结点访问的方法 掌握二叉树的链式存储结构 掌握二叉树结点的递归访问方法 掌握二叉树的遍历【实验内容】1.观察如图所示的二叉树并回答问题1）写出前序、中序和后序的遍历序列前序：ABDECFG中序：DBEAFGC后序：DEBGFCA2）分别写出单支结点和叶子结点单支结点：C、F叶子结点：D、E、G3）以“#”补充所有结点的空分支4）写出补充空分支后二叉树的前序遍历序列前序：ABD#E#CF#G#5）在工程BiTree中添加二叉树的中序或后序
2、遍历接口，并在主函数中将第（4）小题的遍历序列写入main函数的数组A中进行验证结果如下：2. 验证题函数调用和返回动作发生的顺序“E:学习曲据结西试好,实勘认FWIDIGUfbiD命ugbi,ex前中后探SSe r pJP5data 168 D3. 计算题仿照第题，在main函数中，定义数组A= “ABD#E#C#F#” ；调用函数CreateBTree_Pre(root,A)；根据A中的数据建立如图二叉树，调用并验证递 归函数int BTreeDepth(BTNode *root)计算该二叉树深度过程函数调用和返回动作发生的顺序调用顺序root结点返回顺序返回值1A1332B723D314
3、NULL105NULL206E617NULL408NULL509C12210NULL8011F11112NULL9013NULL100调试过程:4. 二叉树的非递归遍历#头文件#includeusing namespace std ;typedef char DataType;typedef struct NodeDataType data ;struct Node *left , *right ;BTNode ;void Treelnit(BTNode *&root);void CreateBTree_Pre (BT Node *&root , DataType Array);void Pr
4、eOrder(BTNode *root);void InOrder(BTNode *root);void PostOrder (BT Node *root);int BTreeDepth(BTNode *root);void Clear BTree(BTNode *&root);#函数#includeBiTree.hvoid TreeInit(BTNode *&root)root = NULL ;void CreateBTree_Pre( BTNode *&root , DataType Array)static int count = 0 ;char item = Arraycount;co
5、unt+;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 data ; PreOrder(root-left);PreOrder(root-right);void lnOrder(BTNode *root)if(root != NULL)InOrder(
6、root-left); cout data ;InOrder(root-right);void PostOrder (BT Node *root)if(root != NULL)PostOrder(root-left); PostOrder(root-right);cout data ;int BTreeDepth(BTNode *root)if(root = NULL)return 0;elseint depl = BTreeDepth(root-left); int depr = BTreeDepth(root-right); if(depl depr)return depl + 1 ;e
7、lsereturn depr + 1 ;void Clear BTree(BTNode *&root)if(root != NULL)ClearBTree(root-left); ClearBTree(root-right); delete root ;root = NULL ;#主函数#includeBiTree.hint main()BTNode *root ;DataType A = ABD#E#CF#G#;Treelnit(root);CreateBTree_Pre(root , A);cout 前序遍历序列:; PreOrder(root);cout endl ;cout 中序遍历序列:;InOrder(root);cout endl ;cout 后续遍历序列:;PostOrder(root);cout endl ;cout 深度 BTreeDepth(root) endl ;return 0;序遍历序列：ABDECFG 中库遍历库列:DBEAFGC 后续遍历序列:DEBGFCA 性度4.Press any key to continue
