沈阳航空航天大学

课 程 设 计 报 告

课程设计名称：数据结构课程设计

课程设计题目：树与二叉树转换

院（系）：

专    业：

班    级：

学    号：

姓    名：

指导教师：

完成日期：

目    录

第1章       题目内容与要求... 1

1 基本功能... 1

2 功能分解... 1

第2章  系统模块结构及流程图... 2

2.1创建模块... 2

2.2遍历模块... 4

2.3转换模块... 8

2.4线索化模块... 9

2.5主模块... 10

第3章  数据结构的描述... 13

第4章 涉及函数的描述... 14

第5章  测试运行结果... 15

参考文献... 17

附   录（程序清单）... 18

第1章                       题目内容与要求

1 基本功能

内容：写一个程序，利用双亲法创建一棵树，将该树转换为二叉链表表示，并给出二叉树的先序、中序、后序的遍历结果以及对该二叉树进行中序遍历线索化。

要求：

1)        给出树的双亲表示和二叉链表表示的存储结构；

2)        要求二叉树三种遍历要采用非递归算法；

3)        给出动态演示（选做）；

2 功能分解

CreateTree(T)：用双亲法建一棵树；

操作函数 （1）PreOrder(ct)：先序非递归方法遍历二叉树；

         （2）InOrder(ct)：中序非递归方法遍历二叉树；

         （3）PostOrder(ct)：后续非递归方法遍历二叉树；

（4）InThreading(ct)：中序线索化二叉树；

（5）PTreeToCSTree(T,0)：将树转换为二叉链表表示的二叉树；

main( )：输出主菜单，根据需要输入菜单上对应功能的数字调用各个函数，实现功能；

第2章  系统模块结构及流程图

 本程序主要分为四个模块（ 见图 1）：创建模块，转换模块，遍历模块，线索化模块。创建模块：利用双亲法创建一棵树。转换模块：将双亲法建立的树转换为二叉链表表示的孩子—兄弟表示法，转换为二叉树。遍历模块：将转换后的二叉树进行前序、中序和后序的非递归遍历。线索化模块：将转换后的二叉树进行中序遍历线索化。

 

图1 功能模块图

2.1创建模块

利用双亲法创建一棵树的操作，流程如图2.1所示：

图2.1   双亲法建树的流程图

2.2遍历模块

用非递归算法将转换后的二叉树进行先序、中序和后序的非递归遍历。其中先序遍历的流程如图2.21所示，中序遍历的流程图如图2.22所示，后序的非递归遍历流程图如图2.23所示。

图2.21  遍历模块中先序遍历的流程图

                      Y

图2.22  遍历模块中中序遍历的流程图

                                      Y

图2.23    遍历模块中后序遍历流程图

2.3转换模块

将用双亲法创建的树转化为二叉链表表示的二叉树，模块具体流程如图2.3所示。

图2.3     转换模块流程图

2.4线索化模块

将转换后的二叉树进行中序遍历线索化，即按照中序遍历顺序，若结点没有左孩子，则指向它的前驱，如果没有右孩子，就指向该结点的后继。具体流程图如图2.4所示。

    图2.4     线索化模块流程图

2.5主模块

输出主菜单，根据需要输入菜单上对应功能的数字调用各个函数，实现各种功能。流程图如下图2.5.

第3章  数据结构的描述

     树是一种非线性的数据结构，树中的元素之间是一对多的层次关系。树有以下三种常用的存储结构，即双亲表示法、孩子表示法和孩子兄弟表示法（二叉链表法）。本实验要实现的第一个功能就是将用双亲表示法建立的树转换为二叉树，即将树的双亲表示法转换为孩子兄弟表示法。

双亲表示法及孩子兄弟表示法：

typedef struct PTNode

{

       char data;

       int parent;// 双亲位置域

       int num;

}PTNode;

typedef struct CSNode

{

       char data;

       CSNode *firstchild,*nextsibling;

       PointerTag LTag,RTag; // 左右标志

}CSNode,*CSTree,ElemType;

    对二叉树的重要操作之一就是遍历，本实验对二叉树执行的是前序、中序以及后序的遍历，并且利用了顺序栈的特点实现了这些遍历的非递归算法。

    本实验实现的第三个功能就是对二叉树进行中序遍历线索化。二叉树的线索化就是利用二叉树中结点的空指针域表示结点的前驱或后继信息，而要得到结点的前驱和后继的信息，需要对二叉树进行遍历，同时将节点的空指针域修改为其直接前驱或直接后继信息，因此二叉树的线索化就是对二叉树的遍历过程。

