当前位置：文档之家 › 数据结构课程设计---二叉树的操作

数据结构课程设计---二叉树的操作

  • 格式：doc
  • 大小：141.50 KB
  • 文档页数：10

数据结构课程设计题目：二叉树的操作学生姓名：学号：系部名称：计算机科学与技术系专业班级：指导教师：课程设计任务书第一章程序要求1）完成二叉树的基本操作。

2）建立以二叉链表为存储结构的二叉树；3）实现二叉树的先序、中序和后序遍历；4）求二叉树的结点总数、叶子结点个数及二叉树的深度。

第二章算法分析建立以二叉链表为存储结构的二叉树，在次二叉树上进行操作；1先序遍历二叉树的操作定义为：若二叉树唯恐则为空操作；否则（1）访问根节点；（2）先序遍历做字数和；（3）先序遍历有子树；2中序遍历二叉树的操作定义为：若二叉树为空，则空操作;否则（1）中序遍历做子树；（2）访问根节点；（3）中序遍历有子树；3后续遍历二叉树的操作定义为：若二叉树为空则为空操作；否则（1)后序遍历左子树;（2)后序遍历右子树;（3）访问根节点；二叉树的结点总数、叶子结点个数及二叉树的深度。

第三章二叉树的基本操作和算法实现二叉树是一种重要的非线性数据结构，是另一种树形结构，它的特点是每个节点之多有两棵子树(即二叉树中不存在度大于2的结点)，并且二叉树的结点有左右之分，其次序不能随便颠倒。

1.1二叉树创建二叉树的很多操作都是基于遍历实现的。

二叉树的遍历是采用某种策略使得采用树形结构组织的若干年借点对应于一个线性序列。

二叉树的遍历策略有四种：先序遍历中续遍历后续遍历和层次遍历。

基本要求1 从键盘接受输入数据（先序），以二叉链表作为存储结构，建立二叉树。

2 输出二叉树。

3 对二叉树进行遍历（先序，中序，后序和层次遍历）4 将二叉树的遍历打印出来。

一．问题描述二叉树的很多操作都是基于遍历实现的。

二叉树的遍历是采用某种策略使得采用树型结构组织的若干结点对应于一个线性序列。

二叉树的遍历策略有四种：先序遍历、中序遍历、后序遍历和层次遍历。

二．基本要求1．从键盘接受输入数据（先序），以二叉链表作为存储结构，建立二叉树。

2．输出二叉树。

3．对二叉树进行遍历（先序、中序、后序和层次遍历）。

4．将二叉树的遍历结果打印输出。

三．提示与分析1．主要数据类型①二叉链表# define DataType char /*元素类型*/typedef struct BiTNode{DataType data;struct BiTNode *lchild, *rchild;}BiTNode, *BiTree;②二叉树的遍历序列DataType preorder[n];DataType inorder[n];DataType postorder[n];2．基本功能分析①采用教材上类似于先序遍历的方法逐个输入结点，建立二叉链表存储的二叉树。

②采用递归算法对二叉树分别进行先序、中序、后序遍历。

③以队列为辅助结构实现二叉树的层次遍历。

④结合先序遍历，以凹入表形式输出二叉树。

//定义二叉树结点结构和操作的头文件btree1.h//定义二叉树结点值的类型为字符型typedef char ElemType;//定义二叉树结点类型struct BTreeNode {ElemType data;BTreeNode* left;BTreeNode* right;};//初始化二叉树，即把树根指针置空void InitBTree(BTreeNode*& BT);//判断二叉树是否为空bool BTreeEmpty(BTreeNode* BT);1.1.1 二叉树的遍历二叉树的遍历即是如何按照某条路径寻访每一个结点，使得每个结点均被访问一次，而且仅被访问一次。

“访问”的含义很广，可以是对结点做出各种处理，如输出结点的信息等。

遍历对线性结构来说是一个容易解决的问题，而对于二叉树则不然，由于二叉树是一种非线性结构，每个结点都有可能有俩棵子树，因而需要寻找一种规律，以便使二叉树上的结点都能够排列在线性队列上，从而便于遍历。

二叉树室友三个基本单位组成的：根节点左子树和右子树。

因而遍历着三个部分，便是遍历了整个二叉树。

