二叉树的遍历实验报告

一、需求分析

在二叉树的应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理，这就是二叉树的遍历问题。

对二叉树的数据结构进行定义，建立一棵二叉树，然后进行各种实验操作。

二叉树是一个非线性结构，遍历时要先明确遍历的规则，先访问根结点还时先访问子树，然后先访问左子树还是先访问有右子树，这些要事先定好，因为采用不同的遍历规则会产生不同的结果。本次实验要实现先序、中序、后序三种遍历。

基于二叉树的递归定义，以及遍历规则，本次实验也采用的是先序遍历的规则进行建树的以及用递归的方式进行二叉树的遍历。

二、系统总框图

                         

三、各模块设计分析

   （1）建立二叉树结构

    建立二叉树时，要先明确是按哪一种遍历规则输入，该二叉树是按你所输入的遍历规则来建立的。本实验用的是先序遍历的规则进行建树。

二叉树用链表存储来实现，因此要先定义一个二叉树链表存储结构。因此要先定义一个结构体。此结构体的每个结点都是由数据域data、左指针域Lchild、右指针域Rchild组成，两个指针域分别指向该结点的左、右孩子，若某结点没有左孩子或者右孩子时，对应的指针域就为空。最后，还需要一个链表的头指针指向根结点。

要注意的是，第一步的时候一定要先定义一个结束标志符号，例如空格键、＃等。当它遇到该标志时，就指向为空。

建立左右子树时，仍然是调用create（）函数，依此递归进行下去，直到遇到结束标志时停止操作。

 （2）输入二叉树元素

   输入二叉树时，是按上面所确定的遍历规则输入的。最后，用一个返回值来表示所需要的结果。

 （3）先序遍历二叉树

   当二叉树为非空时，执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。

 （4）中序遍历二叉树

   当二叉树为非空时，程序执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。

  （5）后序遍历二叉树

    当二叉树为非空时，程序执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。

   （6）主程序

    需列出各个函数，然后进行函数调用。

四、各函数定义及说明

     因为此二叉树是用链式存储结构存储的，所以定义一个结构体用以存储。

         typedef struct BiTNode

{  char data;

             struct BiTNode *Lchild;

             struct BiTNode *Rchild;

}BiTNode,*BiTree;

     （1）主函数main（）

         主程序要包括：定义的二叉树T、建树函数create（）、先序遍历函数Preorder（）、中序遍历函数Inorder（）、后序遍历函数Postorder（）。

     （2）建树函数Create（）

         定义一个输入的数是字符型的，当ch为空时，T就为空值，否则的话就分配空间给T，T就指向它的结点，然后左指针域指向左孩子，右指针指向右孩子，若还有，继续调用Create（），依次循环下去，直到ch遇到空时，结束。

         最后要返回建立的二叉树T。

      （3）先序遍历函数Preorder（）

         根据先序遍历规则，当T为非空时，先输出结点处的数据，指针指向左、右孩子，依次进行下去。

       (4) 中序遍历函数Inorder（）

         根据中序遍历规则，当T为非空时，先左指针指向左孩子数据，然后输出结点处的数据，再右指针指向右孩子，依次进行下去。

      （5）后序遍历函数Postorder（）

         根据后序遍历规则，当T为非空时，先右指针指向右孩子，然后左指针指向左孩子，最后输出结点处的数据，依次进行下去。

  五、使用说明

      在Turbo C的环境下，先按Ctrl+F9运行程序，此时就是建立二叉树的过程，例如输入序列-+a  *b  -c  d  /e  f  输入过程中不要加回车，因为回车也有对应的ASCII码，是要算字符的，输入完之后再按回车，用户界面上就能够看到结果了。

另外你必须会手动建立一棵二叉树，保证你输入的序列能构成一棵二叉树，否则你怎么输入，按最后按多少回车程序也不会结束！

六、源程序

#include "stdio.h"

#include "string.h"

#include "alloc.h"

#define NULL 0

typedef struct BiTNode

{

 char data;

 struct BiTNode *Lchild;

 struct BiTNode *Rchild;

}BiTNode,*BiTree;

BiTree Create()

{

 char ch;

 BiTree T;

 scanf("%c",&ch);

 if(ch==' ')

   T=NULL;

 else

   { T=(BiTNode *)malloc(sizeof(BiTNode));

     T->data=ch;

     T->Lchild=Create();

     T->Rchild=Create();

   }

return T;

}

void Preorder(BiTree T)

{

 if(T)

 {

  printf("%c",T->data);

  Preorder(T->Lchild);

  Preorder(T->Rchild);

 }

}

