二叉树遍历算法的实现

二叉树遍历算法的实现

题目：编制二叉树遍历算法的实现的程序

一． 需求分析

1. 本演示程序中，二叉树的数据元素定义为非负的整型（unsigned int）数据，输入-1表示该处没有节点

2. 本演示程序输入二叉树数据均是按先序顺序依次输入

3. 演示程序以用户和计算机对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据和运算结果显示在其后

4. 本实验一共包括三个主要程序，分别是：1）二叉树前序，中序，后序遍历递归算法实现2）二叉树前序中序遍历非递归算法实现3)二叉树层次遍历算法实现

5. 本程序执行命令包括：1）构建二叉树2）二叉树前序递归遍历3）二叉树中序递归遍历4）二叉树后序递归遍历5）二叉树前序非递归遍历6）二叉树中序非递归遍历7）二叉树层次遍历

6. 测试数据

（1）7 8 -1 9 10 -1 -1 -1 6 11 -1 -1 12 13 -1 -1 14 -1 -1

（2）1 -1 -1

（3）7 8 -1 -1 9 -1 -1

二．概要设计

1.为实现二叉树的遍历算法，我们首先给出如下抽象数据类型

1）二叉树的抽象数据类型

ADT BiTree{

数据对象D:D是具有相同特性的数据元素的集合

数据关系R：

若D=Φ，则R=Φ，称BiTree是空二叉树；

若D≠Φ，则R={H}，H是如下二元关系：

(1) 在D中存在唯一的成为根的数据元素root，它在关系H下无前驱；

(2) 若D-{H}≠Φ，则存在D-{root}={D1,Dr}，且D1∩Dr=Φ

(3) 若D1≠Φ，则D1中存在唯一的元素x1，∈H,且存在D1上的

关系H1⊂H；若Dτ≠Φ，则Dr中存在唯一的元素xr，∈

H,且存在Dr上的关系Hr⊂H；H={,,H1,Hr};

(4) (D1,{H1})是符合本定义的二叉树，成为根的左子树，（Dr，{Hr}）是

一颗符合本定义的二叉树，成为根的右字树。

基本操作P：

InitBiTree（&T）；

操作结果：构造空二叉树

DestroyBiTree（&T）

初始条件;二叉树存在

操作结果：销毁二叉树

CreateBiTree（&T,definition）；

初始条件：按definition给出二叉树T的定义

操作结果：按definition构造二叉树

BiTreeEmpty（T）

初始条件：二叉树T存在。

操作结果：若二叉树为空树，返回TRUE，否则返回FALSE

PreOrderTraverse（T,Visit()）；

初始条件：二叉树T存在，Visit是对节点操作的应用函数。

操作结果：先序遍历T，对每个节点调用函数Visit一次且仅一次。一旦Visit（）失败，则操

作失败

InOrderTraverse（T,Visit()）

初始条件:二叉树T存在，Visit是对节点操作的应用函数

操作结果：中序遍历二叉树T，对每个节点调用函数Visit一次且仅一次。一旦visit()失败，

则操作失败

PostOrderTraverse（T,Visit()）；

初始条件：二叉树T存在，Visit是对节点的应用函数

操作结果：后序遍历T，对每个节点调用函数Visit一次且仅一次。一旦Visit（）失败，则操

作失败

LevelOrderTraverse（T,visit()）；

初始条件：二叉树T存在，Visit是对节点操作的应用函数

操作结果：层序遍历T，对每个节点调用函数Visit一次且仅一次。一旦Visit失败，则操作

失败

}//ADT BiTree

2）栈的抽象数据类型

ADT Stack{

数据对象D：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}

数据关系R：R={|ai-1,ai∈D,i=2,…,n}

约定an端为栈顶，a1端为栈底。

基本操作P:

InitStack（&S）

操作结果：构造一个空栈

StackEmpty（S）

初始条件：栈S已存在

操作结果;若栈S为空，则返回TRUE，否则返回FALSE

GetTop（S,&e）

初始条件：栈S已存在且非空

操作结果：用e返回S的栈顶元素

Push（&S,e）

初始条件：栈S已存在

操作结果：插入元素e作为新的栈顶元素

Pop（&S,&e）

初始条件：栈S已存在且非空

操作结果：删除栈S 的栈顶元素,且用e返回其值

}//ADT Stack

3）队列的抽象数据类型

ADT Queue{

数据对象D：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}

数据关系R：R={|ai-1,ai∈D,i=2,…,n}

约定an端为队列尾，a1端为队列头。

基本操作P:

InitQueue（&Q）

操作结果：构造一个空队列Q

QueueEmpty（Q）

初始条件：队列Q已存在

操作结果：若Q为空队列，则返回TRUE，否则FALSE

GetHead（Q,&e）

初始条件：Q为非空队列

操作结果：用e返回Q的队头元素

EnQueue（&Q,e）

初始条件：队列Q已存在

操作结果：插入元素e为Q的新的队尾元素

DeQueue（&Q,&e）

初始条件：Q为非空队列

操作结果：删除Q的队头元素，并用e返回其值

}//ADT Queue

2.本实验包括三个程序，每个程序包括的模块有

1）二叉树遍历的前序中序后序递归算法

a.主程序模块：

void main(){

初始化；

do{

接受命令；

处理命令；

}while（“命令”=“退出”）；

}

b.二叉树模块——实现二叉树的抽象数据类型

c.各模块间调用关系为

主程序模块

二叉树模块

2）二叉树的前序中序遍历非递归算法

a．主程序模块

void main（）

{

初始化；

执行二叉树先序输入；

执行二叉树前序，中序非递归遍历

退出；

}

b．栈单元模块——实现栈的抽象数据类型

c．二叉树模块——实现二叉树的创建与遍历

d．各模块间调用关系为

主程序模块

二叉树单元模块

栈单元模块

3）二叉树层次遍历算法

a．主程序模块

