数据结构实验第8次课二叉树的创建和遍历.ppt

《数据结构实验第8次课二叉树的创建和遍历.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、预备知识1.利用扩展的先序序列创建二叉树（二叉链表结构）先序序列：AB注意到：字符后的第一个字符为左子树的根；若字符为Ф，则表明子树为空。关键问题：确定根递归：建立根结点，创建左子树，创建右子树扩展的先序序列：ABCФФDEФGФФFФФФAФBФФABФФФStatusCreateBiTree(BiTree&T){scanf(&ch);if(ch==’‘)T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T->data=ch;CreateB

2、iTree(T->lchild);CreateBiTree(T->rchild);}returnOK;}ABCDABCD上页算法执行过程举例如下:ATBCD^^^^^第8次课二叉树的创建和遍历一、实验目的：了解二叉树存储结构的创建方法（二叉链表）了解二叉树遍历的三种方法（先序，中序和后序），知道其程序实现了解在二叉链表结构下，一些常用递归程序的实现方法引例#include#include#defineok1#defineerror0#defineOVERFLOW-1typedefintsta

3、tus;typedefcharElemType;typedefstructBiTNode{ElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;ABCDEFGFILE*fp;statusCreateBiTree(BiTree&T);statusPreOrderTraverse(BiTreeT,status(*visit)(ElemType));statusShow(ElemTypee);main(){BiTreeT;if((fp=fopen("data.txt","

4、r"))==NULL){printf("Can'topenfile!");exit(0);}if(CreateBiTree(T)){fclose(fp);printf("成功创建了二叉树!");}printf("先序遍历序列是:");if(PreOrderTraverse(T,Show))printf("");return(1);}statusCreateBiTree(BiTree&T){ElemTypech;fscanf(fp,"%c",&ch);if(ch=='')T=NULL;else{if(!(T=(Bi

5、TNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T->data=ch;if(CreateBiTree(T->lchild))if(CreateBiTree(T->rchild))return(ok);}return(ok);}statusPreOrderTraverse(BiTreeT,status(*visit)(ElemType)){if(T){if((*visit)(T->data))if(PreOrderTraverse(T->lchild,visit))if(PreOrde

6、rTraverse(T->rchild,visit))returnok;returnerror;}elsereturnok;}statusShow(ElemTypee){printf("%c",e);return(ok);}二、实验内容：1.在引例的基础上，实现中序和后序遍历2.编一个函数，查找二叉树上是否有某个元素测试数据：E,J3.基于递归思想，编制两个函数，求二叉树的叶子节点数和二叉树的深度