void Inorder(BiTree T)

{

 if(T)

 {

 Inorder(T->Lchild);

 printf("%c",T->data);

 Inorder(T->Rchild);

 }

}

void Postorder(BiTree T)

{

 if(T)

 {

  Postorder(T->Lchild);

  Postorder(T->Rchild);

  printf("%c",T->data);

 }

}

main()

{

 BiTree T;

 clrscr();

 printf("The elements is : ");

 T=Create();

 printf("\n");

 printf("The Preorder's result is : ");

 Preorder(T);

 printf(" \n\n");

 printf("The Inorder's result is : ");

 Inorder(T);

 printf("\n\n");

 printf("The Postorder's result is : ");

 Postorder(T);

 getch();

}

七、测试数据

                                    

八、测试结果

 先序遍历序列：-,+,a,*,b,-,c,d,/,e,f ；

  中序遍历序列：a,+,b,*,c,-,d,-,e,/,f ；

后序遍历序列：a,b,c,d,-,*,+,e,f,/,- ；

 

第二篇：线索化二叉树遍历实验报告 2

线索化二叉树遍历实验报告

09040502班     学号:052415     朱博凯

一、   需求分析

（1）    本程序需要用户自行输入二叉树（二叉树的数据可以是任何字符），用”#”表示空格，按回车键结束！

（2）  程序功能：遍历二叉树，线索化二叉树，遍历线索化二叉树，二叉树去线索化。

（3）  测试数据：

ABC##DE#G##F###；

二、   概要设计

为实现本程序功能，应以二叉树结构存储二叉树，而为了实现非递归遍历二叉树的功能，应以带头节点的栈存储二叉树。

1、  二叉树的抽象数据类型定义

ADT BinaryTree{

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

 数据关系R：如D=Ф，则R=Ф，称BinaryTree为空二叉树；

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

（1）       在D中存在唯一的称为根的数据元素root,它在关系H下无前驱；

（2）       如D-{root}≠Ф,则存在D-{root}={D1,Dr},且D1∩Dr=Ф;

（3）       如D1≠Ф,则D1中存在唯一元素x1,<ROOT,X< SPAN>1>∈H,且存在D1上的关系H1∈H；如Dr≠Ф，则Dr中存在唯一的元素xr，<ROOT,X< SPAN>r>∈H,且存在Dr上的关系Hr包含于H；H={<ROOT,X< SPAN>1>,<ROOT,X< SPAN>r>,H1,Hr}；

（4）       (D1,{H1})是一棵符合本定义的二叉树，称为根的右子树。

基本操作 P：

                     InitBiTree(&T);

                            操作结果：构造空二叉树T.

                     DestroyBiTree(&T);

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

                            操作结果：销毁二叉树T.

                     CreateBiThrTree(&T);

                            操作结果：先序构造二叉树T,Ltag和RTag初始置为Link.

PreOrderTraverse(T );

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

操作结果：先序递归遍历T。

                     InOrderTraverse(T);

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

操作结果：中序递归遍历T。

                     PostOrderTraverse(T);

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

操作结果：后序递归遍历T。

                     InOrderThreading(&ThrT, T);

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

                            操作结果：建立头结点ThrT,并调用InThreading(T);函数。

                     InThreading(T);

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

                            操作结果：中序线索化二叉树T;

                     InOrderTrasverse_Thr(T);

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

                            操作结果：中序扫描线索化的二叉树。

}ADT BinaryTree

2、  栈的抽象数据类型定义

ADT Stack{
数据对象：d={ a_i |a_i∈elemset,i=1,2,3,……，n，n≥0}

数据关系：r={<a_i-1,a_i,)>| a_i-1,a_i ∈d, i=2,3,……，n}

            约定a₁为栈底，a_n 为栈顶。

基本操作：

（1）InitStack(&S)
操作结果：构造一个空栈S。
（2）DestroyStack(&S)
初始条件：栈S已存在。
操作结果：销毁栈S。
（3）ClearStack（&S）
初始条件：栈S已存在。。
操作结果：将栈清空为空栈。
（4）StackEmpty(&S)
初始条件：栈S已存在。
操作结果：若栈S为空栈，则返回TRUE，否则FALSE。
（5）StackLength（&S）
初始条件：栈S已存在。
操作结果：返回栈的长度（或者说深度）。
（6）GetTop（S，&e）
初始条件：栈S已存在且非空。
操作结果：用e返回S的栈顶元素。
（7）Push（&S,e）
初始条件：栈S已存在。
操作结果：在栈顶插入新的元素e。
（8）Pop（&S,&e）
初始条件：栈S已存在且非空。
操作结果：删除栈S的栈顶元素，并且用e返回它的值。
（9）StackTraverse（S，visit（））
初始条件：栈S已存在。
操作结果：遍历访问栈，一次对S的每个元素调用函

}ADTStack