void main(){

初始化；

进行二叉树先序输入

进行二叉树层次遍历；

退出；

b．队列单元模块——实现队列抽象数据类型

c．二叉树单元模块——实现二叉树的创建与遍历

d．各模块间调用关系

主程序模块

二叉树模块

队列单元模块

三．详细设计

本程序的一些预定义

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define OVERFLOW -2

typedef int Status;//Status 是函数的类型，其值是函数结果状态代码 typedef int bool;//bool是布尔类型，其值是TRUE或FALSE

#define STACK_INIT_SIZE 100//栈的初始分配空间

#define STACKINCREMENT 10//栈的空间分配增量

1.元素类型，节点类型定义

1）.二叉树节点类型定义

typedefunsignedint ElemTyppe;//二叉树节点中数据元素类型

struct BiTNode{

ElemType data;

2）栈定义

struct Stack{

struct BiTNode **base;

struct BiTNode **top; int SSize;

}Stack;

3）队列定义

struct QNode{

struct Queue{

struct QNode *front; struct QNode *rear; struct BiTNode *p; struct QNode *next; struct BiTNode *lchild; struct BiTNode *rchild; }BiTree; };//队列的节点 }Queue;//指向队列的队首元素和队尾元素

2.抽象数据类型定义的实现（伪码表示部分实现）

1）二叉树抽象数据类型的实现（除遍历操作外） bool InitBiTree(BiTree &T){

Status CreateBiTree(BiTree &T){

//按先序次序输入二叉树中节点的值（非负整数）-1表示空 scanf(&a); if(a==-1)T=NULL; else{ if(!T=(BiTNode *)malloc(sizeof(BiTNode)))exit(OVERFLOW); T->data=a; CreateBiTree(T->lchild); CreateBiTree(T->rchild); T=NULL; return TRUE; }//InitBiTree

return OK; }//CreaateBiTre

void DestroyBiTree(BiTree &T){

if(!T)

return;

Status BiTreeEmpty(BiTree &T){

2)栈的抽象数据类型部分操作实现（伪代码）

Status InitStack(Stack &S){

Status StackEmpty(Stack S){

Status GetTop(Stack S,BiTNode &e){

if(StackEmpty)//栈为空栈 return error; return OK; e=*(S->top-1); if(S->base==S->top) return TRUE; return FALSE; } return OK; S=(Stack *)malloc(STACK_INIT_SIZE*sizeof(Stack)); if(!S) return error; S->base=(BiTNode **)malloc(sizeof(BiTNode *)); if(!S->base) return error; S->top=S->base; S->SSize=STACK_INIT_SIZE; if(T==NULL) return TRUE; return FALSE; DestroyBiTree(T->lchild); DestroyBiTree(T->rchild); free(T); T=NULL; }//DestroyBiTree }//BiTreeEmpty }//StackEmpty

Status Push(Stack &S,(BiTNode *)e){

if(S->top==S->base+S->SSize){//当前栈已满 S->base=(BiTNode**)malloc((S->SSize+STACKINCREMENT)*sizeof(BiTNode *)));

Status Pop(Stack &S,(BiTNode *)&e){

3）队列抽象数据类型伪代码实现（部分）

Status InitQueue(Queue &Q){

return OK; }//InitQueue if(!Q) return error; Q->rear=Q->front=(QNode *)malloc(sizeof(QNode)); if(!Q->rear) return error; Q->front->p=(BiTNode *)malloc(sizeof(BiTNode)); if(!Q->front->p) return error; Q->rear->next=NULL; Q=(Queue *)malloc(sizeof(Queue)); if(StackEmpty(S)) return error; e=*(S->top-1); S->top--; return OK; *(S->top)=e; S->top++; return OK; }//Push if(!S->base) return error; S->top=S->base+S->SSize; S->SSize+=STACKINCREMENT; }//if }//Pop

Status QueueEmpty(Queue Q){

Status GetHead(Queue Q,(BiTNode *)&p){

Status EnQueue(Queue &Q,(BiTNode *)p){

Status DeQueue(Queue &Q,(BiTNode *)&p){

return OK; }//DeQueue if(QueueEmpty(Q))//队列为空队列 return error; p=Q->front->next->p; v=Q->front->next; Q->front->next=Q->front->next->next; free(v); if(Q->rear!=Q->front->next){//队列中有多个数据元素 Q->rear->next=(QNode *)malloc(sizeof(QNode)); if(!Q->rear->next) return error; Q->rear->next->p=p; Q->rear=Q->rear->next; Q->rear->next=NULL; return OK; if(QueueEmpty(Q))//队列为空 return FALSE; return TRUE; p=Q->front->next->p; if(Q->rear==Q->front ) return TRUE; return FALSE; else }//QueueEmpty }//GetHead }//EnQueue }//if else{//队列中有一个数据元素 p=Q->front->next->p; v=Q->front->next; Q->rear=Q->front; free(v); Q->front->next=NULL; }//else

3.遍历算法的实现

1）前序中序后序遍历递归算法实现

Status PreOrderTraverse(BiTree T,int(* visit)(unsignedint a)){

Status InOrderTraverse(BiTree T,int (* visit)(unsignedint a)){

Status PostOrderTraverse(BiTree T,int(* visit)(unsignedint a)){

2）前序，中序非递归算法的实现（利用栈来实现）

Status PreOrderTraverse(BiTree T,int(*visit)(unsignedint e)){

p=*e=T; InitStack(S); while(*e!=NULL||!StackEmpty(S)){ while(*e!=NULL){ visit((*e)->data); Push(S,*e); *e=(*e)->lchild; if(T){ PostOrderTraverse(T->lchild,visit); PostOrderTraverse(T->rchild,visit); (* visit)(T->data); if(T){ InOrderTraverse(T->lchild,visit); (* visit)(T->data); InOrderTraverse(T->rchild,visit); if(T){ visit(T->data); PreOrderTraverse(T->lchild,visit); PreOrderTraverse(T->rchild,visit); }//if return OK; }//PreOrderTraverse }//if return OK; }//InOrderTraverse }//if return OK; }//PostOrdertraverse }//while if(!StackEmpty(S)){ S=Pop(S,e); *e=(*e)->rchild; }//if }//while

return TRUE; }//PreOrderTraverse

Status InOrderTraverse(BiTree T,int(*visit)(unsignedint e)){

3)二叉树层次遍历实现（用队列）

Status LevelOrderTraverse(BiTree T,int(*visit)(unsignedint a)){

4.主函数及其他函数

1）遍历用函数

int Print(unsignedint e){

printf("%u ",e); return 1; InitQueue(Q); EnQueue(Q,T); while(!QueueEmpty(Q)){ if(GetHead(Q,p)&&(*p)!=NULL){ DeQueue(Q,p); EnQueue(Q,(*p)->lchild); EnQueue(Q,(*p)->rchild); visit((*p)->data); p=root; S=InitStack();Push(S,p); while(!StackEmpty(S)){ while(GetTop(S,e)&&(*e)) Push(S,(*e)->lchild);//向左走到尽头 Pop(S,e);//空指针退栈 if(!StackEmpty(S)){//访问节点，向右一步 Pop(S,e); if(!visit((*e)->data)) return FALSE; Push(S,(*e)->rchild); }//if }//while return TRUE; }//InorderTraverse }//if elseif((*p)==NULL){ DeQueue(Q,p);//空?指?针?退ª?出?队¨列¢D }//else if }//while return TRUE; }//LevelOrderTraverse

}

2）先序中序后序递归算法中菜单程序和命令读入执行程序和主程序

int Menu(){

void MenuFunction(int choice,BiTNode &T){

switch(choice){ case 1: system("cls"); break; printf("请按先序输入各节点数据（数据类型为非负整型，输入-1表示该处CreatBiTree(T); break; if(!BiTreeEmpty(T)) DestroyBiTree(T); printf("此树为空树\n"); else break; a=BiTreeEmpty(T); if(a==1) printf("此树为空\n"); printf("此树非空\n"); else break; scanf("%d",&c); return c; printf("\n"); printf("1.清屏，并显示功能菜单\n"); printf("2.构造一个二叉树\n"); printf("3.销毁二叉树\n"); printf("4.判断二叉树是否为空?\n"); printf("5.采用前序递归算法遍历并打印二叉树节点数据\n"); printf("6.采用中序递归算法遍历并打印二叉树节点数据\n"); printf("7.采用后序递归算法遍历并打印二叉树节点数据\n"); printf("8.退出程序\n"); printf("请输入您的选择\n"); int c; }//Menu case 2: 无节点指针指向NULL\n"); case 3: case 4:

PreOrderTraverse(T,Print); break; InOrderTraverse(T,Print); break; PostOrderTraverse(T,Print); break; exit(0); break; printf("输入错误\n"); break; case 6: case 7: case 8: default: }//switch }//MenuFunction

void main(){

3）先序中序非递归算法主函数

void main(){

if(!a){ printf("遍历失败\n"); exit(0); InitBiTree(T); CreateBiTree(T); printf("中序非递归算法遍历结果是:\n"); a=InOrderTraverse(T,Print); printf("请按先序顺序输入数据，注意事项有：\n"); printf("1.数据元素为非负整数\n"); printf("2.当输入-1时表示该处无节点\n"); InitBiTree(T);//创建一个空的二叉树 printf("系统已自动创建一个空的二叉树\n"); do{ choice=Menu(); MenuFunction(choice,T); printf("是否返回主菜单(Y\\N)\n"); scanf(" %c",&c); }while(c=='Y'||c=='y'); exit(0); }//main

printf("\n"); printf("前序遍历非递归算法是\n"); a=PreOrderTraverse(T,Print); if(!a){ printf("遍历失败\n"); exit(0); }//if }//main

4）层次遍历主函数为

void main(){

5.函数调用关系为

1)先序中序后序递归算法调用关系为（其PreOrder,InOrder,PostOrder表示

PreOrderTraverse，InOrderTraverse，PostOrderTraverse） if(!a){ printf("遍历失败\n"); exit(0); InitBiTree(T); CreateBiTree(T); printf("层次遍历算法遍历结果是:\n"); a=LevelOrderTraverse(T,Print); printf("请按先序顺序输入数据，注意事项有：\n"); printf("1.数据元素为非负整数\n"); printf("2.当输入-1时表示该处无节点\n"); }//if printf("\n"); }//main

main()

2）先序中序非递归算法函数调用关系为

InitBiTree CreateBiTree PreOrder InOrder

InitStack Push Pop

3)层次遍历函数调用关系为

main

InitBiTree CreateBiTree LevelOrderTraverse

InitQueue EnQueue DeQueue GetHead

四．调试分析

1.本程序在实现中序前序的非递归算法时，对于入栈元素的类型一直未明确，导致编译时多处位置出现赋值符两边类型不匹配或者函数参数类型不匹配。

2．本程序在建队列时因为有多处指针，导致部分指针未用malloc开空间，导致程序运行时崩溃。

3.本程序在实现队首元素的出队列操作时，采用的是链式存储模式，但判断队中是否有且仅有一个元素时，却采用了表达式if(Q->rear==Q->front+1)即错用成了顺序，导致程序运行时崩溃。

4.本程序分了多个模块，使函数的封装性较好，同时良好的风格也使得程序容易阅读与修改，调试时也容易找出错误所在。

5．本程序采用多种方式对二叉树进行遍历操作，对二叉树遍历这一重要操作有了更深刻的认识，同时程序中多处采用递归，栈操作，队列操作，使得对递归，栈，队列的掌握也更加熟练。

五．用户手册

1.本程序运行环境为DOS环境，执行文件为“二叉树遍历的前序中序后序递归算法.exe”,”二叉树层次遍历.exe”，”二叉树前序中序遍历非递归算法.exe”

2.本程序的二叉树的节点数据类型为unsigned int型，输入时输入-1表示空节点，且输入时按照先序输入

六．测试结果

七．附录

二叉树遍历的先序中序后序递归算法.cpp

二叉树层次遍历.cpp

二叉树前序中序遍历非递归算法.cpp