二叉树的遍历(先序.中序.后序)

实践三：树的应用

1.实验目的要求

通过本实验使学生深刻理解二叉树的性质和存储结构，熟练掌握二叉树的遍历算法。认识哈夫曼树、哈夫曼编码的作用和意义。

实验要求：建一个二叉树并按照前序、中序、后序三种方法遍历此二叉树， 正确调试本程序。

能够建立一个哈夫曼树，并输出哈夫曼编码，正确调程序。写出实验报告。

2.实验主要内容

2.1 对二叉树进行先序、中序、后序递归遍历，中序非递归遍历。

2.2 根据已知的字符及其权值，建立哈夫曼树，并输出哈夫曼编码。

3．实验步骤

2.1实验步骤

● 输入p127二叉链表的定义

● 录入调试p131算法6.4，实现二叉树的构造函数

● 编写二叉树打印函数，可以通过递归算法将二叉树输出为广义表的

形式，以方便观察树的结构。

● 参考算法6.1，实现二叉树的前序、中序和后序的递归遍历算法。

为简化编程，可以将visit函数直接使用printf函数输出结点内容来

代替。

#include

#include

#include

#define OK 1

#define ERROR 0

#define STACK_INIT_SIZE 100

#define STACKINCREMENT 10

typedef char TElemType;

typedef char Status;

// 构造书的结构体

typedef struct BiTNode{

TElemType data;

struct BiTNode *lchild, *rchild;

}BiTNode, *BiTree;

// 构造栈的结构体

typedef BiTree SElemType;

typedef struct{

SElemType *base;

SElemType *top;

int stacksize;

}SqStack;

Status InitStack(SqStack &S){

//构造一个空栈

S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType)); if(!S.base)exit(-2);

S.top = S.base;

S.stacksize = STACK_INIT_SIZE;

return OK;

}

Status StackEmpty(SqStack S){

//若栈S为空栈，则返回TRUE,否则返回FALSE

if(S.top==S.base)

else

}

return 1; return 0;

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(-2); S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; }

*S.top++ = e;

return OK;

}

Status Pop(SqStack &S,SElemType &e){

//若栈不空，则删除S的栈顶元素，用e返回其值并返回OK,否则返回ERROR

if(S.top == S.base) return ERROR;

e = * --S.top;

return OK;

}

Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e)){

//非递归中序遍历二叉树

SqStack S;

BiTNode * p;

InitStack(S);

p = T;

while(p||!StackEmpty(S)){

} else { Pop(S,p); if(!Visit(p->data)) return 0; } p=p->rchild;

return 1;

}

//以下是递归遍历

Status CreateBiTree(BiTree &T){

//构造二叉树T

char ch;

scanf("%c",&ch);

if(ch == ' ') T=NULL;

else{

if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) exit(-2);

}

return 1;

}

Status PreOrderTraverse(BiTree T, Status(* Visit)(TElemType e)){

T->data=ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); //递归先序遍历 if(T){ if(Visit(T->data))

}

if(PreOrderTraverse(T->rchild,Visit)) return 1; return 0; }else return 1;

Status MinOrderTraverse(BiTree T, Status(* Visit)(TElemType e)){

}

Status PostOrderTraverse(BiTree T, Status(* Visit)(TElemType e)){

}

Status PrintElement(TElemType e){

//Visit函数，输出元素 //递归后续遍历 if(T){ if(PostOrderTraverse(T->lchild,Visit)) if(PostOrderTraverse(T->rchild,Visit)) if(Visit(T->data)) return 1; //递归中序遍历 if(T){ if(MinOrderTraverse(T->lchild,Visit)) if(Visit(T->data)) if(MinOrderTraverse(T->rchild,Visit)) return 1; return 0; }else return 1; return 0; }else return 1;

printf("%c ",e);

return 1;

}

//主函数

void main(){

BiTNode* p;

printf("Enter Node:\n");

CreateBiTree(p);

printf("递归先序遍历：");

PreOrderTraverse(p,PrintElement);

printf("\n递归中序遍历：");

MinOrderTraverse(p,PrintElement);

printf("\n递归后序遍历：");

PostOrderTraverse(p,PrintElement);

printf("\n");

printf("\n非递归中序遍历：");

InOrderTraverse(p,PrintElement);

printf("\n");

}

输入：ABCE000DF00G00HJ00K0L00 (“0”表示空格) 输出：