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

实验三　二叉树的二叉链表表示及实现 实验项目中文名称：二叉树的二叉链表表示及实现 实验项目英文名称：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,ch); getchar(); if(ch == ) Tp = NULL; else { Tp=(BiTree)malloc(sizeof(BiTNode)); Tp-data=ch; printf(输入%c的左子树：,ch); creatBitree(Tp-lchild); printf(输入%c的右子树：,ch); creatBitree(Tp-rchild); } } 程序框架结构与流程图 遍历：即将树的所有结点访问且仅访问一次。按照根节点位置的不同分为前序遍历，中序遍历，后序遍历。 前序遍历：根节点-左子树-右子树 中序遍历：左子树-根节点-右子树 后序遍历：左子树-右子树-根节点 （1）序遍历二叉树：若二叉树为空，则空操作；否则，先访问根节点-先序遍历左子树-先序遍历右子树。若二叉树为空，则空操作。 （2）中序遍历二叉树：：若二叉树为空，则空操作；否则，中序遍历左子树-访问根节点-中序遍历右子树。若二叉树为空，则空操作。 （3）后序遍历二叉树：：若二叉树为空，则空操作；否则，后序遍历左子树-后序遍历右子树-访问根节点。若二叉树为空，则空操作。 中序遍历流程图： 3、细节设计 程序分为：5大模块。二叉树的建立链式存储结构、前序遍历、中序遍历、后序遍历、主函数 二叉树的建立链式存储结构；首先typedef struct BiTNode：定义二叉树的链式存储结构，此处采用了每个结点中设置三个域， 即值域，*lchild：左指针域和rchild：右指针域。 二叉树的前序遍历；利用二叉链表作为存储结构的前序遍历：先访问根结点，再依次访问左右子树。 二叉树的中序遍历；利用二叉链表作为存储结构的中序遍历：先访问左子数，再访问根结点，最后访问右子树。 二叉树的后序遍历；利用二叉链表作为存储结构的前序遍历：先访问左右子树，再访问根结点。 主函数。 核心算法的设计：二叉树是n个节点的有穷个集合，它或者是空集（n=0），或者同时满足以下两个条件：（1）：有且仅有一个称为根的节点； （2）：其余节点分为两个互不相交的集合T1，T2，并且T1，T2都是二叉树，分别称为根的左子树和右子树。 四、程序源代码 #includestdio.h #includestdlib.h #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){ Sp-sstack = (BiTree*)malloc(STACKINITSIZE * sizeof(BiTree)); if(!Sp-sstack){ exit(0); } Sp-maxsize = STACKINITSIZ