树和二叉树的实验报告

《数据结构》

实验报告

题目： 树和二叉树

树和二叉树的实验报告

一、 用二叉树来表示代数表达式

（一）需求分析

输入一个正确的代数表达式，包括数字和用字母表示的数，运算符号+ - * / ^ =及括号。系统根据输入的表达式建立二叉树，按照先括号里面的后括号外面的，先乘后除的原则，每个节点里放一个数字或一个字母或一个操作符，括号不放在节点里。分别先序遍历，中序遍历，后序遍历此二叉树，并输出表达式的前缀式，中缀式和后缀式。 （二）系统设计

1. 本程序中用到的所有抽象数据类型的定义；

typedef struct BiNode //二叉树的存储类型

{

char s[20];

struct BiNode *lchild,*rchild; }BiTNode,*BiTree;

2. 主程序的流程以及各程序模块之间的层次调用关系，函数的调用关系图：

3．列出各个功能模块的主要功能及输入输出参数 void push(char cc)

初始条件：输入表达式中的某个符号 操作结果：将输入的字符存入buf数组中去 BiTree Create_RTree()

初始条件：给出二叉树的定义表达式

操作结果：构造二叉树的右子树，即存储表达式等号右侧的字符组 BiTree Create_RootTree()

树和二叉树的实验报告

初始条件：给出二叉树的定义表达式

操作结果：构造存储输入表达式的二叉树，其中左子树存储‘X’，根节点存储‘：=’ void PreOrderTraverse(BiTree T) 初始条件：二叉树T存在

操作结果：先序遍历T，对每个节点调用函数Visit一次且仅一次 void InOrderTraverse(BiTree T) 初始条件：二叉树T存在

操作结果：中序遍历T，对每个节点调用函数Visit一次且仅一次 void PostOrderTraverse(BiTree T) 初始条件：二叉树T存在

操作结果：后序遍历T，对每个节点调用函数Visit一次且仅一次 int main()

主函数，调用各方法，操作成功后返回0 （三）调试分析

调试过程中还是出现了一些拼写错误，经检查后都能及时修正。有些是语法设计上的小错误，比如一些参变量的初始值设置错误，使得程序调试出错。还有操作符优先级设计不够合理，在输出遍历表达式结果时有错误。在小组讨论分析后纠正了这些结果，并尽量改进了算法的性能，减小时间复杂度。

有输入表达式建立二叉树的时间复杂度为O(n),先序遍历和中序遍历及后序遍历的时间复杂度都为O(n). （四）测试结果

X：=(-b+(b^2-4*a*c)^0.5)/(2*a) （五）用户手册

打开界面后，根据提示，输入代数表达式，包括包括数字和用字母表示的数，运算符号+ - * / ^ =及括号。输入完毕回车后系统将显示表达式的前缀式，中缀式，后缀式。 （六）附录 源程序：

#include<stdio.h> #include<stdlib.h> #include <string.h>

树和二叉树的实验报告

