二叉树的二叉链表表示及实现实验报告

实验项目中文名称：二叉树的二叉链表表示及实现

实验项目英文名称：Definition and Implementation of Binary Tree 实验学时：2学时 一、实验目的

1、深入了解二叉树的特性，掌握二叉树的二叉链表表示及实现方法。 2、掌握二叉树的递归遍历算法。 二、实验内容

1、编写函数，创建一棵二叉树；

2、编写函数，用递归算法分别求二叉树的各种遍历序列； 3、编写函数，用非递归算法求二叉树的中序遍历序列。

4、编写函数，用非递归算法求二叉树的先序和后序遍历序列。（选做） 三、设计概要

1、核心数据结构 二叉树的链式存储结构表示 typedef struct BiTNode{

ElemType data;

struct BiTNode *lchild, *rchild; } BiTNode; 结构示意图：

2,二叉树的链式存储算法实现 Status CreateBiTree(BiTree * Tp){

}

//创建一棵二叉树； char ch; scanf(\"%c\ getchar(); if(ch ==' ') Tp = NULL; else {

Tp=(BiTree)malloc(sizeof(BiTNode)); Tp->data=ch;

printf(\"输入%c的左子树：\

creatBitree(Tp->lchild);

printf(\"输入%c的右子树：\ creatBitree(Tp->rchild); }

程序框架结构与流程图

遍历：即将树的所有结点访问且仅访问一次。按照根节点位置的不同分为前序遍历，中序遍历，后序遍历。

前序遍历：根节点->左子树->右子树 中序遍历：左子树->根节点->右子树 后序遍历：左子树->右子树->根节点

（1）序遍历二叉树：若二叉树为空，则空操作；否则，先访问根节点->先序遍历左子树->先序遍历右子树。若二叉树为空，则空操作。

（2）中序遍历二叉树：：若二叉树为空，则空操作；否则，中序遍历左子树->访问根节点->中序遍历右子树。若二叉树为空，则空操作。

（3）后序遍历二叉树：：若二叉树为空，则空操作；否则，后序遍历左子树->后序遍历右子树->访问根节点。若二叉树为空，则空操作。

中序遍历流程图：

3、细节设计

程序分为：5大模块。二叉树的建立链式存储结构、前序遍历、中序遍历、后序遍历、主函数

二叉树的建立链式存储结构；首先typedef struct BiTNode：定义二叉树的链式存储结构，此处采用了每个结点中设置三个域， 即值域，*lchild：左指针域和rchild：右指针域。

二叉树的前序遍历；利用二叉链表作为存储结构的前序遍历：先访问根结点，再依次访问左右子树。

二叉树的中序遍历；利用二叉链表作为存储结构的中序遍历：先访问左子数，再访问根结点，最后访问右子树。

二叉树的后序遍历；利用二叉链表作为存储结构的前序遍历：先访问左右子树，再访问根结点。

主函数。

核心算法的设计：二叉树是n个节点的有穷个集合，它或者是空集（n=0），或者同时满足以下两个条件：（1）：有且仅有一个称为根的节点； （2）：其余节点分为两个互不相交的集合T1，T2，并且T1，T2都是二叉树，分别称为根的左子树和右子树。

四、程序源代码 #include #include #define OK 1 #define ERROR 0

#define STACKINITSIZE 20 #define INCSIZE 10 typedef char ElemType;

typedef struct BiTNode{

ElemType data;

struct BiTNode *lchild, *rchild;

} BiTNode;

typedef BiTNode* BiTree;

typedef int Status;

typedef struct BiTNodeStack{

BiTree *sstack; int top, maxsize;

} BiTNodeStack;

void InitStack(BiTNodeStack * Sp){ }

void DestroyStack(BiTNodeStack * Sp){ }

free(Sp->sstack); Sp->maxsize = 0; Sp->top = 0;

Sp->sstack = (BiTree*)malloc(STACKINITSIZE * sizeof(BiTree)); if(!Sp->sstack){ }

Sp->maxsize = STACKINITSIZE; Sp->top = 0;

exit(0);

Status Push(BiTNodeStack * Sp, BiTree e){ }

Status Pop(BiTNodeStack * Sp, BiTree *ep){ }

Status CreateBiTree(BiTree * Tp){

//创建一棵二叉树； if(0 == Sp->top){ } else{ } return OK;

Sp->top--;

*ep = Sp->sstack[Sp->top]; return ERROR; return OK; BiTree* p;

if(Sp->maxsize == Sp->top){ }

Sp->sstack[Sp->top] = e; Sp->top++;

p = (BiTree*)realloc(Sp->sstack, (Sp->maxsize + INCSIZE) * sizeof(BiTree)); if(!p){ }

Sp->maxsize += INCSIZE; Sp->sstack = p;

exit(0);

typedef struct BiTNode

{ char data;

struct BiTNode *Lchild; struct BiTNode *Rchild; }BiTNode,*BiTree; }

void DestroyBiTree(BiTree * Tp){ if(*Tp){ DestroyBiTree(&((*Tp)->lchild)); DestroyBiTree(&((*Tp)->rchild)); free(*Tp); *Tp = NULL; }

}

Status PreOrderTranverse_DG(BiTree T){

//递归先序遍历二叉树 void PreorderTraverse(BTNode *T) { if (T!=NULL)

{ visit(T->data) ; /* 访问根结点PreorderTraverse(T->Lchild) ; PreorderTraverse(T->Rchild) ; } } }

Status InOrderTranverse_DG(BiTree T){

//递归中序遍历二叉树

void InorderTraverse(BTNode *T) { if (T!=NULL)

{ InorderTraverse(T->Lchild) ;

*/ visit(T->data) ; /* 访问根结点 */ InorderTraverse(T->Rchild) ; } } }

Status PostOrderTranverse_DG(BiTree T){

//递归后序遍历二叉树

void InorderTraverse(BTNode *T) { if (T!=NULL)

{ InorderTraverse(T->Lchild) ; InorderTraverse(T->Rchild) ;

visit(T->data) ; /* 访问根结点 */ } } }

Status PreOrderTranverse_FDG(BiTree T){ }

Status InOrderTranverse_FDG(BiTree T){

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

printf(\"略。\");//非递归先序遍历二叉树，选做。如果做请删除本行代码。 return OK;

#define MAX_NODE 50

void InorderTraverse( BTNode *T) { BTNode *Stack[MAX_NODE] ,*p=T ; int top=0 , bool=1 ;

if (T==NULL) printf(“ Binary Tree is Empty!\\n”) ; else { do

{ while (p!=NULL)

{ stack[++top]=p ; p=p->Lchild ; }

if (top==0) bool=0 ; else { p=stack[top] ; top-- ;

visit( p->data ) ; p=p->Rchild ; } } while (bool!=0) ; } }

return OK; }

Status PostOrderTranverse_FDG(BiTree T){ }

int main(){

BiTree mytree;

printf(\"请按照先序输入二叉树，用空格表示子树为空。\\n\"); CreateBiTree(&mytree); printf(\"递归遍历法：\\n\"); printf(\"先序：\");

PreOrderTranverse_DG(mytree); printf(\"\\n中序：\");

InOrderTranverse_DG(mytree); printf(\"\\n后序：\");

PostOrderTranverse_DG(mytree);

printf(\"\\n**********************************************************printf(\"略。\");//非递归后序遍历二叉树，选做。如果做请删除本行代码。

return OK;

**\\n非递归遍历法：\\n\");

printf(\"先序：\");

PreOrderTranverse_FDG(mytree);

}

printf(\"\\n中序：\");

InOrderTranverse_FDG(mytree); printf(\"\\n后序：\");

PostOrderTranverse_FDG(mytree); printf(\"\\n\");

DestroyBiTree(&mytree); return 0;

五、实验过程

1、实验步骤及截图

2、遇到的问题及解决方法

遇到的问题：本程序通过分别调用先序遍历、中序遍历以及后序遍历函数对二叉树中的元素进行遍历,整个程序基本满足实验要求,但是在一些细节问题上面还是存在缺陷,比如大小写字母不同也会导致程序无法运行,这就需要我们在处理问题上认真细致,还有就是程序并不是很完善,总之,我会在今后更加努力,是程序更完美。 六、心得体会

首先，我的C语言学的不是很好，因此做这样一个课程设计感觉有点吃力，

还好我不断的看书，翻阅资料，询问同学，上网搜索，总算像模像样地把这个程序编的能运行了。功夫不负有心人。

其次，这次编程是我更多地理解掌握了二叉树的遍历。对大一时学过的知识有了很好的巩固。困难还是很多的，比如初次运行的时候，好几十个错误，当时真的感到非常崩溃。幸亏我没有放弃，才最终完成。长舒一口气。

最后，通过这次编程，不仅仅考察了我对知识的掌握，更重要的是锻炼了我的思维能力和耐心，在最困难的时候没有放弃，今天才能如此舒心。