数据结构实验报告—二叉树遍历
- 格式：pdf
- 大小：563.96 KB
- 文档页数：6
- 2 - 1 实 验 环 境 ： vc++6.0 2 实 验 目 的 ： 掌握二叉链表及线索二叉链表的特点及基本运算。 3实 验 原 理 ： （1）二叉树的二叉链表存储结构 typedef struct BiTNode{ TElemType data; struct BiTNode *lchild,*rchild;//左右孩子指针 }BiTNode,*BiTree;
（2）二叉树是另一种树形结构，它的特点是每个结点至多只有两棵子树（即二叉树中不从在度大于2的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。
4实 验 方 案 ： 根据二叉树的知识编写主函数，调用栈的算法以及二叉树的算法，对二叉树进行遍历，验证二叉树算法的正确性，对二叉树的遍历进行实现。
5实 验 过程： 错误1：
将“if(s.top==S.base)”改为“if(S.top==S.base)”； 错误2： - 3 -
将“sElemType &e”改为“SElemType &e”； 6实验结论：
7实 验 总 结 （收 获、体 会 和 建 议 ）： 这次实验让我掌握了二叉树的遍历的基本表示方法和一些代码技巧。
8指导教师评语及成绩： -4 -
评 语 评语等级 优 良 中 及格 不及格 实验方案设计的合理程度 实验结论的记录情况 实验总结情况 实验报告是否按时完成,字迹清楚,文字叙述流畅,层次清晰 成 绩：
指导教师签名： 批阅日期：
附录1：源 程 序 #include #include
#define OK 1 #define ERROR 0 #define OVERFLOW -1 #define TRUE 1 #define FALSE 0
typedef int Status; typedef char TElemType;
typedef struct BiTNode{ TElemType data; struct BiTNode *lchild,*rchild; //左右孩子指针 }BiTNode,*BiTree;
typedef BiTree SElemType; - 5 -
#define STACK_INIT_SIZE 100 //存储空间初始分配量 #define STACKINCREMENT 2 //存储空间分配增量 typedef struct{ SElemType *base; //在栈构造之前和销毁之后，base的值为NULL SElemType *top; //栈顶指针 int stacksize; //当前已分配的存储空间，以元素为单位 }SqStack;
Status InitStack(SqStack &S){ //构造一个空栈S S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); //存储分配失败 S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; }//InitStack
Status GetTop(SqStack S,SElemType &e){ //若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR if(S.top==S.base) return ERROR; e=*(S.top-1); return OK; }//GetTop
Status Push(SqStack &S,SElemType e){ //插入元素e为新的栈顶元素 if(S.top-S.base>=S.stacksize){//栈满，追加存储空间 S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT) *sizeof(SElemType)); if(!S.base) exit(OVERFLOW); //存储分配失败 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e; return OK; }//Push
Status Pop(SqStack &S,SElemType &e){ //若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR if(S.top==S.base) return ERROR; e=*--S.top; return OK; }//Pop - 6 -
Status StackEmpty(SqStack S){ //若栈为空栈，则返回TRUE，否则FALSE if(S.top==S.base) return TRUE; else return FALSE; }//StackEmpty
Status Visit(TElemType e){ //输出元素e的值 printf("%c ",e); return OK; }
Status CreateBiTree(BiTree &T){ //按先序次序输入二叉树结点的值（一个字符），空格字符表示股空树，构造二叉链表表示的二叉树T char ch; scanf("%c",&ch); if(ch==' ') T=NULL; else{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) exit(OVERFLOW); T->data=ch; //生成根结点 CreateBiTree(T->lchild); //构造左子树 CreateBiTree(T->rchild); //构造右子树 } return OK; }//CreateBiTree
Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e)){ //采用二叉链表存储结构，Visit是对数据操作的应用函数， //先序遍历二叉树T的递归算法，对每个数据元素调用函数Visit。 if(T){ if(Visit(T->data)) if(PreOrderTraverse(T->lchild,Visit)) if(PreOrderTraverse(T->rchild,Visit)) return OK; return ERROR; }else return OK; }//PreOrderTraverse
Status InOrderTraverse1(BiTree T,Status(*Visit)(TElemType e)){ //采用二叉链表存储结构，Visit是对数据操作的应用函数， //中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit。 SqStack S;BiTree p; InitStack(S); Push(S,T); //根指针进栈 - 7 -
while(!StackEmpty(S)){ while(GetTop(S,p)&&p) Push(S,p->lchild); //向左走到尽头 Pop(S,p); //空指针退栈 if(!StackEmpty(S)){ //访问结点，向右一步 Pop(S,p); if(!Visit(p->data)) return ERROR; Push(S,p->rchild); }//if }//while return OK; }//InOrderTraverse1
Status InOrderTraverse2(BiTree T,Status(*Visit)(TElemType e)){ //采用二叉链表存储结构，Visit是对数据操作的应用函数， //中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit。 SqStack S;BiTree p; InitStack(S);p=T; while(p||!StackEmpty(S)){ if(p){Push(S,p); p=p->lchild;} //根指针进栈，遍历左子树 else{ //根指针退栈，访问根结点，遍历右子树 Pop(S,p); if(!Visit(p->data)) return ERROR; p=p->rchild; }//else }//while return OK; }//InOrderTraverse2
int main(){ BiTree T; CreateBiTree(T);
PreOrderTraverse(T,Visit); printf("\n");
InOrderTraverse1(T,Visit); printf("\n");
InOrderTraverse2(T,Visit); printf("\n");
return 0; }
