实验12 二叉树遍历实验报告

题目：实现链式存储的二叉树的多种遍历算法，包括递归、非递归以及线索二叉树等

班级：信息学院2011级理科实验班1班  姓名：  学号：

完成日期：2012-5-19

一、需求分析

1.演示程序分别用多种遍历算法遍历二叉树并把数据输出。

2.输入字符序列，递归方式建立二叉树。

3.在演示过程序中，用户敲击键盘，输入数据，即可看到数据的输出。

4.实现链式存储的二叉树的多种遍历算法。

遍历算法包括：

a)中序递归遍历算法、前序递归遍历算法【选】

b)中序遍历非递归算法

c)先序或后序遍历非递归算法

d)建立中序线索，并进行中序遍历和反中序遍历

5.实现二叉树的按层遍历算法

6.设计一个测试用的二叉树并创建对应的内存二叉树，能够测试自己算法的边界(包括树节点数为0、1以及>1 的不同情形)。

7.测试数据：输入数据：-+a  *b  -c  d  -e  f 

二、概要设计

说明：本程序在递归调用中用到了链表，在非递归调用时用到了栈。

1.栈的抽象数据类型

ADT Stack{

数据对象：D={ai|ai∈char,i=1,2,3……..}

数据关系：R={< ai -1,ai >| ai -1,ai ∈D,i=2,3…..}

基本操作：

InitStack（&S）  

操作结果：构造一个空栈

StackEmpty( S )

         初始条件：栈S已存在。

         操作结果：若S为空栈，则返回OK，否则返回ERROR。 

Push( &S, e )

         初始条件：栈S已存在。

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

      Pop( &S, &e )

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

         操作结果：删除S的栈顶元素，并用e返回其值。 

GetTop( S, &e )

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

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

}

2.二叉树的抽象数据类型

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，∈H，且存在D1上的                 关系H1 ⊆H；若Dr≠Φ，则Dr中存在惟一的元素xr，∈H，且                 存在上的关系Hr ⊆H；H={,,H1,Hr}；  

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

     基本操作：  

           CreateBiTree( &T)  

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

             操作结果：按要求构造二叉树T。

       PreOrderTraverse_re( T, print() )  

             初始条件：二叉树T存在，print是二叉树全部结点输出的应用函数。  

             操作结果：先序递归遍历T，对每个结点调用函数print一次且仅一次。一旦                      print()失败，则操作失败。 

       InOrderTraverse( T, print() )  

             初始条件：二叉树T存在，print是二叉树全部结点输出的应用函数。  

             操作结果：中序非递归遍历T，对每个结点调用函数print一次且仅一次。一                      旦printf()失败，则操作失败。 

InOrderTraverse_re(T,print() ) 

         初始条件：二叉树T在在，print是二叉树全部结点输出的应用函数。

操作结果：中序递归遍历T，对每个结点调用函数print一次且仅一次。一旦              printf()失败，则操作失败。 

PreOrderTraverse(T,print())

    初始条件：二叉树T存在，print是二叉树全部结点输出的应用函数。  

         操作结果：先序非递归遍历T，对每个结点调用函数print一次且仅一次。一                  旦print()失败，则操作失败。 

 Levelorder(T) 

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

操作结果：分层遍历二叉树T，并输出。

InOrderThreading(Thrt,T);

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

操作结果：中序遍历二叉树，并将其中序线索化。

InOrderTraverse_Thr( T, print);

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

操作结果：中序非递归遍历二叉线索树T

InThreading(p);

初始条件：结点p在在。

操作结果：结点p及子树线索化。

3.主程序的流程：

void main()

{

    初始化;

    提示;

    执行二叉数ADT函数;

}

4.本程序包含三个模块

1）主程序模块