void TraverseBTree(BTreeNode* BT, int mark){if(mark==1) { //先序遍历if(BT!=NULL) {cout<<BT->data<<' ';TraverseBTree(BT->left,mark);TraverseBTree(BT->right,mark);}}else if(mark==2) { //中序遍历if(BT!=NULL) {TraverseBTree(BT->left,mark);cout<<BT->data<<' ';TraverseBTree(BT->right,mark);}}else if(mark==3) { //后序遍历if(BT!=NULL) {TraverseBTree(BT->left,mark);TraverseBTree(BT->right,mark);cout<<BT->data<<' ';}}else if(mark==4) //按层遍历{const MaxLength=30;BTreeNode* Q[MaxLength];//定义存储二叉树结点指针的数组空间作为队列使用int front=0, rear=0;//定义队首指针和队尾指针，初始均置0表示空队BTreeNode* p;｝1.1.1.1 求二叉树的结点总数叶子节点个数及二叉树的深度//用于求二叉树深度的递归函数int Depth(BTreeNode* BT){if(BT==NULL)return 0; //对于空树，返回0并结束递归else{//计算左子树的深度int dep1=Depth(BT->left);//计算右子树的深度int dep2=Depth(BT->right);//返回树的深度if(dep1>dep2) return dep1+1;else return dep2+1;｝}//求二叉树中所有结点数int BinaryTree::BTreeCount(){return Count(root);}//用于求二叉树中所有结点数的递归函数int Count(BTreeNode* BT){if(BT==NULL) return 0;elsereturn Count(BT->left)+Count(BT->right)+1;}//求二叉树中所有叶子结点数int BinaryTree::BTreeLeafCount(){return LeafCount(root);}//用于求二叉树中所有叶子结点数的递归函数int LeafCount(BTreeNode* BT){if(BT==NULL) return 0;else if(BT->left==NULL && BT->right==NULL) return 1;else return LeafCount(BT->left)+LeafCount(BT->right); ｝第四章调试结果测试数据1．输入：ABC+DE+G++F+++（其中+表示空格字符）则输出结果为：先序：ABCDEGF中序：CBEGDFA后序：CGEFDBA2．输入：AB+DG+++CE++F++先序：ABDGCEF中序：BGDAECF后序：GDBEFCA3．输入：ABDF++++C+E+G++先序：ABDFCEG中序：FDBACEG后序：FDBGECA第五章实习体会数据结构的实习是培养学生综合运用所学知识,发现,提出,分析和解决实际问题,锻炼实践能力的重要环节,是对学生实际工作能力的具体训练和考察过程. 回顾起此数据结构实习，至今我仍感慨颇多，的确，从选题到定稿，从理论到实践，在整整两星期的日子里，可以说得是苦多于甜，但是可以学到很多很多的的东西，同时不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。

通过这次实习使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，从而提高自己的实际动手能力和独立思考的能力。

在设计的过程中遇到问题，可以说得是困难重重，这毕竟第一次做的，难免会遇到过各种各样的问题，同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固。

经过两个星期的上机实践学习，使我对数据机构有了更进一步的认识和了解，要想学好它要重在实践，要通过不断的上机操作才能更好地学习它，通过实践，我也发现我的好多不足之处，首先是自己对知识点的掌握不够熟悉，通过学习也有所改进；再有对C语言的一些标准库函数不太了解，还有对函数调用的正确使用不够熟悉，还有对C语言中经常出现的错误也不了解，通过实践，使我在这几个方面的认识有所提高。

通过实践的学习，我认到学好计算机要重视实践操作，不仅仅是学习C语言，还是其它的语言，以及其它的计算机方面的知识都要重在实践，所以后在学习过程中，我会更加注视实践操作，使自己便好地学好计算机。

在今后的日子里，认真对待每意见事，争取做到最好，努力将知识与实践相结合，不断巩固，加深所学的知识，做到学以致用。

参考文献：1.严蔚敏、吴伟民，《数据结构》（C语言版），北京：清华大学出版社，2006.52.宁正元、易金聪，《数据结构习题解析与上机实验指导》，中国水利水电出版社、上海交通大学出版社、东南大学出版社，2002.63.刘怀亮，《数据结构习题解析与实验指导》（C语言描述），冶金工业出版社，2005.2目录第一章程序要求—————————————— 1第二章算法分析—————————————— 1第三章二叉树的基本操作和算法实现——————— 11.1 二叉树的创建---------------------------------- 41.1.1 二叉树的遍历-------------------------------- 71.1.1.1 求二叉树的结点个数叶子节点个数及二叉树的深度--------------------- 7 第四章调试结果———————————————8 第五章实习体会———————————————9。

合集下载

数据结构实验3：二叉树的操作

数据结构实验3：二叉树的操作

TextFile中。

(4) P：打印代码文件(Print)。

将文件CodeFile以紧凑格式显示在终端上，每行50个代码。

同时将此字符形式的编码文件写入文件CodePrin中。

(5) T：打印哈夫曼树(Tree printing)。

将已在内存中的哈夫曼树以直观的方式显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。

3) 实现提示：(1) 文件CodeFile的基类型可以设为字节型。

(2) 用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quit。

请用户键入一个选择功能符。

此功能执行完毕后再显示此菜单，直至某次用户选择了“E”为止。

(3) 在程序的一次执行过程中，第一次执行I、D或C命令之后，哈夫曼树已经在内存了，不必再读入。

每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。

三、实验过程与实验结果实验3-01：以二叉链表为存储结构，实现二叉树的创建、遍历数据结构定义：typedef struct BiTNode{char data;BiTNode *lchild, *rchild;}BiTNode;typedef BiTNode *BiTree;算法设计思路简介：本实验需要实现以下操作：二叉树的初始化、前中后序遍历等基本操作1.利用递归实现前后序遍历，思路简洁，仅需要调整递归体的执行顺序即可实现。

2.利用非递归实现中序遍历，需要利用栈操作，按照中序遍历规则将节点依次入栈后出栈实现。

算法描述：图1 中序遍历（非递归）实现算法的实现和测试结果（参考OJ）实验3-02：编写算法交换二叉树中所有结点的左、右子树数据结构定义：typedef struct BiTNode{char data;BiTNode *lchild, *rchild;}BiTNode;typedef BiTNode *BiTree;算法设计思路简介：本实验需要实现以下操作：二叉树的初始化、前中后序遍历等基本操作1.利用递归实现前后序遍历，思路简洁，仅需要调整递归体的执行顺序即可实现。

数据结构课程设计-二叉树的基本操作Word版

数据结构课程设计-二叉树的基本操作Word版

数据结构课程设计报告设计题目：二叉树的基本操作专业：计算机科技院系：计算机学院姓名：xx xx学号：xxxxxxxx时间：2013年9月22日目录一、设计要求-------------------------------------------------------31.问题描述----------------------------------------------------32.需求分析----------------------------------------------------3二、详细设计--------------------------------------------------------31.概要设计-----------------------------------------------------32.各模块源代码-----------------------------------------------3三、用户手册--------------------------------------------------------9四、总结-------------------------------------------------------------10一、设计要求1.问题描述设计一个与二叉树基本操作相关的演示程序。

2.需求分析（1）创建二叉树。

按照用户需要构建二叉树（2）分别以先序、中序、后序遍历二叉树（3）查找子节点元素二、详细设计（附源代码）1.概要设计//定义二叉树数据结构typedef struct TNode{int num;struct TNode *lchild, *rchild;}TNode;2．各模块源代码（包含main( )函数）#include<stdio.h>#include<stdlib.h>#define MaxLength 100//定义二叉树数据结构typedef struct TNode{int num;struct TNode *lchild, *rchild;}TNode;//声明全局变量rootstatic TNode *root=NULL;//声明插入新结点的函数(根非空)int myInsert_Node(TNode *p, int n);//定义插入新节点的初始函数，拆开写的目的是递归时避免不必要的判断void Insert_Node(int n){if(root==NULL) //如果根结点不存在则创建{root=(TNode *)malloc(sizeof(TNode));root->num=n;root->lchild=NULL;root->rchild=NULL;}else{myInsert_Node(root, n);//非根结点的插入操作}}int myInsert_Node(TNode *p, int n){TNode *temp;if(n<p->num) //比当前结点小，则访问左子树{if(p->lchild==NULL) //左子树为空，则插入该结点{temp=(TNode *)malloc(sizeof(TNode));temp->num=n;temp->lchild=NULL;temp->rchild=NULL;p->lchild=temp;return 0;}else //左子树不为空，则与左子树进行比较{myInsert_Node(p->lchild,n);}}else //右子树同理{if(p->rchild==NULL){temp=(TNode *)malloc(sizeof(TNode));temp->num=n;temp->lchild=NULL;temp->rchild=NULL;p->rchild=temp;return 0;}else{myInsert_Node(p->rchild,n);}}}//前序递归遍历二叉树void Pre_travel(TNode *p){if(p){printf("%d ",p->num);Pre_travel(p->lchild);Pre_travel(p->rchild);}}//中序递归遍历二叉树void Mid_travel(TNode *p){if(p){Mid_travel(p->lchild);printf("%d ",p->num);Mid_travel(p->rchild);}}//后序递归遍历二叉树void Suf_travel(TNode *p){if(p){Suf_travel(p->lchild);Suf_travel(p->rchild);printf("%d ", p->num);}}//中序非递归遍历二叉树/*从根节点开始，沿左子树一直走到没有左孩子的节点为止，并将所经过的节点的地址进栈；当找到没有左孩子的节点时，从栈顶退出该节点并访问它，此时，此节点的左子树已访问完毕；在用上述方法遍历该节点的右子树，如此重复到栈空为止。

数据结构实验报告—二叉树

数据结构实验报告—二叉树

数据结构实验报告—二叉树数据结构实验报告—二叉树引言二叉树是一种常用的数据结构，它由节点和边构成，每个节点最多有两个子节点。

在本次实验中，我们将对二叉树的基本结构和基本操作进行实现和测试，并深入了解它的特性和应用。

实验目的1. 掌握二叉树的基本概念和特性2. 熟练掌握二叉树的基本操作，包括创建、遍历和查找等3. 了解二叉树在实际应用中的使用场景实验内容1. 二叉树的定义和存储结构：我们将首先学习二叉树的定义，并实现二叉树的存储结构，包括节点的定义和节点指针的表示方法。

2. 二叉树的创建和初始化：我们将实现二叉树的创建和初始化操作，以便后续操作和测试使用。

3. 二叉树的遍历：我们将实现二叉树的前序、中序和后序遍历算法，并测试其正确性和效率。

4. 二叉树的查找：我们将实现二叉树的查找操作，包括查找节点和查找最大值、最小值等。

5. 二叉树的应用：我们将探讨二叉树在实际应用中的使用场景，如哈夫曼编码、二叉搜索树等。

二叉树的定义和存储结构二叉树是一种特殊的树形结构，它的每个节点最多有两个子节点。

节点被表示为一个由数据和指向其左右子节点的指针组成的结构。

二叉树可以分为三类：满二叉树、完全二叉树和非完全二叉树。

二叉树可以用链式存储结构或顺序存储结构表示。

- 链式存储结构：采用节点定义和指针表示法，通过将节点起来形成一个树状结构来表示二叉树。

- 顺序存储结构：采用数组存储节点信息，通过计算节点在数组中的位置来进行访问和操作。

二叉树的创建和初始化二叉树的创建和初始化是二叉树操作中的基础部分。

我们可以通过手动输入或读取外部文件中的数据来创建二叉树。

对于链式存储结构，我们需要自定义节点和指针，并通过节点的方式来构建二叉树。

对于顺序存储结构，我们需要定义数组和索引，通过索引计算来定位节点的位置。

一般来说，初始化一个二叉树可以使用以下步骤：1. 创建树根节点，并赋初值。

2. 创建子节点，并到父节点。

3. 重复步骤2，直到创建完整个二叉树。

数据结构实验三——二叉树基本操作及运算实验报告

数据结构实验三——二叉树基本操作及运算实验报告

《数据结构与数据库》实验报告实验题目二叉树的基本操作及运算一、需要分析问题描述：实现二叉树（包括二叉排序树）的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目，以及二叉树常用运算。

问题分析：二叉树树型结构是一类重要的非线性数据结构，对它的熟练掌握是学习数据结构的基本要求。

由于二叉树的定义本身就是一种递归定义，所以二叉树的一些基本操作也可采用递归调用的方法。

处理本问题，我觉得应该：1、建立二叉树；2、通过递归方法来遍历（先序、中序和后序）二叉树；3、通过队列应用来实现对二叉树的层次遍历；4、借用递归方法对二叉树进行一些基本操作，如：求叶子数、树的深度宽度等；5、运用广义表对二叉树进行广义表形式的打印。

算法规定：输入形式：为了方便操作，规定二叉树的元素类型都为字符型，允许各种字符类型的输入，没有元素的结点以空格输入表示，并且本实验是以先序顺序输入的。

输出形式：通过先序、中序和后序遍历的方法对树的各字符型元素进行遍历打印，再以广义表形式进行打印。

对二叉树的一些运算结果以整型输出。

程序功能：实现对二叉树的先序、中序和后序遍历，层次遍历。

计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目。

对二叉树的某个元素进行查找，对二叉树的某个结点进行删除。

测试数据：输入一：ABC□□DE□G□□F□□□（以□表示空格）,查找5,删除E预测结果：先序遍历ABCDEGF中序遍历CBEGDFA后序遍历CGEFDBA层次遍历ABCDEFG广义表打印A（B（C,D（E（,G）,F）））叶子数3 深度5 宽度2 非空子孙数6 度为2的数目2 度为1的数目2查找5，成功，查找的元素为E删除E后，以广义表形式打印A（B（C,D（,F）））输入二：ABD□□EH□□□CF□G□□□（以□表示空格）,查找10,删除B预测结果：先序遍历ABDEHCFG中序遍历DBHEAGFC后序遍历DHEBGFCA层次遍历ABCDEFHG广义表打印A（B(D,E(H)),C(F(,G))）叶子数3 深度4 宽度3 非空子孙数7 度为2的数目2 度为1的数目3查找10，失败。