3、  程序包括6个模块

1）主程序模块：

2）创建二叉树；

3）计算树的高度；

4）递归遍历二叉树（先、中、后序）；

5）非递归遍历二叉树（先、中序）；

6）线索化二叉树（先、中序）；

7）二叉树去线索化；

三、   详细设计

1、  元素类型、结点类型

typedef struct BiTNode{

       TElemType data;

       struct BiTNode *lchild ,*rchild;

       PointerTag LTag , RTag;

}BiTNode , *BiTree , BiThrNode , *BiThrTree;        //二叉树

typedef struct{

       BiTree *base;

       BiTree *top;

       int stacksize;

}SqStack;            //栈

2、  栈的实现

typedef struct{

       char *base;

       char *top;

       int stacksize;

}SqStack;            //栈类型

栈的基本操作设置如下：
void InitStack(Stack &S)
    //初始化，设S为空栈（S.top=NULL）
void DestroyStack(Stack &S)
   //销毁栈S，并释放所占空间
void ClearStack(Stack &S)
   //将S清为空栈
int StackLength(Stack S)
   //返回栈S的长度S.size
Status StackEmpty(Stack S)
   //若S为空栈（S.top==NULL），则返回TRUE；否则返回FALSE
Status GetTop(Stack S,ElemType e)
   //若栈S不空，则以e带回栈顶元素并返回TRUE，否则返回FALSE
Status Push(Stack&S,ElemType e)
  //若分配空间成功，则在S的栈顶插入新的栈顶元素e，并返回TRUE，
  //否则返回FALSE
void StackTraverse(Stack S,Status (*visit)(ElemType e))
  //从栈底到栈顶依次对S中的每个结点调用函数visit

3、  主函数和其他函数的伪码

typedef int status;

typedef char TElemType;

typedef enum PointerTag{Link,Thread};

//二叉树的操作

status CreatBiTree(BiTree &T);

status treedepth(BiTree T);

status Visit(TElemType e);

status PreOrderTraverse(BiTree T,status(*Visit)(TElemType e));

status InOrderTraverse(BiTree T,status(*Visit)(TElemType e));

status PostOrderTraverse(BiTree T,status(*Visit)(TElemType e));

status UnInOrderTraverse(BiTree T,status(*Visit)(TElemType e));//非递归中序遍历

status UnPreOrderTraverse(BiTree T,status(*Visit)(TElemType e));//非递归先序遍历

//线索化二叉树的操作

void InOrderThreading(BiThrTree &Thrt,BiThrTree T);

void InThreading(BiThrTree p);

status InOrderTraverse_Thr(BiThrTree T, status (*Visit)(TElemType e));

void PreOrderThreading(BiThrTree &Thrt,BiThrTree T);

status PreOrderTraverse_Thr(BiThrTree T, status (*Visit)(TElemType e));

void PreThreading(BiThrTree p);

void UnThreading(BiThrTree &Thrt);

//栈的操作

status InitStack(SqStack &S);

status GetTop(SqStack S , BiTree &e);

status Push(SqStack &S , BiTree e);

status Pop(SqStack &S , BiTree &e);

status StackEmpty(SqStack S);

//全局变量

SqStack S;

BiThrTree pre;

BiThrTree i;

void main()          //主函数

{

       printf("\t************\n\t*二叉树演示*\n\t************\n");

       BiTree T;

       BiThrTree Thrt;

       printf("\n创建二叉树(用#表示空格):\n");

       CreatBiTree(T);

       printf("树的高度为:%d",treedepth(T));

       printf("\n递归先序遍历:");

       PreOrderTraverse(T , Visit);

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

       InOrderTraverse(T , Visit);

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

       PostOrderTraverse(T , Visit);

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

       UnInOrderTraverse(T , Visit);

       printf("\n非递归先序遍历:");

       UnPreOrderTraverse(T , Visit);

       printf("\n中序遍历线索化二叉树:");

       InOrderThreading(Thrt , T);

       InOrderTraverse_Thr(Thrt , Visit);

       printf("\n后序递归去线索化并输出:");

       UnThreading(Thrt);

       printf("\n先序遍历线索化二叉树:");

       PreOrderThreading(Thrt , T);

       printf("\n");

}