void main(){

初始化；

{

接受命令；

显示结果；

｝

｝

2）链表模块。递归调用时实现链表抽象数据类型。

3）栈模块。非递归调用时实现栈的抽象数据类型。

三、详细设计

1.宏定义及全局变量

#define TElemType char

#define SElemType BiTree

#define OK 1

#define OVERFLOW 0

#define ERROR 0

#define STACK_INIT_SIZE 100

#define STACKINCREMENT 10

SqStack S;

BiThrTree pre;

BiThrTree i;

2.函数定义

int CreateBiTree(BiTree &T);                                    //创建二叉树

void PreOrderTraverse_re(BiTree T,void (*print)(TElemType e));    //先序递归遍历二叉树

void InOrderTraverse(BiTree T,int (*print)(TElemType e));        //中序非递归遍历二叉树

void InOrderTraverse_re(BiTree T,int (*print)(TElemType e)) ;    //中序递归遍历二叉树

void PreOrderTraverse(BiTree T,int (*print)(TElemType e));        //先序非递归遍历二叉树

int print(TElemType e);        //打印元素

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

void Pop(SqStack &S,SElemType &e);

void Push(SqStack &S,SElemType &e);

int StackEmpty(SqStack S);

int GetTop(SqStack S,SElemType &e);

void Levelorder(BiTree T) ;

void InOrderThreading(BiThrTree &Thrt,BiThrTree T);

int InOrderTraverse_Thr(BiThrTree T, int (*print)(TElemType e));

void InThreading(BiThrTree p);

3.二叉树链表

数据结构：

typedef struct BiTNode{

    TElemType data;

    struct BiTNode *lchild ,*rchild;

    PointerTag LTag , RTag;

}BiTNode , *BiTree , BiThrNode , *BiThrTree;     

基本操作：

a)构造二叉树T

int CreateBiTree(BiTree &T)

{

    char ch;

    scanf("%c",&ch);

    if(ch==' ')

        T=NULL;

    else

    {

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

            return ERROR;

     T->data=ch;

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

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

    }

    return OK;

}

b)先序递归遍历二叉数T，并输出全部结点值。

void PreOrderTraverse_re(BiTree T,int (*print)(TElemType e))

{

    if(T)

    {

     if(print(T->data))

          PreOrderTraverse_re(T->lchild,print);

         PreOrderTraverse_re(T->rchild,print);

        return ;

    }

    else

        return ;

}

c)中序非递归遍历二叉树T，并输出全部结点值

void InOrderTraverse(BiTree T,int (*print)(TElemType e))

{

    SqStack S;

    S.base=NULL;S.top=NULL;

    SElemType p=NULL;

    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);

         print(p->data);

         Push(S,p->rchild);

        }

    }

    return;

}

d)中序递归遍历二叉树T，并输出全部结点值

void InOrderTraverse_re(BiTree T,int (*print)(TElemType e))  

 {  

     if(T)  

     {  

InOrderTraverse_re(T->lchild,print);

print(T->data);

InOrderTraverse_re(T->rchild,print);

     }  

 }

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

 void InOrderThreading(BiThrTree &Thrt,BiThrTree T)

{

    Thrt=(BiThrTree)malloc(sizeof(BiThrNode));

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

f)结点p线索化

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;                   // 保持pre指向p的前驱

     InThreading(p->rchild); // 右子树线索化

      }    

} // InThreading

g)//中序遍历线索化二叉树

int InOrderTraverse_Thr(BiThrTree T, int (*print)(TElemType e))

{

    BiThrTree p=NULL;

p=T->lchild;

    while(p!=T)

    {

     while(p->LTag==Link)

         p=p->lchild;

     if(!print(p->data))

            return ERROR;

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

        {

         p=p->rchild;

         print(p->data);

        }

     p=p->rchild;

    }

    return OK;

}

4.栈

数据结构：

typedef struct{

        SElemType *base;

        SElemType *top;

        int stacksize;

}SqStack;

基本操作：

a)创建一个空栈

void InitStack(SqStack &S)

{

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

    S.top=S.base;        //初始为空

    S.stacksize=STACK_INIT_SIZE;

    return;

}

b)栈顶插入元素

void Push(SqStack &S,SElemType &e)

{

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

    {

        S.base=(SElemType*)realloc(S.base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(SElemType));

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

        S.stacksize+=STACKINCREMENT;

    }

    *S.top++=e;

}

c)栈顶删除元素

void Pop(SqStack &S,SElemType &e)

{

    if(S.top==S.base)

        return;

    e=*--S.top;

    return;

}

d)判断栈是否为空栈

int StackEmpty(SqStack S)            

{

    if(S.top==S.base)

        return OK;

    else

        return ERROR;

}

e)e返回S的栈顶元素

int GetTop(SqStack S,SElemType &e)