第4章 涉及函数的描述

主要函数设计：

void CreateTree(PTree &T)

作用：利用双亲法建立一棵树T。

参数表：T为存放创建后树的结构体指针。

CSTree PTreeToCSTree (PTree T,int root)

作用：将用双亲法创建的树转换为二叉树。

参数表：T 为存放双亲表示法的树，指针，root为根结点的编号。

void PreOrder(CSNode *ct)

作用：对二叉树进行先序遍历。

参数表：ct为传递进来的转后的二叉树的根结点。

void InOrder(CSTree ct)

作用：对二叉树进行中序遍历。             

参数表：ct为传递进来的转后的二叉树的根结点。

void PostOrder(CSTree ct)

作用：对二叉树进行后序遍历。             

参数表：ct为传递进来的转后的二叉树的根结点。

void InThreading(CSNode *ct)

作用：对二叉树进行中序遍历线索化。        

参数表：ct为传递进来的转后的二叉树的根结点。

第5章  测试运行结果

运行操作及结果：

主菜单界面如下：

输入1，进入创建树界面，按照提示输入一棵树

 

界面如下：

成功创建树后，将树转换为二叉树，键入2，实现转换。

再在菜单输入3、4、5或6，实现对应功能，下图举例为前序遍历结果：

参考文献

[1] 周洪玉.数据结构[M].北京:清华大学出版社,2011

[2] 严蔚敏.数据结构（C语言版）.北京:清华大学出版社，2003

[3] 陈锐.零基础学数据结构.北京:机械工业出版社，2010

[4] 王成端、徐翠霞.数据结构上机实验与习题解析.北京:中国电力出版社，2006

[5]侯风巍.数据结构要点精析—C语言版.北京:北京航空航天大学出版社，2007

附   录（程序清单）

#include

#include

#include

#include

#define OVERFLOW -1

#define MAX_TREE_SIZE 100

#define STACK_INIT_SIZE 100

#define OK 1

#define ERROR 0

typedef struct PTNode

{

         char data;

         int parent;// 双亲位置域

         int num;

}PTNode;

typedef struct

{

         PTNode nodes[MAX_TREE_SIZE];

         int n; // 结点数

}PTree;

enum PointerTag // 枚举

{Link,Thread}; // Link(0):指针,Thread(1):线索

typedef struct CSNode

{

         char data;

         CSNode *firstchild,*nextsibling;

         PointerTag LTag,RTag; // 左右标志

}CSNode,*CSTree,ElemType;

typedef struct node

{

ElemType stack;

struct node *next;

}linkstack;          

typedef struct

 {

   int num;

   char name;

 }QElemType;

typedef struct QNode //定义队列

{

   char data;

    struct QNode *next;

}QNode,*QueuePtr;

typedef struct //定义队列的头尾指针

{

         QueuePtr  front;

    QueuePtr  rear;

}LinkQueue;

int Initstack(linkstack **s)//初始化一个带头结点的链式空栈

{

*s=(linkstack *)malloc(STACK_INIT_SIZE*sizeof(linkstack));

if(*s==NULL) exit(OVERFLOW);

(*s)-＞next=NULL;

return OK;

}

int Push(linkstack *s,ElemType *x)//入栈操作，将x的数据元素插入栈s中，使x成为新的栈顶元素

{

linkstack *p,*q;

q=s;

p=(linkstack *)malloc(sizeof(linkstack));

if(!p)exit(-1);

p-＞stack=*x;

p-＞next=NULL;

while(q-＞next)

   q=q-＞next;

q-＞next=p;

return OK;

}

int Pop(linkstack *s,ElemType *e)//出栈操作,先将栈s的栈顶结点的值送到e所指向的内存单元，然后删除栈顶结点

{

linkstack *p,*q;

p=s;

if(s-＞next==NULL)return 0;

while(p-＞next)

{

   q=p;

   p=p-＞next;

}

q-＞next=NULL;

*e=p-＞stack;

free(p);

return OK;

}

int Emptystack(linkstack *s)//判断栈是否为空

{

if(s-＞next==NULL)return OK;

else return ERROR;

}

int Gettop(linkstack *s,ElemType *e)

{

linkstack *p,*q;

p=s;

if(s-＞next==NULL)return ERROR;

while(p-＞next)

{

   q=p;

   p=p-＞next;

}

*e=p-＞stack;

return OK;

}

void InitQueue(LinkQueue &Q) //构造一个链式空队列

{

         Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));

         if(!Q.front)exit(OVERFLOW);

         Q.front-＞next=NULL;

}

void EnQueue(LinkQueue &Q,char e) //插入元素为新的队尾元素