status CreatBiTree(BiTree &T)

//创建二叉树

{

       char ch;

       ch=getchar();

       if(ch=='#')

       T=NULL;

       else{

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

                     return ERROR;

              T->data=ch;

              if (CreatBiTree(T->lchild)) T->LTag=Link;

              if (CreatBiTree(T->rchild)) T->RTag=Link;

       }

       return OK;

}

status treedepth(BiTree T)

//计算树的高度

{

       int lchilddep,rchilddep;

       if(T==NULL)

              return 0;

       else

       {

              lchilddep=treedepth(T->lchild);

              rchilddep=treedepth(T->rchild);

              if(lchilddep>rchilddep)

                     return lchilddep+1;

              else

                     return rchilddep+1;

       }

}

status Visit(TElemType e)

{

       printf("%c",e);

       return OK;

}

status PreOrderTraverse(BiTree T,status(*Visit)(TElemType e))

//递归先序遍历

{

       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 InOrderTraverse(BiTree T,status(*Visit)(TElemType e))

//递归中序遍历

{

       if(T)

       {

              if(InOrderTraverse(T->lchild,Visit))

                     if(Visit(T->data))

                            if(InOrderTraverse(T->rchild,Visit))

                                   return OK;

                            return ERROR;

       }

       else return OK;

}//InOrderTraverse

status PostOrderTraverse(BiTree T,status(*Visit)(TElemType e))

//递归后序遍历

{

       if(T)

       {

              if(PostOrderTraverse(T->lchild,Visit))

                     if(PostOrderTraverse(T->rchild,Visit))

                            if(Visit(T->data))

                                   return OK;

                            return ERROR;

       }

       else return OK;

}//PostOrderTraverse

status UnInOrderTraverse(BiTree T,status(*Visit)(TElemType e))

//非递归中序遍历

{

       BiTree p;

       InitStack(S);

       Push(S,T);

       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;

}//UnInOrderTraverse

status UnPreOrderTraverse(BiTree T,status(*Visit)(TElemType e))

//非递归先序遍历

{

       BiTree p;

       InitStack(S);

       p=T;

       while(p||!StackEmpty(S))

       {

              if(p)

              {

                     if(!Visit(p->data))

                            return ERROR;

                     Push(S,p);

                     p=p->lchild;

              }

              else

              {

                     Pop(S,p);

                     p=p->rchild;

              }//else

       }//while

       return OK;

}//UnPreOrderTraverse

void InOrderThreading(BiThrTree &Thrt,BiThrTree T)

//中序遍厉二叉树T，并将其中序线索化，Thrt指向头结点

{

       if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) exit(OVERFLOW);

       Thrt->LTag=Link;//建头结点

       Thrt->RTag=Thread;

       Thrt->rchild=Thrt;//右指针回指

       if(!T)

       Thrt->lchild=Thrt;

       else

       {

              Thrt->lchild=T;

              pre=Thrt;

              InThreading(T);//中序遍历进行中序线索化

              pre->rchild=Thrt;

              pre->RTag=Thread;//最后一个结点线索化

              Thrt->rchild=pre;

       }

       i=Thrt;

}//InOrderThreading

void InThreading(BiThrTree p)       //线索化

{

       if(p)

       {

              InThreading(p->lchild);

              if(!p->lchild)

              {

                     p->LTag = Thread;

                     p->lchild = pre;

              }

              if(!pre->rchild)

              {

                     pre->RTag = Thread;

                     pre->rchild = p;

              }

              pre = p;

              InThreading(p->rchild);

       }

}//InThreading

void UnThreading(BiThrTree &Thrt)  //后序去线索化

{

       BiThrTree p=Thrt;

       if(p)

       {

              if(p->LTag == Thread)

              {

                     p->lchild = NULL;

                     p->LTag = Link;

              }

              if(p->LTag == Link && p->lchild) UnThreading(p->lchild);

              if(p->RTag == Link && p->rchild)UnThreading(p->rchild);

              if(p != i) Visit(p->data);

       }

}

status InOrderTraverse_Thr(BiThrTree T, status (*Visit)(TElemType e))

//中序遍历线索化后的二叉树

{

       BiThrTree p;

       p=T->lchild;

       while(p!=T)

       {

              while(p->LTag==Link)

                     p=p->lchild;

              if(!Visit(p->data))

                     return ERROR;

              while(p->RTag==Thread && p->rchild!=T)

              {

                     p=p->rchild;

                     Visit(p->data);

              }

              p=p->rchild;

       }

       return OK;

}