{

    if(S.top==S.base)

        return ERROR;

    e=*(S.top-1);

    return OK;

}

5.主函数

void main()

{

    int flag;

    BiTree T;

    BiThrTree Thrt;

    printf("**********************************************************\\n");

    printf("**          实验12  二叉树的遍历                        **\\n");

    printf("** 1. 实现二叉树的不同遍历算法和二叉树的中序线索化算法  **\\n");

    printf("**  a) 中序递归遍历算法；                               **\\n");

    printf("**  b) 先序递归遍历算法；                               **\\n");

    printf("**  c) 中序遍历的非递归算法；                           **\\n");

    printf("**  d) 先序或后序遍历非递归算法之一；                   **\\n");

    printf("**  e) 建立中序线利用线索进行中序遍历和反中序遍历。     **\\n");

    printf("** 2. 实现二叉树的按层遍历算法。                        **\\n");

    printf("**********************************************************\\n");

    printf("\\n选择操作：\\n\1.先序与中序遍历算法\\n\2.中序线索的中序遍历和反中序遍历算法\\n\3.按层遍历算法\\n请选择：");

    scanf("%d",&flag);

    switch(flag)

    {

        case 1:        

                printf("前序递归创建二叉树（空格 表示此结点为空）:\\n");

                getchar();

                CreateBiTree(T);

                printf("中序递归遍历输出:");

                InOrderTraverse_re(T,print);

                printf("\\n前序递归遍历输出：");

                PreOrderTraverse_re(T,print);

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

                InOrderTraverse(T,print);

                printf("\\n前序非递归遍历输出：");

                PreOrderTraverse(T,print);  

                printf("\\n");

                break;

        case 2:    printf("前序递归创建二叉树（空格 表示此结点为空）:\\n");

                getchar();

                CreateBiTree(T);

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

                InOrderThreading(Thrt , T);

                InOrderTraverse_Thr(Thrt , print);

                break;

        case 3: printf("前序递归创建二叉树（空格 表示此结点为空）:\\n");

                getchar();

                CreateBiTree(T);

                printf("\\n按层遍历输出：");

                Levelorder(T);

                printf("\\n");

                break;

        default:return;

    }

}

6.函数间调用关系

4、调试分析

1、二叉树的分层遍历，开始时想用队列来做，但考虑到比较麻烦，因而改为数组模拟队列，简单易懂，课后可自行尝试用队列来做。

2．  在线索化二叉树时考虑到如果将两种存储结构分开将导致两个类型的指针不能互相传值，造成许多麻烦。比较两种存储结构发现，线索二叉树比二叉树多了两个标志域LTag,Rtag。于是把两种存储结构合并为BiThrNode,并在建立二叉树时把LTag,Rtag均置为Link。程序正常运行。

五、用户手册

1 本程序的运行环境为windows xp操作系统，开发环境为VC6.0，执行文件为顺BiTree.exe

2进入演示程序BiTree.cpp，完成编译，连接（即按下Ctrl F5）进入演示界面，或直接打开执行文件BiTree.exe，产生如下图所示的界面：

3用户需根据用户提示信息操作，输入二叉树（以空格表示空结点），输入完成后按回车键，屏幕上打印出对应于该二叉树的各种遍历结果。如下图：

6、测试结果

输入：-+a  *b  -c  d  -e  f  

屏幕输出：

中序递归遍历输出：a+b*c-d

前序递归遍历输出：+a*b-cd

中序非递归遍历输出：a+b*c-d

前序非递归遍历输出：+a*b-cd

按层遍历输出：+a*b-cd

中序遍历线索化二叉树：a+b*c-d

7、附录

BiTree.cpp

BiTree.exe

#include

#include

#define QElemType BiTNode

#define TElemType char

#define OK 1

#define OVERFLOW 0

#define ERROR 0

#define STACK_INIT_SIZE 100

#define STACKINCREMENT 10

typedef enum PointerTag{Link,Thread};    //Link==0,指针，Thread==1,线索

