用递归和非递归算法实现二叉树的三种遍历.doc

数据结构与算法实验报告三二叉树的操作与应用一. 实验目的熟悉二叉链表存储结构的特征，掌握二叉树遍历操作及其应用二. 实验要求（题目）说明：以下题目中（一）为全体必做，（二）（三）任选其一完成（一） 从键盘输入二叉树的扩展先序遍历序列，建立二叉树的二叉链表存储结构；（二） 分别用递归和非递归算法实现二叉树的三种遍历；（三） 模拟WindowsXP资源管理器中的目录管理方式,模拟实际创建目录结构,并以二叉链表形式存储,按照凹入表形式打印目录结构（以扩展先序遍历序列输入建立二叉链表结构），如下图所示: (基本要求:限定目录名为单字符;扩展:允许目录名是多字符组合)A B E F C G D三. 分工说明一起编写、探讨流程图，根据流程图分工编写算法，共同讨论修改，最后上机调试修改。四. 概要设计 实现算法，需要链表的抽象数据类型：ADT Binarytree 数据对象：D是具有相同特性的数据元素的集合数据关系R：若D为空集，则R为空集，称binarytree为空二叉树；若D不为空集，则R为H，H是如下二元关系；（1） 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；（2） 若Droot不为空，则存在DrootD1，Dr，且D1Dr为空集；（3） 若D1不为空，则D1中存在唯一的元素x1，H，且存在D1上的关系H1是H的子集；若Dr不为空集，则Dr中存在唯一的元素Xr，H，且存在Dr上的关系Hr为H的子集；H=,H1,Hr; (4) (D1,H1)是一颗符合本定义的二叉树，称为根的左子树，(Dr,Hr)是一颗符合本定义的二叉树，称为根的右子树。基本操作:Creatbitree(&S，definition)初始条件：definition给出二叉树S的定义操作结果：按definition构造二叉树S counter(T) 初始条件：二叉树T已经存在 操作结果：返回二叉树的总的结点数 onecount(T)初始条件：二叉树T已经存在操作结果：返回二叉树单分支的节点数Clearbintree(S)初始条件：二叉树S已经存在操作结果：将二叉树S清为空树Bitreeempty(S)初始条件：二叉树S已经存在操作结果：若S为空二叉树，则返回TRUE，否则返回FALSEBitreedepth(S,&e)初始条件：二叉树S已经存在 操作结果：返回S的深度Parent(S)初始条件：二叉树S已经存在，e是S中的某个结点操作结果：若e是T的非根结点，则返回它的双亲，否则返回空Preordertraverse(S)初始条件：二叉树S已经存在，Visit是对结点操作的应用函数。操作结果：先序遍历S，对每个结点调用函数visit一次且仅一次。一旦visit失败，则操作失败。Inordertraverse (S,&e)初始条件：二叉树S已经存在，Visit是对结点操作的应用函数。 操作结果：中序遍历S，对每个结点调用函数visit一次且仅一次。一旦visit失败，则操作失败。Postordertraverse (&S,e)初始条件：二叉树S已经存在，Visit是对结点操作的应用函数。操作结果：后序遍历S，对每个结点调用函数visit一次且仅一次。一旦visit失败，则操作失败。 ADT Binarytree五、详细设计扩展先序遍历：# include# include#includetypedef struct binarytreechar data;struct binarytree *lchild,*rchild;BiTreeNode,*BiTree;void CreateBiTree(BiTree *bt)char ch;ch=getchar();if(ch=.) *bt=NULL; else *bt=(BiTreeNode *)malloc(sizeof(BiTreeNode); (*bt)-data=ch;CreateBiTree(&(*bt)-lchild);CreateBiTree(&(*bt)-rchild); void PreOder(BiTree root)if(root!=NULL)printf(%4c,root-data);PreOder(root-lchild);PreOder(root-rchild);main()BiTree root;CreateBiTree(&root);printf(先序遍历:n);PreOder(root);递归算法：#include stdio.h#define PR printf#define ERROR 0#define MAX 100 /*=建立各结构体=*/typedef struct node char data; /*数据域*/ struct node *lchild; struct node *rchild; /*结点的左右指针，分别指向结点的左右孩子*/BTNode;typedef BTNode *DataType;typedef struct DataType dataMAX;int top;SeqStack;SeqStack *s; /*=栈的操作=*/SeqStack *createemptystacks() /*创建一个空栈*/SeqStack *s;s=(SeqStack*)malloc(sizeof(SeqStack);s-top=0;return s;int stackemptys(SeqStack *s) /*判栈空*/return s-top=0;int stackfulls(SeqStack *s) /*判栈满*/return s-top=MAX;void pushs(SeqStack *s,DataType x) /*进栈*/if(stackfulls(s)PR(over flown);elses-datas-top+=x;void pops(SeqStack *s) /*退栈*/if(stackemptys(s)PR(underflown);elses-top-;DataType gettops(SeqStack *s) /*栈非空时取栈顶元素*/return s-datas-top-1;/*=建立二叉树=*/BTNode *createbintree() /*输入扩充的先序序列，建立二叉树*/ BTNode *t; char x; scanf(%c,&x); if(x=#) t=NULL; /*读入#，返回空指针 */ else t=(BTNode *)malloc(sizeof(BTNode); /*生成结点*/ t-data=x; t-lchild=createbintree(); /*构造左子树*/ t-rchild=createbintree(); /*构造右子树*/ return(t); /*=树的遍历=*/void preorder(BTNode *t) /*NLR 先序遍历*/ if(t!=NULL) PR( %ct,t-data); /*访问结点*/ preorder(t-lchild); /*中序遍历左子树*/ preorder(t-rchild); /*中序遍历右子树*/ /*=*/void inorder(BTNode *t) /*LNR 中序遍历*/ if(t!=NULL) inorder(t-lchild); /*中序遍历左子树*/ PR( %ct,t-data); /*访问结点*/ inorder(t-rchild); /*中序遍历右子树*/ /*=*/void postorder(BTNode *t) /*LRN 后序遍历*/ if(t!=NULL) postorder(t-lchild); /*后序遍历左子树*/ postorder(t-rchild); /*后序遍历右子树*/ PR( %ct,t-data); /*访问结点*/ /*=主函数=-=*/void main()BTNode *t;int n=0;PR( - 请输入二叉树各元素:(例如 abd#e#cf#g#)n); /例如 abd#e#cf#g# t=createbintree();PR(nn - 1.按先序遍历输出为：n); preorder(t); /*NLR 先序遍历*/ PR(n 按中序遍历输出为：n); inorder(t); /*LNR 中序遍历*/ PR(n 按后序遍历输出为：n); postorder(t); /*LRN 后序遍历*/ # include# include# include# define TRUE 1# define FALSE 0# define Stack_Size 50# define NUM 20typedef struct binarytree /*定义一棵二叉树*/char data;struct binarytree *LChild,*RChild;BiTNode,*BiTree;typedef struct /*定义顺序栈S*/ BiTree dataStack_Size; int top;SeqStack;void CreateBiTree(BiTree &bt) /*利用“扩展先序遍历”创建二叉链表*/ char ch; ch=getchar(); /*调用getchar函数，需要用户输入字符，用户按回车键结束输入*/ if(ch=.) bt=NULL; else bt=(BiTNode *)malloc(sizeof(BiTNode); bt-data=ch; CreateBiTree(bt-LChild); CreateBiTree(bt-RChild); void InitStack(SeqStack &S) /*初始化顺序栈S*/S.top=-1;int IsEmpty(SeqStack S) /*判栈空*/return(S.top=-1? TRUE:FALSE);int Push(SeqStack &S,BiTree &x) /*进栈*/ if(S.top=Stack_Size-1)return(FALSE); S.top+; S.dataS.top=x; return(TRUE);int Pop(SeqStack &S,BiTree &x) /*出栈*/ if(S.top=-1) return(FALSE); else x=S.dataS.top; S.top-; return(TRUE); void PreOrder(BiTree root) /*先序遍历非递归*/ BiTNode *p; SeqStack S; p=root; InitStack(S); while(p!=NULL|!IsEmpty(S) while(p!=NULL) printf(%4c,p-data);Push(S,p);p=p-LChild; if(IsEmpty(S) return; Pop(S,p); p=p-RChild; void InOrder(BiTree root) /*中序遍历非递归*/BiTNode *p;SeqStack S;InitStack(S);p=root;while(p!=NULL | ! IsEmpty(S)if(p!=NULL)Push(S,p);p=p-LChild;elsePop(S,p); printf(%4c,p-data);p=p-RChild;void PostOrder(BiTree root) /*后序遍历非递归*/BiTNode *p,*q;BiTNode *S;int top=0;q=NULL;p=root;S=(BiTNode*)malloc(sizeof(BiTNode*)*NUM); /*NUM为预定义的常数*/while(p!=NULL | top!=0)while(p!=NULL)top+;Stop=p;p=p-LChild;if(top0)p=Stop;if(p-RChild=NULL)|(p-RChild=q)printf(%4c,p-data);q=p;top-;p=NULL;elsep=p-RChild;free(S);void main() /*主函数部分*/loop:BiTree root=NULL;CreateBiTree(root); printf(PreOrder traversal is:n);PreOrder(root);printf(n);printf(InOrder traversal is:n);InOrder(root);printf(n);printf(PostOrder traversal is:n);PostOrder(root);printf(n);printf(Please input a new one:n);char c=getchar();goto loop;实现概要设计中定义的所有的数据类型，对每个操作给出伪码算法或算法流程图。对主程序和其他模块也都需要写出伪码算法或流程图。五、调试分析（主要描述调试过程中碰到的问题及解决方法）初步完成编程的工作时，在输入二叉树的发现只能输入一个字符，而且程序不再进行，最后是自己的不小心将语句char a; scanf(%c,&a);中的%c写为%d导致的。 在编写元素入栈和出栈的时候，程序报如下的错误：语法有错误。，经过检查原来是定义的时候的类型使用错了。六、程序使用说明（通过运行截图再加以必要的文字说明）七、程序测试结果（提供测试数据和运行结果）扩展先序遍历递归算法：非递归算法：1、函数的参数传递有哪几种？ref和out的区别？值传递、引用传递、输出传递、参数数组ref和out的区别： out 关键字会导致参数通过引用来传递，这与 ref 关键字类似。 不同之处在于： （1）ref传进去的参数必须在调用前初始化，而out不必，因为out的函数会先清空变量，即使变量已经赋值。 （2）ref传进去的参数在函数内部可以直接使用，而out不可。 （3）ref传进去的参数在函数内部可以不被修改，但out必须在离开函数体前进行赋值。 （4）ref:当需要通过调用某函数来改变实参变量的值时，使用ref。 out:主要是为了一个方法能返回两个以上的结果。2、虚函数和抽象函数的区别？答：虚函数是有代码的并明确允许子类去覆盖，但子类也可不覆盖，就是说可以直接用，不用重写；抽象函数没有实现代码，即没有函数体，而是由abstract修饰符声明。抽象函数只提供函数名称，具体实现交由继承的派生类，子类继承后必须要重写。3、抽象类和接口的区别？相同点：都不能被直接实例化，都可以通过继承实现其抽象方法。都是面向抽象编程的技术基础，实现了诸多的设计模式。不同点：接口支持多继承；抽象类不能实现多继承。接口只能定义抽象规则；抽象类既可以定义规则，还可能提供已实现的成员。接口是一组行为规范；抽象类是一个不完全的类，着重类族的概念。 接