void PreOrderThreading(BiThrTree &Thrt,BiThrTree T)

//先序遍厉二叉树T，并将其先序线索化，Thrt指向头结点

{

       if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)))) exit(OVERFLOW);

       Thrt->LTag=Link;

       Thrt->RTag=Thread;//建头结点

       Thrt->rchild=Thrt;//右指针回指

       if(!T)

       Thrt->lchild=Thrt;

       else

       {

              Thrt->lchild=T;

              pre=Thrt;

              PreThreading(T);//先序遍历进行先序线索化

              pre->rchild=Thrt;pre->RTag=Thread;//最后一个结点线索化

              Thrt->rchild=pre;

       }

       i=Thrt;

}

status PreOrderTraverse_Thr(BiThrTree T, status (*Visit)(TElemType e))

//先序遍历线索化后的二叉树

{

       BiThrTree p;

       p=T->lchild;

       while(p!=T)

       {

              while(p->LTag==Link)

                     p=p->lchild;

              if(!Visit(p->data))

                     return ERROR;

              while(p->RTag==Thread && p->rchild!=T)

              {

                     p=p->rchild; Visit(p->data);

              }

              p=p->rchild;

       }

       return OK;

}//PreOrderTraverse_Thr

void PreThreading(BiThrTree p)            //先序线索化

{

       if(p)

       {

             

              if(!p->lchild)

              {

                     p->LTag = Thread;

                     p->lchild = pre;

              }

              if(!pre->rchild)

              {

                     pre->RTag = Thread;

                     pre->rchild = p;

              }

              pre = p;

              Visit(p->data);

             

              if(p->LTag==Link)

                     PreThreading(p->lchild);

              if(p->RTag == Link)

                     PreThreading(p->rchild);

       }

}//PreThreading

status InitStack(SqStack &S)         //栈的初始化

{

       S.base=(BiTree *)malloc(STACK_INIT_SIZE * sizeof(BiTree));

       if(!S.base)exit(OVERFLOW);

       S.top = S.base;

       S.stacksize = STACK_INIT_SIZE;

       return OK;

}

status GetTop(SqStack S , BiTree &e)          //取顶元素

{

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

       else{

              e = *(S.top-1);

              return OK;

       }

}

status Push(SqStack &S , BiTree e)              //进栈

{

       if(S.top - S.base >= S.stacksize)

       {

              S.base = (BiTree *)realloc(S.base , (S.stacksize + STACKINCREMENT) * sizeof(BiTree));

              if(!S.base) exit(OVERFLOW);

              S.top = S.base + S.stacksize;

              S.stacksize += STACKINCREMENT;

       }

       *S.top++ = e;

       return OK;

}

status Pop(SqStack &S , BiTree &e)            //出栈

{

       if(S.top == S.base)

              return ERROR;

       else{

              e = * --S.top;

              return OK;

       }

}

status StackEmpty(SqStack S)                     //检查栈是否为空

{

       if(S.top == S.base)

              return 1;

       else

              return 0;

}

4、  函数间调用关系

四、   调试分析

1．  在线索化二叉树时，如果像书上把二叉树和线索二叉树的存储结构分开，则二叉树中的数据域不能传递到线索二叉树中（两个类型的指针不能互相赋值）。比较两种存储结构发现，线索二叉树比二叉树多了两个标志域LTag,Rtag。于是把两种存储结构合并为BiThrNode,并在建立二叉树时把LTag,Rtag均置为Link。程序正常运行。

2．  本次实验报告所用的算法，书中均有具体算法演示，且易实现，除存储结构外没有大问题。

五、   用户手册

1.      本程序开发环境为VC 6.0，运行环境为dos操作系统，执行文件为：Binary Tree.exe

2.      运行该程序的Binary Tree.exe文件,产生如下图所示的界面

3.      按照提示输入二叉树（以”#”表示空格）。

4.      输入完成后，按回车键。

5.      屏幕上打印出对应于该二叉树的的各种遍历结果。

六、   测试结果

输入一个二叉树： abc##de#g##f###

屏幕打印结果：

树的高度为: 5

递归先序遍历: abcdegf

递归中序遍历: cbegdfa

递归后序遍历: cgefdba

非递归中序遍历: cbegdfa

非递归先序遍历: abcdegf

中序遍历线索化二叉树: cbegdfa

后序递归去线索化并输出: cgefdba

先序遍历线索化二叉树: abcdegf

七、  附录

源程序文件名清单：
Binary Tree.cpp //主程序
Binary Tree.exe //可执行文件

stdio.h          //程序中用到的头文件

stdlib.h