{

         QueuePtr p;

         p=(QueuePtr)malloc(sizeof(QNode));

         p-＞data=e;

         p-＞next=NULL;

         Q.rear-＞next=p;

         Q.rear=p;

}

void DeQueue(LinkQueue &Q, char &b) //删除队头元素

{      

         QueuePtr p;

   

         if(Q.front==Q.rear) exit(-1);

         p=Q.front-＞next;

         b=p-＞data;

    Q.front-＞next=p-＞next;

    if(Q.rear==p)  Q.rear=Q.front;

         free(p);

}

QueueEmpty(LinkQueue &Q)

{

         if(Q.front!=Q.rear)return ERROR;

         return OK;

}

void CreateTree(PTree &T)// 操作结果: 构造树T

{

         LinkQueue q;

         QElemType p,t;

         int i=1,j,k;

         char r[MAX_TREE_SIZE],ch; // 临时存放孩子结点数组

         InitQueue(q); // 初始化队列

         printf("请输入根结点(字符型,空格为空): ");

         ch=getchar();

         scanf("%c%*c",&T.nodes[0].data); // 根结点序号为0

         if(T.nodes[0].data!=NULL) // 非空树

         {

                   T.nodes[0].parent=-1; // 根结点无双亲

                   t.name=T.nodes[0].data;

                   t.num=0;

                   EnQueue(q,t.name); // 入队此结点

                   while(i

                   {

                            DeQueue(q,t.name); // 出队一个结点  使用队列是为了保存父节点

                            printf("请按长幼顺序输入结点%c的所有孩子: ",t.name);  //只是输入该节点的孩子节点

                            printf("\n");

                            scanf("%c",&r[0]);

            ch=getchar();//把回车读入，保证下次为读入为字符

                            for(k=1;r[k-1]!=' ';k++)

                            {

                                     scanf("%c",&r[k]);

                                     ch=getchar();

                                    

                            }

                            for(j=0;j

                            {   

                                     if(r[j]==' ')

                                               T.nodes[i].data=NULL;

                                     else

                                     {

                                     T.nodes[i].data=r[j];

                                     T.nodes[i].parent=t.num;

                                     p.name=r[j];                         

                                     p.num=i;

                                     if(r[j]!=' ')  

                                               EnQueue(q,p.name); // 入队此结点

                                     i++;

                                     }

                            }

                   }

                   if(i＞MAX_TREE_SIZE)

                   {

                            printf("结点数超过数组容量\n");

                            exit(OVERFLOW);

                   }

                   T.n=i;

         }

         else

                   T.n=0;

}

CSTree PTreeToCSTree (PTree T,int root)//T存放双亲表示法的树，root为根节点的编号

{                                      

         CSTree ct=(CSTree)malloc(sizeof(CSNode)); //建立子树的根节点

         CSTree child,sibling;//sibling供链结一层的兄弟链表用

    bool isFirst; //是否是第一个孩子的标记

         ct-＞data=T.nodes[root].data;

         ct-＞firstchild=NULL;

         ct-＞nextsibling=NULL;

         isFirst=true;                 

         for(int i=1;i＜=T.n;i++) //查找root的孩子，将他们链成Child_Sibling链表

         {

                   if(T.nodes[i].parent==root)//找到root的孩子

                   {

                            child=PTreeToCSTree(T,i);//建立root孩子的Child_Sibling链表

                            if(isFirst) //若child是root的第一个孩子，则链到root的firstchild

                            {

                                      ct-＞firstchild=child;

                                     isFirst=false;

                                     sibling=ct-＞firstchild;//以后root的孩子都链到sibling链表上

                if(ct-＞firstchild!=NULL) // 有左孩子

                                               ct-＞LTag=Link;

                            }

                            else //若child不是root的第一个孩子，则链到sibling的nextsibling

                            {

                                     sibling-＞nextsibling=child;

                                     sibling=sibling-＞nextsibling;

                if(ct-＞nextsibling) // 有右孩子

                                               ct-＞RTag=Link;

                            }

                   }

         }

         return ct;

}

void PreOrder(CSNode *ct)//先序遍历非递归算法

{

linkstack *S;

CSTree p,q;

q=(CSTree)malloc(sizeof(CSNode));//结构体

Initstack(&S);                  //初始化栈

p=ct;

while(p||!Emptystack(S))

{

   while (p)

   {

        printf("%c",p-＞data);

        

        

                   Push(S,p);    //进栈

                   p=p-＞firstchild;

        

   }

   if(Pop(S,q))     //出栈

    p=q-＞nextsibling;

}

}

void InOrder(CSTree ct)//中序遍历非递归算法

{

linkstack *S;         

CSTree p,q;

q=(CSTree)malloc(sizeof(CSNode));

Initstack(&S);//初始化栈

p=ct;

while (p||!Emptystack(S))

{

   while (p)

   {

    Push(S,p);       //进栈

    p=p-＞firstchild;

   }

   Pop(S,q);         //出栈

   printf("%c",q-＞data);

   p=q-＞nextsibling;

}

}

void PostOrder(CSTree ct)//后序遍历二叉树非递归算法

{

    linkstack *S;

    CSTree p,q;

    char flag;//标记访问过的节点

    Initstack(&S);

    q=(CSTree)malloc(sizeof(CSNode));

    p=ct;

    while (p||!Emptystack(S))

    {

        if(p!=q)

        {

            while(p)                                   //当子树p不为空时 进栈

            {

                Push(S,p);                                             

                if(p-＞firstchild)

                                               p=p-＞firstchild;             //不为空 后移指向左子树

                else p=p-＞nextsibling;           //为空指向 右子树

            }

        }

        if (Emptystack(S))break;                      

        Gettop(S,q);

        if(q-＞nextsibling==p)                  //判断是否遍历过 右子树 如遍历过右子树 说明该遍历根子树

        {

            p=(CSTree)malloc(sizeof(CSNode));

            Pop(S,p);

            printf("%c",p-＞data);

            p=q;

            flag = p-＞data;                    //记录 遍历过的子树

        }

        else

        {

            p=q-＞nextsibling;

                            if(p==NULL)//如果右子树为空，则打印根节点

                            {

                                     Pop(S,q);

                printf("%c",q-＞data);

                            }

            else if(flag==p-＞data)//如果根节点的右子树刚刚访问完成，那么打印根节点

            {

                p=(CSTree)malloc(sizeof(CSNode));

                Pop(S,q);

                printf("%c",q-＞data);

                p=q;

                flag = p-＞data;

            }

        }

     }

}

         void InThreading(CSNode *ct)// 中序遍历进行中序线索化

         {

                   CSNode *p=ct;

                   CSNode *pre=NULL;

                   if(p)

                   {

                            InThreading(p-＞firstchild); // 递归左子树线索化

                            if(!p-＞firstchild) // 没有左孩子

                            {

                                     p-＞LTag=Thread; // 前驱线索

                           

                            }

                            if(!p-＞nextsibling) // 没有右孩子

                            {

                                     p-＞RTag=Thread; // 后继线索

                           

                            }

                            if(pre)

                            {

                                     if(pre-＞RTag==1)

                                               pre-＞nextsibling=p;

                                     if(p-＞LTag==1)

                                               p-＞firstchild=pre;

                            }

                            pre=p;

                            InThreading(p-＞nextsibling); // 递归右子树线索化 pre-＞nextsibling=p; // 前驱右孩子指针指向后继(当前结点p)

                   }

         }

         void main()

         {

                   int k;

                   PTree T;

                   CSTree ct;

                   printf("\n");

                            printf("\n ____________________________________________________________________________ ");

                   printf("  |                            欢迎使用树的多种遍历器                          |");

                   printf("  |                               树与二叉树的转换                             |");

                   printf("  |                                                                            |");

                   printf("  |____________________________________________________________________________| \n");

                   while(1)

                   {

                           

                            printf("\n ");

                            printf("\n                        1.创建树 ");

                            printf("\n                        2.树与二叉树的转换");

                            printf("\n                        3.前序非递归遍历算法 ");

                            printf("\n                        4.中序非递归遍历算法 ");

                            printf("\n                        5.后序非递归遍历算法 ");

                            printf("\n                        6.中序线索化二叉树 ");

                            printf("\n                        7.退出操作\n");

                            printf("请选择你要进行的操作(数字键)：");

                            fflush(stdin);

                            scanf("%d",&k);

                            system("cls");

                            switch(k)

                            {

                            case 1:CreateTree(T);break; //建树

                            case 2:ct=PTreeToCSTree(T,0);break;//转化为二叉树

                            case 3:PreOrder(ct);break;//先序遍历非递归算法

                            case 4:InOrder(ct);break;//中序遍历非递归算法

                            case 5:PostOrder(ct);break;//后序遍历非递归算法

                            case 6:InThreading(ct);break;//线索化

                            case 7:

                                     {

                                               printf("\n\n退出\n\n");

                                               exit(0);

                                               break;

                                     }

                            default:printf("\n序号不对\n");break;

                            }

                   }

         }