连云港网站开发公司,网站后台登陆密码,dw怎么做网站首页,如何删除wordpress文件夹广州大学学生实验报告 开课实验室#xff1a;计算机科学与工程实验#xff08;电子楼418A#xff09; 2019年5月13日 学院 计算机科学与教育软件学院 年级、专业、班 计算机科学与技术172班 姓名 学号 17061 实验课程名称 数据结构实验 成绩 实验项目名…广州大学学生实验报告 开课实验室计算机科学与工程实验电子楼418A 2019年5月13日 学院 计算机科学与教育软件学院 年级、专业、班 计算机科学与技术172班 姓名 学号 17061 实验课程名称 数据结构实验 成绩 实验项目名称 实验二 树和二叉树的实现 指导老师 一、实验目的 理解并运用树的操作方法 二、使用仪器、器材 微机一台 操作系统Win10 编程软件C 三、实验内容及原理 自己选择存储方法、自己设计输入输出方式在实验报告中清晰说明。 输入一棵多元树进行多种遍历树的高度设空树高度为-1不小于3包含儿子数为0、1、2、3的结点。 输入一棵二叉树进行多种遍历。树的高度设空树高度为-1不小于4包含了儿子数为0、1、2的结点。选做二叉树的总结点或叶片数目的统计。 3.补充下列程序使该程序能正确运行。 题目要求由先序遍历序列建立二叉树的515二叉链表中序线索化二叉树并找出结点的前驱和后继。 实验过程原始数据记录1、输入一棵多元树进行多种遍历 树的高度设空树高度为-1不小于3包含儿子数为0、1、2、3的结点。 Tree.h #pragma once #include stdio.h #include malloc.h #define MaxSize 100 typedef struct tnode { char data; //节点的值 struct tnode *hp; //指向兄弟 struct tnode *vp; //指向孩子节点 } TSBNode; //孩子兄弟链存储结构类型 TSBNode *CreateTree(char *str); //由str建立孩子兄弟链存储结构 void DispTree(TSBNode *t); //输出孩子兄弟链存储结构 void DestroryTree(TSBNode *t); //销毁树t int TreeHeight2(TSBNode *t); void PreOrder(TSBNode *b); //先序遍历的递归算法 void PostOrder(TSBNode *b); //后序遍历的递归算法 void LevelOrderTraverse(TSBNode *b);//层次遍历 tree.cpp #includepch.h #include tree.h TSBNode * CreateTree(char * str) { struct { TSBNode *nodep; //节点指针 int num; //孩子个数 } St[MaxSize]; //顺序栈 int top -1; //栈顶指针 int i 0, j; char ch str[i]; TSBNode *t NULL, *pNULL, *q; while (ch ! \0) { switch (ch) { case (: top; St[top].nodep p; St[top].num 0; //当前节点p进栈 break; case ):top--; break; //退栈 case ,:St[top].num; break; //栈顶节点增加一个孩子 default: p (TSBNode *)malloc(sizeof(TSBNode)); p-data ch; //建立一个节点p存放ch p-hp p-vp NULL; if (t NULL) //原为空树 t p; else //将其作为栈顶节点的一个孩子 { if (St[top].num 0) //第一个孩子用vp指向它 St[top].nodep-vp p; else //其他孩子用栈顶节点的孩子节点的hp指向它 { q St[top].nodep-vp; for (j 1; j St[top].num; j) q q-hp; q-hp p; } } break; } i; ch str[i]; } return t; } void DispTree(TSBNode * t) { TSBNode *p; if (t ! NULL) { printf(%c, t-data); if (t-vp ! NULL) //有孩子时输出一个( { printf((); p t-vp; //p指向节点t的第一个孩子 while (p ! NULL) { DispTree(p); p p-hp; if (p ! NULL) printf(,); } printf()); //输出一个) } } } void DestroryTree(TSBNode * t) { if (t ! NULL) { DestroryTree(t-vp); DestroryTree(t-hp); free(t); //释放根节点 } } int TreeHeight2(TSBNode * t) { TSBNode *p; int h, maxh 0; if (t NULL) return 0; //空树返回0 else { p t-vp; //指向第1个孩子节点 while (p ! NULL) //扫描t的所有子树 { h TreeHeight2(p); //求出p子树的高度 if (maxh h) maxh h; //求所有子树的最大高度 p p-hp; //继续处理t的其他子树 } return(maxh 1); //返回maxh1 } } void PreOrder(TSBNode * b) { //st1为处理整个树的栈st2为处理其兄弟节点的栈 TSBNode *st1[100], *st2[100], *p NULL; int top1 -1, top2 -1; if (b ! NULL) { p b; top1; st1[top1] p; //先将根节点进栈 while (top1 0) //栈不空时循环 { p st1[top1]; top1--; //退栈 printf(%c , p-data); //打印输出 if (p-vp) //若该节点存在兄弟节点 { p p-vp; while (p ! NULL) //将兄弟节点依次进栈 { top2; st2[top2] p; p p-hp; } while (top2 0) //将兄弟节点依次退栈st2并将退栈的元素放到st1中 { top1; st1[top1] st2[top2]; top2--; } } } } } void PostOrder(TSBNode * b) { if (b NULL) return; TSBNode *p b-vp; PostOrder(p); //递归打印孩子节点 if (p ! NULL) p p-hp; while (p) //该节点不空则递归打印兄弟节点 { PostOrder(p); p p-hp; } printf(%c , b-data); //打印输出 } } void LevelOrderTraverse(TSBNode * b) { } Main.cpp #include pch.h #include iostream #includetree.h int main() { TSBNode *t; t CreateTree(A(B(E,F),C(G(J)),D(H,I(K,L,M)))); printf(t:); DispTree(t); printf(\n树t的高度:%d\n, TreeHeight2(t)); printf(\n树t的先根遍历结果为:); PreOrder(t); printf(\n); printf(\n树t的后根遍历结果为:); PostOrder(t); DestroryTree(t); return 1; } 2、输入一棵二叉树进行多种遍历。 树的高度设空树高度为-1不小于4包含了儿子数为0、1、2的结点。选做二叉树的总结点或叶片数目的统计。 Btree.h #pragma once #includepch.h #include stdio.h #include malloc.h #define MaxSize 100 typedef char ElemType; typedef struct node { ElemType data; //数据元素 struct node *lchild; //指向左孩子节点 struct node *rchild; //指向右孩子节点 } BTNode; void CreateBTree(BTNode * b, char *str); //创建二叉树 void DestroyBTree(BTNode *b); BTNode *FindNode(BTNode *b, ElemType x); BTNode *LchildNode(BTNode *p); BTNode *RchildNode(BTNode *p); int BTHeight(BTNode *b); void DispBTree(BTNode *b);//输出二叉树 //二叉树的遍历算法 void PreOrder1(BTNode *b);//先序遍历非递归算法1 void PreOrder2(BTNode *b);//先序遍历非递归算法2 void InOrder1(BTNode *b);//中序遍历非递归算法1 void PostOrder1(BTNode *b);//后序遍历非递归算法1 //有关栈的操作 typedef struct { BTNode *data[MaxSize]; //存放栈中的数据元素 int top; //存放栈顶指针即栈顶元素在data数组中的下标 } SqStack; //顺序栈类型 void InitStack(SqStack *s); //初始化栈 void DestroyStack(SqStack *s); //销毁栈 bool StackEmpty(SqStack *s); //判断栈是否为空 bool Push(SqStack *s, BTNode *e); //进栈 bool Pop(SqStack *s, BTNode *e); //出栈 bool GetTop(SqStack *s, BTNode *e); //取栈顶元素 Btree.cpp #includepch.h #include btree.h void CreateBTree(BTNode * b, char * str) //创建二叉树 { BTNode *St[MaxSize], *p NULL; int top -1, k, j 0; char ch; b NULL; //建立的二叉树初始时为空 ch str[j]; while (ch ! \0) //str未扫描完时循环 { switch (ch) { case (:top; St[top] p; k 1; break; //为左孩子节点 case ):top--; break; case ,:k 2; break; //为孩子节点右节点 default:p (BTNode *)malloc(sizeof(BTNode)); p-data ch; p-lchild p-rchild NULL; if (b NULL) //*p为二叉树的根节点 b p; else //已建立二叉树根节点 { switch (k) { case 1:St[top]-lchild p; break; case 2:St[top]-rchild p; break; } } } j; ch str[j]; } } void DestroyBTree(BTNode * b) { if (b ! NULL) { DestroyBTree(b-lchild); DestroyBTree(b-rchild); free(b); } } BTNode * FindNode(BTNode * b, ElemType x) { BTNode *p; if (b NULL) return NULL; else if (b-data x) return b; else { p FindNode(b-lchild, x); if (p ! NULL) return p; else return FindNode(b-rchild, x); } } BTNode * LchildNode(BTNode * p) { return p-lchild; } BTNode * RchildNode(BTNode * p) { return p-rchild; } int BTHeight(BTNode * b) { int lchildh, rchildh; if (b NULL) return(0); //空树的高度为0 else { lchildh BTHeight(b-lchild); //求左子树的高度为lchildh rchildh BTHeight(b-rchild); //求右子树的高度为rchildh return (lchildh rchildh) ? (lchildh 1) : (rchildh 1); } } void DispBTree(BTNode * b) { if (b ! NULL) { printf(%c, b-data); if (b-lchild ! NULL || b-rchild ! NULL) { printf((); //有孩子节点时才输出( DispBTree(b-lchild); //递归处理左子树 if (b-rchild ! NULL) printf(,); //有右孩子节点时才输出, DispBTree(b-rchild); //递归处理右子树 printf()); //有孩子节点时才输出) } } } void PreOrder1(BTNode * b) { BTNode *p; SqStack *st; //定义一个顺序栈指针st InitStack(st); //初始化栈st Push(st, b); //根节点进栈 while (!StackEmpty(st)) //栈不为空时循环 { Pop(st, p); //退栈节点p并访问它 printf(%c , p-data); //访问节点p if (p-rchild ! NULL) //有右孩子时将其进栈 Push(st, p-rchild); if (p-lchild ! NULL) //有左孩子时将其进栈 Push(st, p-lchild); } printf(\n); DestroyStack(st); //销毁栈 } void PreOrder2(BTNode * b) { BTNode *p; SqStack *st; //定义一个顺序栈指针st InitStack(st); //初始化栈st p b; while (!StackEmpty(st) || p ! NULL) { while (p ! NULL) //访问节点p及其所有左下节点并进栈 { printf(%c , p-data); //访问节点p Push(st, p); //节点p进栈 p p-lchild; //移动到左孩子 } if (!StackEmpty(st)) //若栈不空 { Pop(st, p); //出栈节点p p p-rchild; //转向处理其右子树 } } printf(\n); DestroyStack(st); //销毁栈 } void InOrder1(BTNode * b) { BTNode *p; SqStack *st; //定义一个顺序栈指针st InitStack(st); //初始化栈st if (b ! NULL) { p b; while (!StackEmpty(st) || p ! NULL) { while (p ! NULL) //扫描节点p的所有左下节点并进栈 { Push(st, p); //节点p进栈 p p-lchild; //移动到左孩子 } if (!StackEmpty(st)) //若栈不空 { Pop(st, p); //出栈节点p printf(%c , p-data); //访问节点p p p-rchild; //转向处理其右子树 } } printf(\n); } DestroyStack(st); //销毁栈 } void PostOrder1(BTNode * b) { BTNode *p, *r; bool flag; SqStack *st; //定义一个顺序栈指针st InitStack(st); //初始化栈st p b; do { while (p ! NULL) //扫描节点p的所有左下节点并进栈 { Push(st, p); //节点p进栈 p p-lchild; //移动到左孩子 } r NULL; //r指向刚刚访问的节点初始时为空 flag true; //flag为真表示正在处理栈顶节点 while (!StackEmpty(st) flag) { GetTop(st, p); //取出当前的栈顶节点p if (p-rchild r) //若节点p的右孩子为空或者为刚刚访问过的节点 { printf(%c , p-data); //访问节点p Pop(st, p); r p; //r指向刚访问过的节点 } else { p p-rchild; //转向处理其右子树 flag false; //表示当前不是处理栈顶节点 } } } while (!StackEmpty(st)); //栈不空循环 printf(\n); DestroyStack(st); //销毁栈 } void InitStack(SqStack * s) { s (SqStack *)malloc(sizeof(SqStack));//分配一个是顺序栈空间首地址存放在s中 s-top -1; //栈顶指针置为-1 } void DestroyStack(SqStack *s) //销毁栈 { free(s); } bool StackEmpty(SqStack * s) { return(s-top -1); } bool Push(SqStack * s, BTNode * e) { if (s-top MaxSize - 1) //栈满的情况即栈上溢出 return false; s-top; //栈顶指针增1 s-data[s-top] e; //元素e放在栈顶指针处 return true; } bool Pop(SqStack * s, BTNode * e) { if (s-top -1) //栈为空的情况即栈下溢出 return false; e s-data[s-top]; //取栈顶指针元素的元素 s-top--; //栈顶指针减1 return true; } bool GetTop(SqStack * s, BTNode * e) { if (s-top -1) //栈为空的情况即栈下溢出 return false; e s-data[s-top]; //取栈顶元素 return true; } Main.cpp int main() { BTNode *b; CreateBTree(b, A(B(D(G,H(,J)),E(,I)),C(,F))); DispBTree(b); printf(\n); printf(先序遍历序列1:); PreOrder1(b); printf(先序遍历序列2:); PreOrder2(b); printf(中序遍历序列:); InOrder1(b); printf(后序遍历序列:); PostOrder1(b); DestroyBTree(b); printf(\n); } 3、补充下列程序使该程序能正确运行。 步骤一新建工程新建一个头文件,命名为 thread.h一个源文件命名为thread.cpp 步骤二 在thread.h中编辑代码代码如下 #include iostream using namespace std; typedef char DataType; typedef struct Node { DataType data; int Ltag; int Rtag; __struct Node__ *LChild; /*填空1、指针域的数据类型*/ __struct Node__ *RChild; }BTNode; BTNode *pre; void CreateBiTree(BTNode *root, DataType Array[]) ; //创建初始化二叉树 void Inthread(BTNode *root); //实现中序线索二叉树 BTNode * InPre(BTNode *p); //求中序线索二叉树结点的前驱 BTNode * InNext(BTNode * p) ; //求中序线索二叉树结点的后驱 在Thread.cpp中编辑代码代码如下 #include thread.h /*11、填空请填空包含头文件*/ void CreateBiTree(BTNode *root, DataType Array[]) { static int count0; //静态变量count char itemArray[count];//读取Array[]数组中的第count个元素 count; if(item #) //如果读入#字符创建空树 { root NULL; return ;} else { root __ (BTNode *)malloc(sizeof(BTNode))__;/*填空3生成一个新结点*/ ___ root-data___ item; /*填空4将ch做为新结点的数据域的值*/ root-Ltag0; root-Rtag0; __ CreateBiTree(root-LChild, Array)_; /*填空5: 递归的方法生成左子树注意实参的表示方法*/ __ CreateBiTree(root-RChild, Array)_; /*填空6: 递归的方法生成右子树注意实参的表示方法*/ } } void Inthread(BTNode *root) /* 对root所指的二叉树进行中序线索化其中pre始终指向刚访问过的结点其初值为NULL */ { if (root!NULL) { Inthread(root-LChild); /* 线索化左子树 */ if (root-LChildNULL) { root-Ltag___ 1__; __ root-LChild_pre; /*填空7-8置前驱线索 */ } if (pre!NULL pre-RChildNULL) /* 填空9-10置后继线索 */ { pre-Rtag__ 1___; __ root-RChild __root; } preroot; Inthread(root-RChild); /*线索化右子树*/ } } /* 在中序线索二叉树中查找p的中序前驱, 并用pre指针返回结果 */ BTNode * InPre(BTNode *p) { BTNode *q; if(p-Ltag1) pre __p-LChild__; /*填空13直接利用线索找前驱*/ else { /* 填空14-15在p的左子树中查找最右下端结点 */ for(q p-LChild;q-Rtag__0__;qq-_ RChild __); preq; } return(pre); } /*在中序线索二叉树中查找p的中序后继结点并用next指针返回结果*/ BTNode * InNext(BTNode * p) { BTNode *Next; BTNode *q; if (p-Rtag1) Next p-RChild; /*填空16直接利用线索*/ else { /*填空17-18 在p的右子树中查找最左下端结点*/ for(qp-RChild; q-Ltag___0___ ;qq-__ LChild ___); Nextq; } return(Next); } void main() { BTNode *root,*q; DataType A[]AB#CD##E##F#G##;//以#补充空分支后的某个遍历序列 CreateBiTree(root,A);//以先序遍历序列建立二叉树 pre NULL; Inthread(root); q InPre(root); /*找根结点的前驱大家试找其它结点的前驱*/ coutroot-data的前驱为q-dataendl; q InNext(root); /*找根结点的后驱大家试找其它结点的后驱*/ coutroot-data的后继为q-dataendl; }; 实验结果及分析1.输入一棵多元树进行多种遍历 多元树存储结构为孩子兄弟存储结构遍历算法:先跟遍历采用非递归算法后根遍历采用递归算法。 2.输入一棵二叉树进行多种遍历。 遍历算法均为非递归算法 3.补充下列程序使该程序能正确运行。
