数据结构实验2报告总结.docx

一 实验目的和要求 理解二叉树的基本概念，熟练使用多种表示法构造二叉树，掌握采用二叉链表存储结构实现二叉树的构造、遍历、插入、删除等操作算法；理解线索二叉树的作用，掌握获得线索二叉树节点在指定遍历次序下的前驱或后继结点的方法；理解哈弗曼编码和哈弗曼树的作用，掌握由指定文本求得哈弗曼编码的方法。 理解树的基本概念，熟悉树的多种存储结构，掌握采用孩子兄弟链表存储结构实现树的遍历、插入、删除等操作算法。 通过研究树和二叉树，深刻理解链式存储结构用于表达非线性结构的作用，掌握采用递归算法实现递归数据结构基本操作的设计方法。二 题目及题意分析 题目：插入x元素作为p结点的第i个孩子 分析：以中国城市作为元素,以插入孩子结点的方式构造一棵树，找到结点p，p不为空时，若p的孩子结点为空，则直接插入x元素作为p的孩子;若p的孩子结点不为空，插入的x元素的位置n小于等于1时，将x元素直接插在最前面;若n大于1时，查找插入的位置执行插入。三 设计方案和功能说明 源程序如下：TreeNode.htemplateclass TreeNode /数的孩子兄弟链表结点类public: /数据域，保存元素T data;TreeNode* child,*sibling; /指针域，分别指向孩子兄弟结点TreeNode(T data,TreeNode*child=NULL,TreeNode*sibling=NULL) this-data=data;this-child=child;this-sibling=sibling;Tree.h#include#includeTreeNode.h /树的孩子兄弟链表节点类templateclass Tree /树类public:TreeNode*root; /指向根结点 Tree(); /构造空树 bool isEmpty();/判断是否空树 TreeNode* insertChild(TreeNode*p,T value); / 插入value作为结点p的孩子TreeNode* insertChild(TreeNode*p,T x,int i);/ 插入x元素作为p结点的第i个孩子friend ostream&operator(ostream&out,Tree&tree);/先根次序遍历树并以树的横向凹入表示法输出树 void preOrder(TreeNode *p,int i); ;templateTree:Tree() /构造空树root=NULL;templatebool Tree:isEmpty()/判断是否空树return root=NULL;templateTreeNode* Tree:insertChild(TreeNode*p,T value) /插入value作为结点p的孩子TreeNode*q=NULL;if(p!=NULL)q=new TreeNode (value);if(p-child=NULL)p-child=q;elsep=p-child;while(p-sibling!=NULL)p=p-sibling;p-sibling=q; return q;templateTreeNode*Tree:insertChild(TreeNode* p,T x,int i)/ 插入x元素作为p结点的第i个孩子 TreeNode*q=NULL; if(p!=NULL) q=new TreeNode(x); if(p-child=NULL) p-child=q; else if(ichild=new TreeNode(x,NULL,p-child); return p-child; p=p-child; for(int j=1;p-sibling!=NULL&jsibling; if( p-sibling=NULL) p-sibling=q; else p-sibling=new TreeNode(x,NULL,p-sibling); return q;templatevoid Tree:preOrder(TreeNode *p,int i) if(p!=NULL) for(int j=0;ji;j+)coutt;coutdatachild,i+1); preOrder(p-sibling,i); templateostream&operator(ostream&out,Tree &tree)/先根次序遍历树并以树的横向凹入表示法输出树 tree.preOrder(tree.root,0);return out;Main.cpp#include Tree.h TreeNode*aa; void make(Tree&tree) tree.root=new TreeNode(中国); tree.insertChild(tree.root,北京); tree.insertChild(tree.root,上海); TreeNode*js=tree.insertChild(tree.root,江苏省); tree.insertChild(js,南京市); tree.insertChild(js,苏州市); TreeNode *zj=tree.insertChild(tree.root,浙江省); tree.insertChild(zj,杭州市); tree.insertChild(zj,宁波市); TreeNode *sx=tree.insertChild(tree.root,山西省); tree.insertChild(sx,太原市); tree.insertChild(sx,大同市); aa=zj; int main() Treetree; make(tree); couttree; tree.insertChild(aa,无锡市,2); co