数据结构实验2报告总结

理解二叉树的基本概念，熟练使用多种表示法构造二叉树，掌握采用二叉链表存储结构实现二叉树的构造、遍历、插入、删除等操作算法；理解线索二叉树的作用，掌握获得线索二叉树节点在指定遍历次序下的前驱或后继结点的方法；理解哈弗曼编码和哈弗曼树的作用，掌握由指定文本求得哈弗曼编码的方法。

理解树的基本概念，熟悉树的多种存储结构，掌握采用孩子兄弟链表存储结构实现树的遍历、插入、删除等操作算法。

通过研究树和二叉树，深刻理解链式存储结构用于表达非线性结构的作用，掌握采用递归算法实现递归数据结构基本操作的设计方法。 二 题目及题意分析

题目：插入x元素作为p结点的第i个孩子

分析：以中国城市作为元素,以插入孩子结点的方式构造一棵树，找到结点p，p不为空时，若p的孩子结点为空，则直接插入x元素作为p的孩子;若p的孩子结点不为空，插入的x元素的位置n小于等于1时，将x元素直接插在最前面;若n大于1时，查找插入的位置执行插入。

三 设计方案和功能说明 源程序如下： TreeNode.h

template

class 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

#include\"TreeNode.h\" //树的孩子兄弟链表节点类 template

class 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); };

template

Tree::Tree() //构造空树 { root=NULL; }

template

bool Tree::isEmpty()//判断是否空树 { return root==NULL; }

template

TreeNode* Tree::insertChild(TreeNode*p,T value) p的孩子 { TreeNode*q=NULL; if(p!=NULL) { q=new TreeNode (value); if(p->child==NULL) p->child=q; else { p=p->child; while(p->sibling!=NULL) p=p->sibling; p->sibling=q; } }

return q; }

//插入value作为结点

template

TreeNode*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(i<=1)//带有容错功能 { p->child=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; }

template

void Tree::preOrder(TreeNode *p,int i) { if(p!=NULL) { for(int j=0;jcout<data<child,i+1); preOrder(p->sibling,i); } }

template

ostream&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); cout<}

四 运行结果及分析

1插入位置小于等于1（即n<=1） n=-2时

n=0时

n=1时

2插入位置大于1（即n>1） n=2时

五 实验总结

通过实验理解了树及二叉树的存储结构熟悉掌握了孩子兄弟链表的存储结构实现，以及遍历、查找、删除等操作，深刻理解实现链式存储结构表达非线性的树存储结构。