下载文档原格式
实验报告（2014 / 2015 学年第一学期）课程名称数据结构实验名称二叉树基本操作以及哈夫曼编码译码系统实验时间年月日指导单位指导教师学生姓名班级学号学院(系) 专业二叉树的基本运算：一、问题描述1.设计递归算法，实现二叉树的运算：删除一棵二叉树，求一棵二叉树的高度，求一棵二叉树中叶子节点数，复制一棵二叉树，交换一棵二叉树的左右子树2.设计算法，自上而下，自左向右即按层次遍历一棵二叉树3.设计main函数，测试上述每个运算二、系统分析和概要设计首先用maketree构造一棵二叉树，然后遍历二叉树，然后交换每个结点的左右子树，接着算出输得高度和叶子节点，最后删除。
三、详细设计2. 核心算法建立二叉树的void MakeTree(const T& x,BinaryTree<T>& left,BinaryTree<T>& right)和计算叶子节点的int Size();3. 算法分析删除一棵二叉树，求一棵二叉树的高度，求一棵二叉树中叶子节点数，复制一棵二叉树等都是用递归的方法实现。
四、程序代码流程图#include<iostream.h>template<class T>struct BTNode{BTNode(){lChild=rChild=NULL;}BTNode(const T &x){element=x;lChild=rChild=NULL;}BTNode(const T &x,BTNode<T>* l,BTNode<T>* r){element=x;lChild=l;rChild=r;}T element;BTNode<T>* lChild,* rChild;};template<class T>class BinaryTree{public:BinaryTree(){root=NULL;}~BinaryTree(){Clear();}void Copy(BinaryTree<T> &r) const;bool IsEmpty()const{return root == NULL;}void Clear();void Exchange();bool Root(T& x)const;int GetHeight();void MakeTree(const T& x,BinaryTree<T>& left,BinaryTree<T>& right);void BreakTree(T& x,BinaryTree<T>& left,BinaryTree<T>& right);void PreOrder(void (*Visit)(T &x));void LevelOrder(void (*Visit)(T& x));int Size();BinaryTree<T>(BinaryTree<T> &t)root=Copy(t.root);}// void InOrder(void (*Visit)(T &x));// void PostOrder(void (*Visit)(T &x));BTNode<T>* Copy(BTNode<T>* t);protected:BTNode<T> * root;private:static int number;void Clear(BTNode<T>* &t);void Exchange(BTNode<T>* t);int GetHeight(BTNode<T>* t);int Size(BTNode<T>* t);void PreOrder(void (*Visit)(T &x),BTNode<T>* t);void LevelOrder(void (*Visit)(T& x),BTNode<T>* t); // void InOrder(void (*Visit)(T &x),BTNode<T>* t);// void PostOrder(void (*Visit)(T &x),BTNode<T>* t); };template <class T>bool BinaryTree<T>::Root(T &x)const{if(root){x=root->element;return true;}elsereturn false;}template <class T>void BinaryTree<T>::Clear(){Clear(root);}template <class T>void BinaryTree<T>::Clear(BTNode<T>* &t){if(t)Clear(t->lChild);Clear(t->rChild);delete t;t=NULL;}}template <class T>void BinaryTree<T>::MakeTree(const T& x,BinaryTree<T>& left,BinaryTree<T>& right) {if(root||&left==&right)return;root=new BTNode <T>(x,left.root,right.root);left.root=right.root=NULL;}template <class T>void BinaryTree<T>::BreakTree(T& x,BinaryTree<T>& left,BinaryTree<T>& right) {if(!root||&left==&right||left.root||right.root)return;x=root->element;left.root=root->lChild;right.root=root->rChild;delete root;root=NULL;}template <class T>BTNode<T>* BinaryTree<T>::Copy(BTNode<T>* t){if(!t)return NULL;BTNode<T>*q=new BTNode<T>(t->element);q->lChild=Copy(t->lChild);q->rChild=Copy(t->rChild);return q;}template <class T>void Visit(T &x){cout<<x<<" ";}template <class T>void BinaryTree<T>::PreOrder(void (*Visit)(T& x)){PreOrder(Visit,root);}template <class T>void BinaryTree<T>::PreOrder(void (*Visit)(T& x),BTNode<T>* t) {if(t){Visit(t->element);PreOrder(Visit,t->lChild);PreOrder(Visit,t->rChild);}}template <class T>void BinaryTree<T>::Exchange(){Exchange(root);}template <class T>void BinaryTree<T>::Exchange(BTNode<T>* t){if(!t)return;BTNode<T>* temp;temp=t->lChild;t->lChild=t->rChild;t->rChild=temp;Exchange(t->lChild);Exchange(t->rChild);}template <class T>int BinaryTree<T>::GetHeight(){return GetHeight(root);}int BinaryTree<T>::GetHeight(BTNode<T>* t){int templ;int tempr;if(!t)return 0;templ=GetHeight(t->lChild);tempr=GetHeight(t->rChild);if(templ++>tempr++)return templ;elsereturn tempr;}template <class T>int BinaryTree<T>::number=0;template <class T>int BinaryTree<T>::Size(){Size(root);return number;}template <class T>int BinaryTree<T>::Size(BTNode<T>* t){if(t!=NULL){Size(t->lChild);if(t->lChild ==NULL&&t->rChild ==NULL)number++;Size(t->rChild);}return number;}template <class T>void BinaryTree<T>::LevelOrder(void (*Visit)(T& x)) {PreOrder(Visit,root);}void BinaryTree<T>::LevelOrder(void (*Visit)(T& x),BTNode<T>* t) {BTNode *quene[50],*p;int pre=1,rear=1;quene[++pre]=t;while(pre!=0){p=quene[++rear];cout<<p->element<<" ";if(p->lChild !=NULL)quene[++pre]=p->rChild ;if(p->rChild !=NULL)quene[++pre]=p->lChild ;}}void main(){BinaryTree <char> a,b,x,y,z;y.MakeTree('E',a,b);z.MakeTree('F',a,b);x.MakeTree('C',y,z);y.MakeTree('D',a,b);z.MakeTree('B',y,x);cout<<"二叉树z的先序遍历:"<<endl;z.PreOrder(Visit);cout<<endl;cout<<"层次遍历二叉树:";z.LevelOrder(Visit);cout<<endl;BinaryTree<char> q(z);cout<<"复制的二叉树q的先序遍历:"<<endl;q.PreOrder(Visit);cout<<endl;cout<<"树的高度:";cout<<z.GetHeight()<<endl;cout<<"叶子节点数量:";cout<<z.Size()<<endl;z.Exchange();cout<<"二叉树左右子树交换后的先序遍历:"<<endl;z.PreOrder(Visit);cout<<endl;}五、测试用例和运行结果测试用例如main函数中所示，结果如下图所示。
内蒙古科技大学本科生课程设计说明书题目：数据结构课程设计——二叉树的遍历和应用学生姓名：学号：专业：班级：指导教师：2013年5月29日内蒙古科技大学课程设计说明书内蒙古科技大学课程设计任务书I内蒙古科技大学课程设计说明书目录内蒙古科技大学课程设计任务书..............................................................错误！未定义书签。
目录 (II)第一章需求分析 (3)1.1课程设计目的 (3)1.2任务概述 (3)1.3课程设计内容 (3)第二章概要设计 (5)2.1设计思想 (5)2.2二叉树的遍历 (5)2.3运行界面设计 (6)第三章详细设计 (7)3.1二叉树的生成 (7)3.2二叉树的先序遍历 (7)3.3 二叉树的中序遍历 (8)3.4二叉树的后续遍历 (8)3.5主程序的设计 (8)第四章测试分析 (11)4.1二叉树的建立 (11)4.2二叉树的先序、中序、后序遍历 (11)第五章课程设计总结 (12)附录：程序代码 (13)致谢 ···········································································································错误！未定义书签。
二叉排序树操作一、设计步骤1）分析课程设计题目的要求2）写出详细设计说明3）编写程序代码，调试程序使其能正确运行4）设计完成的软件要便于操作和使用5）设计完成后提交课程设计报告（一）程序功能：1）创建二叉排序树2）输出二叉排序树3）在二叉排序树中插入新结点4）在二叉排序树中删除给定的值5）在二叉排序树中查找所给定的值（二）函数功能：1） struct BiTnode 定义二叉链表结点类型包含结点的信息2） class BT 二叉排序树类，以实现二叉排序树的相关操作3） InitBitree() 构造函数，使根节点指向空4) ~BT () 析构函数，释放结点空间5) void InsertBST(&t,key) 实现二叉排序树的插入功能6) int SearchBST(t,key) 实现二叉排序树的查找功能7) int DelBST(&t,key) 实现二叉排序树的删除功能8) void InorderBiTree (t) 实现二叉排序树的排序（输出功能）9) int main() 主函数，用来完成对二叉排序树类中各个函数的测试二、设计理论分析方法（一）二叉排序树定义首先，我们应该明确所谓二叉排序树是指满足下列条件的二叉树：（1）左子树上的所有结点值均小于根结点值；（2）右子数上的所有结点值均不小于根结点值；（3）左、右子数也满足上述两个条件。
根据对上述的理解和分析，我们就可以先创建出一个二叉链表结点的结构体类型（struct BiTNode）和一个二叉排序树类（class BT），以及类中的构造函数、析构函数和其他实现相关功能的函数。
（二）插入函数（void InsertBST(&t,key)）首先定义一个与BiTNode<k> *BT同一类型的结点p，并为其申请空间，使p->data=key,p->lchild和p->rchild=NULL。
二叉树实验心得(优秀5篇)二叉树实验心得篇1二叉树实验心得在进行二叉树实验的过程中，我不仅掌握了一个重要的数据结构——二叉树，还从中体验到了深入理解一个数据结构的魅力和乐趣。
在实验开始时，我首先学习了二叉树的基本概念，如节点、左子树、右子树等。
我明白了二叉树是一种重要的数据结构，它具有层次结构，每个节点最多有两个子节点，且没有祖先节点的左或右子树中的任何一个节点。
接下来，我学习了二叉树的遍历，包括前序遍历、中序遍历和后序遍历。
通过实验，我明白了这些遍历方式的实现原理，并能够灵活地应用它们。
此外，我还学习了递归和迭代两种方法来实现这些遍历方式，这两种方法各有优点和缺点，我深入了解了它们之间的差异。
在进行实验的过程中，我遇到了一些问题，如递归方法导致的栈溢出，以及中序遍历中的栈和队列的使用。
我通过查阅资料和讨论，解决了这些问题，并从中获得了宝贵的经验。
通过这次实验，我更加深入地理解了二叉树的结构和遍历方式，并能够在实际应用中灵活使用。
我明白了数据结构的重要性，以及深入理解数据结构的过程中的乐趣。
同时，我也学会了如何解决问题，并从中获得了宝贵的经验。
总的来说，这次实验是一个非常有意义的经历，我不仅掌握了新的知识，还锻炼了自己的解决问题的能力。
我相信，这次实验将对我未来的学习和工作产生积极的影响。
二叉树实验心得篇2二叉树实验心得这次实验我们了解了二叉树的基本概念，包括二叉树、结点、左子树、右子树、祖先节点等概念。
通过实验，我们对二叉树的性质有了更深刻的理解，比如二叉树只有左子树或右子树，没有左右子树的情况，即空子树。
在实现二叉树时，我们了解了二叉树节点的定义和插入节点的多种方法，包括先插法、后插法等。
我们还学会了利用二叉树来解决实际问题，比如快速查找等问题。
在实验过程中，我们对二叉树的知识进行了深入探究，收获颇丰。
通过这次实验，我对二叉树有了更深刻的认识，明白了二叉树在计算机科学中的重要性。
同时，我对自己的编程能力也有了新的认识，发现自己可以在理解算法的基础上更好地实现它们。
二叉树实验知识点总结
一、二叉树的基本概念
二叉树是一种特殊的树形结构，其每个节点最多只有两个子节点。
二叉树分为满二叉树、完全二叉树和普通二叉树等类型。
二、遍历方式
1.前序遍历：先访问当前节点，再遍历左子树和右子树；
2.中序遍历：先遍历左子树，再访问当前节点，最后遍历右子树；
3.后序遍历：先遍历左子树和右子树，最后访问当前节点；
4.层次遍历：按照从上到下、从左到右的顺序依次访问每个节点。
三、常见操作
1.插入节点：在二叉搜索树中插入一个新的节点；
2.删除节点：在二叉搜索树中删除一个指定的节点；
3.查找节点：在二叉搜索树中查找一个指定的节点；
4.求深度：计算二叉搜索树的深度。
四、平衡二叉树
平衡二叉树是一种特殊的二叉搜索树，其左右子树高度差不能超过1。
常见的平衡二叉搜索包括红黑树、AVL 树等。
五、应用场景
1.数据库索引；
2.哈夫曼编码；
3.表达式求值；
4.图形处理等。
六、注意事项
1.二叉树的插入、删除和查找操作需要保证二叉树的结构不被破坏；
2.平衡二叉树的实现需要注意平衡因子的计算和旋转操作的实现；
3.在使用二叉树进行算法设计时，需要考虑遍历方式和时间复杂度等问题。
七、总结
二叉树是一种重要的数据结构，在算法设计中有广泛的应用。
掌握二叉树的基本概念、遍历方式、常见操作和应用场景，可以帮助我们更好地理解和使用这种数据结构。
同时，我们需要注意在实际应用中遵循相关规范，保证程序的正确性和效率。
树左旋和右旋的原理介绍树的左旋和右旋是二叉搜索树中常见的操作，用于调整树的结构以维持平衡性。
左旋和右旋的原理是通过改变树中节点之间的指向关系来实现的，从而改变树的形状。
二叉搜索树在深入了解左旋和右旋的原理之前，我们先来了解一下二叉搜索树（Binary Search Tree，简称BST）。
二叉搜索树是一种特殊的二叉树，它具有以下性质：1. 左子树上的所有节点的值都小于根节点的值。
2. 右子树上的所有节点的值都大于根节点的值。
3. 左右子树也分别为二叉搜索树。
二叉搜索树的这种特性使得它在查找、插入和删除操作中具有高效性能。
左旋的原理左旋是指将一个节点的右子树变为其父节点，同时将该节点作为其右子树的左子节点。
左旋的目的是为了调整树的结构，使得树保持平衡。
左旋的步骤左旋的具体步骤如下： 1. 将要进行左旋的节点记为node。
2. 将node的右子节点记为rightChild。
3. 将rightChild的左子节点（如果存在）记为rightLeftChild。
4. 将node的父节点记为parent。
5. 将rightChild的左子节点设置为node。
6. 将rightChild的父节点设置为parent。
7. 如果parent为空，说明node原本是根节点，现在rightChild成为新的根节点。
8. 如果parent不为空，将parent的左子节点或右子节点设置为rightChild，取决于node在parent的位置。
左旋示意图下面是一个示意图，展示了左旋的过程：parent parent/ /node => rightChild\ /rightChild node右旋的原理右旋是指将一个节点的左子树变为其父节点，同时将该节点作为其左子树的右子节点。
右旋的目的同样是为了调整树的结构，保持平衡。
右旋的步骤右旋的具体步骤如下： 1. 将要进行右旋的节点记为node。
2. 将node的左子节点记为leftChild。
目录 一 需求分析.................................................................................................................. 1 二 概要设计.................................................................................................................. 1 三 详细设计.................................................................................................................. 2 四 调试分析和测试结果.............................................................................................. 4 五 总结.......................................................................................................................... 6 六 参考文献.................................................................................................................. 7 七 致谢.......................................................................................................................... 7 八 附录.......................................................................................................................... 7 1
一 需求分析 问题描述：交换二叉树中所有结点的左、右子树，该二叉树以二叉链表作为存储结构。 基本思想：设二叉树的根指针为s，且以二叉链表表示，可利用一个类型为Q的指针队列来实现，且设队列单元包含两个域，一个为front，一个为rear，整个队列容量为maxsize，当树非空时，将当前的树根结点入队列，同时将当前队列顶元素出队列当作根结点，然后依据当前的根结点是否具有孩子结点来判定是否将其左、右指针进行交换；再将交换后的左指针或右指针入队列，这样反复进行，直到队列空为止。 图1-1是该课题的功能模块图：
图 1-1
二 概要设计
该课题主要分为三个功能模块：重新建立二叉树、交换左右子数、先根遍历二叉树。这里主要用到了队列及二叉树的知识，先对二叉树进行层次遍历，然后
二叉树结点的左、右子树的交换 重新建立二叉树 交换左右子数 先根遍历二叉树退出 2
再进行左右子树交换操作，最后再进行先根遍历二叉树，这就实现了二叉树节点的左右子树交换。三个功能模块相互独立又相互关联，独立仅在于各自操作互不影响，而关联在于后两个功能可以对当前建立的二叉树进行操作，产生不同的结果。 该功能流程图（图2-1）如下：
三 详细设计
本课题为二叉树结点的左、右子树的交换，主要分为三个模块：重新建立二叉树、交换左右子数、先根遍历二叉树。各模块的详细设计如下：
开 始 输入二叉树的节点（以“！“结束）
enter
重新建立二叉树
交换左右子数
先根遍历二叉树
菜 单 2 1 3
0
结 束 图2-1 3
首先定义结构体类型及二叉树结点类型，如下所示： typedef char datatype; // 树的结点数据类型为字符型，可以根据需要修改 typedef struct node *pointer; // 定义二叉树结点类型 struct node { datatype data; //结点数据 pointer lchild,rchild; //左右孩子结点 }; 三个模块各写三个函数，分别如下所示： bitree level_creat() //由层次序列建立二叉树，返回根指针 { char ch; ch=cin.get(); int front,rear; pointer root,s; root=NULL; //置空二叉树 front=rear=0; //置空队列 //while(cin>>ch,ch!='!') while(cin>>ch,ch!='!') { if(ch!='@') //非虚结点，建立新结点 { s=new node; s->data=ch; s->lchild=s->rchild=NULL; } else s=NULL; rear++; Q[rear]=s; //不管结点是否为虚都要入队 if(rear==1) { root=s; front=1; } //第一个点是根，要修改头指针，他不是孩子 else if(s && Q[front]) //孩子和双亲都不是虚结点 if(rear%2==0) Q[front]->lchild=s; // rear是偶数，新结点是左孩子 else { Q[front]->rchild=s; //rear 是奇数，新结点是右孩子 front++; } } return root; } void exchange(bitree t) //交换左右子数函数 { pointer p; 4
if(t==NULL) return; //空树，直接返回 p=t->lchild; t->lchild=t->rchild; t->rchild=p; //交换 exchange(t->rchild); //遍历原左子树 exchange(t->lchild); //遍历原右子树 } void preorder(bitree t) //先根遍历函数 { if(t==NULL) return; cout
} 四 调试分析和测试结果
本人主要编写main（）函数及先根遍历函数，主函数还是比较简单，就是先根遍历函数有一个小问题：输入的的第一个树即根结点始终打印不出来，分析代码，也没发现什么错误，比较纠结。 下面是测试结果截图： 图4-1为程序运行首页。
图4-1 图4-2为输入二叉树结点的界面。 5
图4-2 图4-3为操作菜单。
图4-3 图4-4为左右二叉树交换成功。
图4-4 图4-5为先根遍历输出结果。 6
图4-5 五 总结 在刚选到该课题的时候，感觉挺茫然的，不知从何处入手。毕竟一个寒假过来，上学期学的数据结构知识也忘的差不多了，并且学的也不是很扎实，所以感觉无从下手。在队友的相互帮助下，我们开始加紧的看书，去图书馆借资料以及上网进行搜索相关的资料，并慢慢的开始做起来。 我们这组三人，分工也比较明确，各自主要负责自己的模块。二本人负责先序遍历模块以及主函数的的编写。在编码过程中，我们遇到了很多小问题，以及一些因粗心而造成的错误，我们都一一解决了。只是我这个环节还有一个问题没有得到解决，就是输出先根遍历的结果时根节点没输出来。这个问题困扰我两天，一直没有得到解决。这个需要以后再继续学习、探究。 总的来说，由于时间有限，本次课程设计“马马虎虎”地完成了。从理论到实践，在整整一个星期的日子里，我学到很多很多的东西，不仅巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的内容。通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才是真正的知识，才能提高自己的实际动手能力和独立思考的能力。 7
六 参考文献 1.严蔚敏 吴伟明 数据结构（C语言版）--清华大学出版社 2. csdn论坛 网址：http://www.csdn.com
七 致谢 完成该课题的设计，离不开队友的相互配合、同学的帮助及老师的指导，在此表示十分感谢！
八 附录 //源代码 #include #include #include using namespace std;
/* 二叉树类型的定义(二叉链表形式储存) */ typedef char datatype; // 树的结点数据类型为字符型，可以根据需要修改 typedef struct node *pointer; // 定义二叉树结点类型 struct node { datatype data; //结点数据 pointer lchild,rchild; //左右孩子结点 }; typedef pointer bitree; //定义二叉树类型 /* 先根遍历交换左右子树 */ /* 层次遍历序列生成 */