typedef struct BiNode {

char ch,bt[1024]; int len=0;

void push(char c) { }

BiTree Create_RTree() {

BiTree T,Q,S; char *p; while(ch!=EOF) {

ch=getchar(); if(ch=='\n') { }

if(len>0) { }

return NULL;

//输入结束，堆栈中为右节点的值

if((Q=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)

return NULL;

memset(Q->s,0x00,sizeof(Q->s)); Q->lchild=NULL; Q->rchild=NULL; memcpy(Q->s,bt,len); len =0; return Q;

if (len<1024)

bt[len++] = c; char s[20];

struct BiNode *lchild,*rchild;

}BiTNode,*BiTree;

else if (ch == '(') {

if((Q=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)

return NULL;

memset(Q->s,0x00,sizeof(Q->s)); Q->rchild = NULL;

树和二叉树的实验报告

}

ch=getchar(); if(ch=='\n') return Q; Q->s[0]=ch;

Q->rchild=Create_RTree(); return Q;

else if(ch ==')') {

}

if(len>0) { }

return NULL;

if((Q=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)

return NULL;

memset(Q->s,0x00,sizeof(Q->s)); Q->lchild=NULL; Q->rchild=NULL; memcpy(Q->s,bt,len); len=0; return Q;

else if(ch =='+'||ch=='-'||ch =='*'||ch =='/'||ch =='^') {

if((T=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)

return NULL; return NULL;

if((Q=(BiTNode*)malloc(sizeof(BiTNode)))==NULL) memset(Q->s,0x00,sizeof(Q->s)); memset(T->s,0x00,sizeof(T->s)); T->lchild=NULL; T->rchild=NULL; if(len==0) {

if(ch =='+'||ch =='-') {

// 只有+-号前面可以不是数字,此时左节点为空 T->s[0]=ch;

if((S=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)

return NULL;

memset(S->s,0x00,sizeof(S->s)); S->lchild=NULL; S->rchild=NULL; p=S->s;

树和二叉树的实验报告

}

} else

{ }

T->rchild=S;

ch=getchar();

if(ch=='+'||ch =='-'||ch =='*'||ch =='/'||ch=='^')

break; *p++=ch;

return NULL;

else { }

BiTNode *Create_RootTree() {

BiTree Q,T;

while((ch=getchar())!= EOF) {

if (ch=='\n') { }

return NULL;

}

return NULL;

}

Q->lchild=T; Q->s[0]=ch;

if((Q->rchild = Create_RTree()) == NULL) else

return Q; return NULL; //堆栈中为左节点值 memcpy(T->s,bt,len); len =0;

} else

push(ch);

else if(ch==':') //构造根节点：= {

ch=getchar();

if(ch!='=') return NULL;

if((Q=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)

树和二叉树的实验报告

}

memset(Q->s,0x00,sizeof(Q->s)); memcpy(Q->s,bt,len); len =0;

Q->lchild = NULL; Q->rchild = NULL;

if((T=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)

return NULL; T->lchild = Q;

memset(T->s,0x00,sizeof(T->s)); memcpy(T->s,":=",2);

//继续处理:=后面的数据，作为根节点的右节点 if((T->rchild=Create_RTree())==NULL)

return NULL; return T;

else { }

void PreOrderTraverse(BiTree T) { }

void InOrderTraverse(BiTree T) {

if(T) { } else

InOrderTraverse(T->lchild); printf("%s ",T->s); InOrderTraverse(T->rchild); if(T) { } else

return;

printf("%s ",T->s);

PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); }

return NULL;

}

push(ch);

树和二叉树的实验报告

}

}

return;

void PostOrderTraverse(BiTree T) { } int main() { }

printf("请输入一个中缀表达式：\n"); BiTree T=NULL;

if((T=Create_RootTree())==NULL)

return 0;

printf("先序遍历："); PreOrderTraverse(T); printf("\n"); printf("中序遍历："); InOrderTraverse(T); printf("\n");

printf("后序遍历："); PostOrderTraverse(T); printf("\n"); return 0; if(T) { } else

return;

PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); printf("%s ",T->s);

测试数据结果：

X：=(-b+(b^2-4*a*c)^0.5)/(2*a)

树和二叉树的实验报告

二、求二叉树中从根结点到叶子节点的路径

（一）需求分析

以无歧义的陈述说明程序设计的任务，强调程序要做什么。明确规定： （1）．输入的形式和输入值的范围； （2） 输出的形式 （3） 程序所能达到的功能

（4） 测试数据：包括正确的输入及其输出结果，含有错误的输入及其输出结果。 （二）系统设计

1． 说明本程序中用到的所有抽象数据类型的定义；

typedef char ElemType; typedef struct node { ElemType data;

struct node *lchild; struct node *rchild; }BiTNode;

2． 主程序的流程以及各程序模块之间的层次调用关系，画出函数的调用关系图。

3． 列出各个功能模块的主要功能及输入输出参数。

（三）调试分析 内容包括：

（1）．调试过程中遇到的问题是如何解决的及对设计与实现的回顾讨论与分析。 （2） 算法的时间复杂度分析（包括基本操作和其他算法）和改进设想；

树和二叉树的实验报告

（3） 经验与体会等。 （四）测试结果

（五）用户手册

说明如何使用你编写的程序，详细列出每一步操作步骤。 （六）附录

#include <iostream> #define NULL 0 #define Max 50 using namespace std; typedef struct node { char data; struct node *lc,*rc; }btnode;

void creattree(btnode *&b) {//递归创建二叉树

char i;

cin>>i;

if(i=='#')

b=NULL;

else{

b=(btnode *)malloc(sizeof(btnode));

b->data=i; creattree(*&b->lc); creattree(*&b->rc);

树和二叉树的实验报告

}

}

void findleafnode(btnode *b) {//找出所有叶子结点 }

btnode *st[Max]; int front,rear=-1;

void allpath(btnode *b){ //从叶子结点到根结点的路径

if(b!=NULL){

rear++; if(b!=NULL){ }

if(b->lc==NULL&&b->rc==NULL)

cout<<b->data<<' ';

else{ }

findleafnode(b->lc); findleafnode(b->rc);

st[rear]=b;//当前结点入栈

if(b->lc==NULL&&b->rc==NULL){ //当b为叶子结点时

front=rear;

while(front>=0){//输出从根节点到叶子结点的路径

cout<<st[front]->data<<' ';

front--;

}

cout<<endl;

rear--; //栈尾指针退一步

//重设栈头指针

树和二叉树的实验报告

}

else{

allpath(b->lc);

allpath(b->rc); rear--; }

void main(){

btnode *b;

cout<<"请以先序构造一棵树，无结点时以‘#’代替"; cout<<endl; } }

creattree(b);

cout<<"叶子结点为："<<endl; findleafnode(b); cout<<endl;

cout<<"从所有叶子结点到根结点的路径为："<<endl;

allpath(b); }

cout<<"以上路径中第一条最长路径是："<<endl;

树和二叉树的实验报告