typedef struct BiTNode{

    TElemType data;

    struct BiTNode *lchild ,*rchild;

    PointerTag LTag , RTag;

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

#define QElemType BiTNode

#define SElemType BiTree

typedef struct{

    SElemType *base;

    SElemType *top;

    int stacksize;

}SqStack;

//全局变量

SqStack S;

BiThrTree pre;

BiThrTree i;

/*函数声明*/                                

int CreateBiTree(BiTree &T);                                    //创建二叉树

void PreOrderTraverse_re(BiTree T,void (*print)(TElemType e));    //先序递归遍历二叉树

void InOrderTraverse(BiTree T,int (*print)(TElemType e));        //中序非递归遍历二叉树

void InOrderTraverse_re(BiTree T,int (*print)(TElemType e)) ;    //中序递归遍历二叉树

void PreOrderTraverse(BiTree T,int (*print)(TElemType e));        //先序非递归遍历二叉树

int print(TElemType e);        //打印元素

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

void Pop(SqStack &S,SElemType &e);

void Push(SqStack &S,SElemType &e);

int StackEmpty(SqStack S);

int GetTop(SqStack S,SElemType &e);

void Levelorder(BiTree T) ;

void InOrderThreading(BiThrTree &Thrt,BiThrTree T);

int InOrderTraverse_Thr(BiThrTree T, int (*print)(TElemType e));

void InThreading(BiThrTree p);

/*二叉树的创建递归创建*/

int CreateBiTree(BiTree &T)

{

    char ch;

    scanf("%c",&ch);

    if(ch==' ')

        T=NULL;

    else

    {

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

            return ERROR;

     T->data=ch;

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

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

    }

    return OK;

}

 /*******************************************/ 

 /*             先序递归遍历输出            */ 

 /*******************************************/

void PreOrderTraverse_re(BiTree T,int (*print)(TElemType e))

{

    if(T)

    {

     if(print(T->data))

          PreOrderTraverse_re(T->lchild,print);

         PreOrderTraverse_re(T->rchild,print);

        return ;

    }

    else

        return ;

}

 /*******************************************/ 

 /*            中序非递归遍历输出           */ 

 /*******************************************/

void InOrderTraverse(BiTree T,int (*print)(TElemType e))

{

    SqStack S;

    S.base=NULL;S.top=NULL;

    SElemType p=NULL;

    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);

         print(p->data);

         Push(S,p->rchild);

        }

    }

    return;

}

 /*******************************************/ 

 /*            中序递归遍历输出             */ 

 /*******************************************/

void InOrderTraverse_re(BiTree T,int (*print)(TElemType e))  

 {  

     if(T)  

     {  

InOrderTraverse_re(T->lchild,print);

print(T->data);

InOrderTraverse_re(T->rchild,print);

     }  

     return ;  

 }

 /*******************************************/ 

 /*          按照前序非递归遍历二叉树：栈   */ 

 /*******************************************/   

void PreOrderTraverse(BiTree T,int (*print)(TElemType e))  

{  

    SqStack S;

    S.base=NULL;S.top=NULL;

    SElemType p=T;//p指向当前访问的结点 

    InitStack(S);     

    while(p||!StackEmpty(S))  

     {  

         if(p)  

         {  

print(p->data);

             Push(S,p);  

p=p->lchild;

         }  

         else 

         {  

             Pop(S,p);  

p=p->rchild;

         }  

     }  

     return;  

 }

 void InOrderThreading(BiThrTree &Thrt,BiThrTree T)

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

{

    Thrt=(BiThrTree)malloc(sizeof(BiThrNode));

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;                   // 保持pre指向p的前驱

InThreading(p->rchild); // 右子树线索化

  }

} // InThreading

int InOrderTraverse_Thr(BiThrTree T, int (*print)(TElemType e))

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

{

    BiThrTree p=NULL;

p=T->lchild;

    while(p!=T)

    {

     while(p->LTag==Link)

         p=p->lchild;

     if(!print(p->data))

            return ERROR;

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

        {

         p=p->rchild;

         print(p->data);

        }

     p=p->rchild;

    }

    return OK;

}

/***************************以下为辅助函数***************************************/

int print(TElemType e)

{

    printf("%c",e);

    return OK;

}

/*栈函数*/

/*栈的初始化*/

void InitStack(SqStack &S)

{

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

    S.top=S.base;        //初始为空

    S.stacksize=STACK_INIT_SIZE;

    return;

}

/*栈顶插入元素*/

void Push(SqStack &S,SElemType &e)

