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

预备知识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;

CreateBiTree(T->lchild);

CreateBiTree(T->rchild);}returnOK;}AB

C

D

ABCD上页算法执行过程举例如下:ATBCD^^^^^第8次课二叉树的创建和遍历一、实验目的：了解二叉树存储结构的创建方法（二叉链表）了解二叉树遍历的三种方法（先序，中序和后序），知道其程序实现了解在二叉链表结构下，一些常用递归程序的实现方法引例#include<stdio.h>#include<stdlib.h>#defineok1#defineerror0#defineOVERFLOW-1typedef

intstatus;typedefcharElemType;typedef

struct

BiTNode{

ElemTypedata;

struct

BiTNode*lchild,*rchild;}BiTNode,*BiTree;ABCDEFGFILE*fp;statusCreateBiTree(BiTree&T);statusPreOrderTraverse(BiTree

T,status(*visit)(ElemType));statusShow(ElemTypee);main(){

BiTreeT;

if((fp=fopen("data.txt","r"))==NULL){

printf("Can'topenfile!\n");exit(0);}

if(CreateBiTree(T)){fclose(fp);printf("\n

成功创建了二叉树!\n");}

printf("先序遍历序列是:");

if(PreOrderTraverse(T,Show))printf("\n");return(1);}statusCreateBiTree(BiTree&T){

ElemType

ch;

fscanf(fp,"%c",&ch);

if(ch=='')T=NULL;else{

if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T->data=ch;

if(CreateBiTree(T->lchild))

if(CreateBiTree(T->rchild))return(ok);}

return(ok);}statusPreOrderTraverse(BiTree

T,status(*visit)(ElemType)){

if(T){if((*visit)(T->data))if(PreOrderTraverse(T->lchild,visit))if(PreOrderTraverse(T->rchild,visit))returnok;returnerror;}elsereturnok;}statusShow(ElemTypee){

printf("%c",e);

return(ok);}二、实验内容：