二叉树的建立和遍历报告

班级：09级计科（1）班 姓名:林有龙 学号：22号

数据结构程序设计报告（二）

一、设计题目：

二叉树的建立和遍历

二、问题描述：

建立二叉树并对二叉树进行先序、中序、后序遍历，输入任意二叉树就输出其先序、中序、后序遍历。

三、结构设计：

四、算法分析

1、数据结构的定义

二叉树是另一种树型结构，它的特点是每个结点至多只有两棵子树，并且二叉树有左右之分，其次序不能任意颠倒。二叉树的存储结构分为顺序存储和链式存储结构，本次我们主要应用二叉树的二叉链表的方式存储方式，实验中首先必须对二叉树的数据结构进行定义，即定义一个二叉链表，其中其数据成员包括节点的数据、左子树的指针、右子树的指针。

2、二叉树的建立

在实验开始前我们要建立一个以先序形式的二叉树，先序的二叉树就是先访问根结点，然后访问左子树，最后访问右子树的遍历。

3、二叉树的遍历

二叉树的遍历分为先序、中序、后序，需先取遍历的节点的数据存入队列中，然后输出。

4、程序中要的函数的介绍

（1）二叉树的类型定义

typedef char TElemType;

typedef struct BiTNode

{ TElemType data;

struct BiTNode *lchild,*rchild;

} BiTNode, *BiTree;

（2）定义链式队列类型

typedef struct QNode

{ ElemType data;

struct QNode *next;

} QNode, *QueuePtr;

typedef struct

{ QueuePtr front;

QueuePtr rear;

} LinkQueue;

（3）初始化链式队列的函数

void InitQueue(LinkQueue *Q)

（4）销毁链式队列、判断空队列

void DestroyQueue(LinkQueue *Q)

int QueueEmpty(LinkQueue Q)

（5）主函数

main()

{ BiTree T; int n=0;

printf("请输入树的值:"); CreateBiTree(&T);

printf("\n先序遍历为:"); PreOrderTraverse(T);

printf("\n中序遍历为:"); InOrderTraverse(T);

printf("\n后序遍历为:"); PostOrderTraverse(T);

printf("\n层次遍历为:"); LevelOrderTraverse(T);

printf("\n节点数为%d\n",BiTreeDepth(T));

}

5、实验代码

#include "stdio.h"

#include "stdlib.h"

typedef char TElemType;

typedef struct BiTNode

{ TElemType data;

struct BiTNode *lchild,*rchild;

} BiTNode, *BiTree;

typedef BiTree ElemType;

typedef struct QNode

{ ElemType data;

struct QNode *next;

} QNode, *QueuePtr;

typedef struct

{ QueuePtr front;

QueuePtr rear;

} LinkQueue;

void InitQueue(LinkQueue *Q)

{ Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));

if (!(Q->front)) exit(0);

Q->front->next=NULL; }

void DestroyQueue(LinkQueue *Q)

{ while (Q->front)

{ Q->rear=Q->front->next;

free(Q->front);

Q->front=Q->rear; }

}

int QueueEmpty(LinkQueue Q)

{ if (Q.front==Q.rear)

return 1;

else

return 0; }

void EnQueue(LinkQueue *Q, ElemType e)

{ QueuePtr p;

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

if (!p) exit(0);

p->data=e; p->next=NULL;

Q->rear->next=p;

Q->rear=p; }

void DeQueue(LinkQueue *Q, ElemType *e)

{ QueuePtr p;

if (Q->front!=Q->rear)

{ p=Q->front->next;

*e=p->data;

Q->front->next=p->next;

if (Q->rear==p) Q->rear=Q->front;

free(p); }

}

void CreateBiTree(BiTree *T)

{ char ch;

scanf("%c",&ch);

if (ch==' ')

*T=NULL;

else

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

(*T)->data=ch;

CreateBiTree(&(*T)->lchild);

CreateBiTree(&(*T)->rchild); }

}

void PreOrderTraverse(BiTree T)

{ if (T)

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

PreOrderTraverse(T->lchild);

PreOrderTraverse(T->rchild); }

}

void InOrderTraverse(BiTree T)

{ if (T)

{InOrderTraverse(T->lchild);

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

InOrderTraverse(T->rchild); }

}

void PostOrderTraverse(BiTree T)

{ if (T)

{PostOrderTraverse(T->lchild);

PostOrderTraverse(T->rchild);

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

}

void LevelOrderTraverse(BiTree T)

{ LinkQueue Q; BiTree p;

InitQueue(&Q);

if (T) EnQueue(&Q, T);

while (!QueueEmpty(Q))

{ DeQueue(&Q, &p);

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

if (p->lchild) EnQueue(&Q, p->lchild);

if (p->rchild) EnQueue(&Q, p->rchild); }

DestroyQueue(&Q);

}

int BiTreeDepth(BiTree T)

{ int h1,h2;

if (T==NULL)

return 0;

else

{ h1=BiTreeDepth(T->lchild);

h2=BiTreeDepth(T->rchild);

if (h1>h2)

return h1+1;

else

return h2+1; }

}

main()

{ BiTree T; int n=0;

printf("请输入树的值:"); CreateBiTree(&T);

printf("\n先序遍历为:"); PreOrderTraverse(T);

printf("\n中序遍历为:"); InOrderTraverse(T);

printf("\n后序遍历为:"); PostOrderTraverse(T);

printf("\n层次遍历为:"); LevelOrderTraverse(T);

printf("\n节点数为%d\n",BiTreeDepth(T));

}

6、程序运行结果

五、实验总结

通过本次实验，加深了对建立二叉树、二叉树遍历的理解，遍历形式有先序遍历、中序遍历、后序遍历、层次遍历、还有深度的求解等，在本次实验中也遇到了很大的问题，首先对二叉数树的建立和怎样让二叉树进入队列中的理解是个难点，还有就是在对先序、中序、后序遍历的函数的理解上也存在相当大的问题，但是在同学和网上搜资料后都一一的解决，总体来说这次实验很成功。