{

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

    {

        S.base=(SElemType*)realloc(S.base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(SElemType));

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

        S.stacksize+=STACKINCREMENT;

    }

    *S.top++=e;

}

/*栈顶删除元素*/

void Pop(SqStack &S,SElemType &e)

{

    if(S.top==S.base)

        return;

    e=*--S.top;

    return;

}

int StackEmpty(SqStack S)            /*若栈为空栈，则返回OK，否则返回ERROR*/

{

    if(S.top==S.base)

        return OK;

    else

        return ERROR;

}

int GetTop(SqStack S,SElemType &e)

{

    if(S.top==S.base)

        return ERROR;

    e=*(S.top-1);

    return OK;

}

 /************************************************************/ 

 /*                  按层次顺序建立一棵二叉树                */ 

 /************************************************************/ 

void Levelorder(BiTree T) 

{

    int i,j; 

    BiTNode *q[20],*p; /*q[20]用于模拟队列，存储入队的结点*/ 

    p=T; 

    if(p!=NULL) 

    {

        i=1;q[i]=p;j=2;

    } /*i为队首位置，j为队尾位置*/ 

    while(i!=j) 

    {

        p=q[i];

printf("%c",p->data); /*访问队首元素*/ 

if (p->lchild!=NULL)

        {

q[j]=p->lchild;

            j++;

        } 

        /*若队首元素左链域不为空，则将其入队列*/ 

if (p->rchild!=NULL)

        {

q[j]=p->rchild;

            j++;

        } 

        /*若队首元素右链域不为空，则将其入队列*/ 

        i++; /*将队首移到下一个位置*/ 

    } 

} 

void main()

{

    int flag;

    BiTree T;

    BiThrTree Thrt;

    printf("**********************************************************\\n");

    printf("**          实验12  二叉树的遍历                        **\\n");

    printf("** 1. 实现二叉树的不同遍历算法和二叉树的中序线索化算法  **\\n");

    printf("**  a) 中序递归遍历算法；                               **\\n");

    printf("**  b) 先序递归遍历算法；                               **\\n");

    printf("**  c) 中序遍历的非递归算法；                           **\\n");

    printf("**  d) 先序或后序遍历非递归算法之一；                   **\\n");

    printf("**  e) 建立中序线利用线索进行中序遍历和反中序遍历。     **\\n");

    printf("** 2. 实现二叉树的按层遍历算法。                        **\\n");

    printf("**********************************************************\\n");

/*    printf("\\n选择操作：\\n\1.先序与中序遍历算法\\n\2.中序线索的中序遍历和反中序遍历算法\\n\3.按层遍历算法\\n请选择：");

    scanf("%d",&flag);

    switch(flag)

    {

        case 1:        

                printf("前序递归创建二叉树（空格 表示此结点为空）:\\n");

                getchar();

                CreateBiTree(T);

                printf("中序递归遍历输出:");

                InOrderTraverse_re(T,print);

                printf("\\n前序递归遍历输出：");

                PreOrderTraverse_re(T,print);

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

                InOrderTraverse(T,print);

                printf("\\n前序非递归遍历输出：");

                PreOrderTraverse(T,print);  

                printf("\\n");

                break;

        case 2:    printf("前序递归创建二叉树（空格 表示此结点为空）:\\n");

                getchar();

                CreateBiTree(T);

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

                InOrderThreading(Thrt , T);

                InOrderTraverse_Thr(Thrt , print);

                break;

        case 3: printf("前序递归创建二叉树（空格 表示此结点为空）:\\n");

                getchar();

                CreateBiTree(T);

                printf("\\n按层遍历输出：");

                Levelorder(T);

                printf("\\n");

                break;

        default:return;

    }*/

                printf("前序递归创建二叉树（空格 表示此结点为空）:\\n");

                getchar();

                CreateBiTree(T);

                printf("中序递归遍历输出:");

                InOrderTraverse_re(T,print);

                printf("\\n前序递归遍历输出：");

                PreOrderTraverse_re(T,print);

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

                InOrderTraverse(T,print);

                printf("\\n前序非递归遍历输出：");

                PreOrderTraverse(T,print);  

                printf("\\n按层遍历输出：");

                Levelorder(T);

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

                InOrderThreading(Thrt , T);

                InOrderTraverse_Thr(Thrt , print);

                printf("\\n");

    while(1);

    return;

}