实验报告二叉树.docx

实验报告二叉树

篇一：二叉树实验报告

山东工商学院

《数据结构》实验指导及报告书

XX/XX学年

姓名：学号：班级：指导教师：

Xx学院

XX年11月25日

第一学期

实验三二叉树

一、实验目的

一、把握二叉树的大体特性

二、把握二叉树的先序、中序、后序的递归遍历算法3、明白得二叉树的先序、中序、后序的非递归遍历算法

4、通过求二叉树的深度、叶子结点数和层序遍历等算法，明白得二叉树的大体特性

二、实验预习

说明以下概念

一、二叉树：是另一种树型结构，它的特点是每一个结点最多只有两棵子树，而且二叉树有左右之分，第二序不能任意倒置。二、递归遍历：

一、非递归遍历：

4、层序遍历：

三、实验内容和要求

一、阅读并运行下面程序，依照输入写出运行结果，并画出二叉树的形态。#include#include

#defineMAX20

typedefstructBTNode{/*节点结构声明*/

chardata;/*节点数据*/structBTNode*lchild;

structBTNode*rchild;/*指针*/}*BiTree;

BiTreecreateBiTree(BiTreet){/*先序遍历创建二叉树*/chars;

printf(\npleaseinputdata:(exitfor#));s=getche();

if(s==#){t=NULL;returnt;}

t=(BiTree)malloc(sizeof(structBTNode));

if(t==NULL){printf(Memoryallocfailure!);exit(0);}t-data=s;

t-lchild=createBiTree(t-lchild);/*递归成立左子树*/t-rchild=createBiTree(t-rchild);/*递归成立右子树*/returnt;}

voidPreOrder(BiTreep){/*先序遍历二叉树*/if(p!=NULL){

printf(%c,

p-data);PreOrder(p-lchild);PreOrder(p-rchild);}}

voidInOrder(BiTreep){/*中序遍历二叉树*/if(p!=NULL){

InOrder(p-lchild);printf(%c,p-data);InOrder(p-rchild);}}

voidPostOrder(BiTreep){/*后序遍历二叉树*/if(p!=NULL){

PostOrder(p-lchild);PostOrder(p-rchild);printf(%c,p-data);}}

voidPreorder_n(BiTreep){/*先序遍历的非递归算法*/BiTreestack[MAX],q;inttop=0,i;

for(i=0;iwhile(q!=NULL){

printf(%c,q-data);

if(q-rchild!=NULL)stack[top++]=q-rchild;if(q-lchild!=NULL)q=q-lchild;else

if(top0)q=stack[--top];elseq=NULL;}}

voidrelease(BiTreet){/*释放二叉树空间*/if(t!=NULL){

release(t-lchild);release(t-rchild);

free(t);}}

intmain(){

BiTreet=NULL;inte,m,g;

t=createBiTree(t);

printf(\n\nPreOrderthetreeis:);PreOrder(t);

printf(\n\nInOrderthetreeis:);InOrder(t);

printf(\n\nPostOrderthetreeis:);PostOrder(t);

printf(\n\n先序遍历序列（非递归）:);

Preorder_n(t);

printf(\n\n输出结点总数:);e=PreOrder_num(t);printf(%d,e);

printf(\n\n输出树的深度: