太原理工大学 数据结构与算法R 实验报告（2） |
您所在的位置：网站首页 › 武汉理工大学数据结构与算法综合实验图片压缩实验报告 › 太原理工大学 数据结构与算法R 实验报告（2） |
太原理工大学 数据结构与算法R 实验报告（2）
|
实验名称（树） 一、实验目的和要求 熟悉树的各种表示方法和各种遍历方式，掌握有关算法的实现，了解树在计算机科学及其它工程技术中的应用。 二、实验内容和原理 选做第一题、第二题（第一题，第二题写在一个程序里：） 输入： （第一行为先序遍历输入一颗二叉树，空由#代替，第二行输入查找结点序号） ABD##EH###CF#I##G## 3 输出： （先输出三种遍历输出结果，再输出叶子节点个数，最后输出查找位置结点） 先序遍历结果: ABDEHCFIG 中序遍历结果: DBHEAFICG 后序遍历结果: DHEBIFGCA 叶子节点的个数为: 4 第3个位置的节点为: D 存储结构： 二叉链表存储 算法思想： 通过递归思想，若左右孩子皆无，则为递归出口，即叶子节点 通过先序遍历将结点存储在a[]数组中，那么第k个位置的结点即为a[k]的值 三、主要仪器设备 惠普笔记本，win10环境，皆在cpp文件运行，请同样以cpp形式打开 四、操作方法与实验步骤 第一题、第二题： #include #include #define N 1000 char a[N]; int i=1,k; typedef struct node{ char data; struct node * lchild; struct node * rchild; }BiTree; BiTree * CreatTree(); int Count(BiTree * );//叶子节点 void Preorder(BiTree * );//先序遍历 void Middleorder(BiTree * );//中序遍历 void Postorder(BiTree * );//后序遍历 void getNode(BiTree * );//递归算法，在二叉树中求位于先序序列中第K个位置的结点 int main(){ printf("请以先序序列输入一颗二叉树，空以#代替\n"); BiTree * top = NULL; top = CreatTree(); printf("先序遍历结果: "); Preorder(top); printf("\n"); printf("中序遍历结果: "); Middleorder(top); printf("\n"); printf("后序遍历结果: "); Postorder(top); printf("\n"); putchar('\n'); printf("叶子节点的个数为: %d\n",Count(top)); printf("请输入要查找的节点位置: "); scanf("%d",&k); printf("第%d个位置的节点为: ",k); getNode(top); printf("%c\n",a[k]); system("pause"); return 0; } BiTree * CreatTree(){ BiTree *t; char ch; ch = getchar(); if(ch != '#'){ t=(BiTree *)malloc(sizeof(BiTree)); t->data=ch;//先序遍历根左右，空由#代替 t->lchild=CreatTree(); t->rchild=CreatTree(); } else{ t=NULL; } return t; } int Count(BiTree * top){ if(top==NULL){ return 0; } else if((top->lchild==NULL)&&(top->rchild==NULL)){//递归出口，若左右孩子皆空则为叶子节点 return 1; } else { return Count(top->lchild)+Count(top->rchild); } } void Preorder(BiTree *top){ if(top!=NULL){//不空则先序遍历 printf("%c",top->data); Preorder(top->lchild); Preorder(top->rchild); } } void Middleorder(BiTree *top){ if(top!=NULL){//不空则中序遍历 Middleorder(top->lchild); printf("%c",top->data); Middleorder(top->rchild); } } void Postorder(BiTree *top){ if(top!=NULL){//不空则后序遍历 Postorder(top->lchild); Postorder(top->rchild); printf("%c",top->data); } } void getNode(BiTree *t){ if(t){//不空则遍历根左右 a[i]=t->data; i++; getNode(t->lchild); getNode(t->rchild); } }五、实验数据记录和处理 第一题，第二题：
六、实验结果与分析 程序采用递归建立二叉树，递归输出二叉树，叶子节点，即查找位置结点，递归算法写起来比较简单，且容易理解，一目了然，但效率不如非递归算法 可以借助栈，实现3种遍历的非递归算法，除此之外，还可以给出二叉树的层次遍历算法，可以借助队列实现。 我给出先序遍历的非递归算法： // 思路：将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。 void PreOrder(BiTree T){ stack stack; //p是遍历指针 BiTree p = T; //p不为空或者栈不空时循环 while (p || !stack.empty()) { if (p != NULL) { //存入栈中 stack.push(p); //对树中的结点进行操作 operation1(p->data); //遍历左子树 p = p->lchild; } else { //退栈 p = stack.top(); stack.pop(); //访问右子树 p = p->rchild; } } }七、讨论、心得 第三题为非递归改写程序，我试着用教程改写了一下，发现比较复杂，但非递归改写 以上程序，效率会提高很高，我会在考完试后空余时间深入学习这一方法 |
【本文地址】