數(shù)據(jù)結(jié)構(gòu)實驗第8次課二叉樹的創(chuàng)建和遍歷

預(yù)備知識1.利用擴展的先序序列創(chuàng)建二叉樹（二叉鏈表結(jié)構(gòu)）先序序列：AB注意到：字符后的第一個字符為左子樹的根；若字符為Ф，則表明子樹為空。關(guān)鍵問題：確定根遞歸：建立根結(jié)點，創(chuàng)建左子樹，創(chuàng)建右子樹擴展的先序序列：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上頁算法執(zhí)行過程舉例如下:ATBCD^^^^^第8次課二叉樹的創(chuàng)建和遍歷一、實驗?zāi)康模毫私舛鏄浯鎯Y(jié)構(gòu)的創(chuàng)建方法（二叉鏈表）了解二叉樹遍歷的三種方法（先序，中序和后序），知道其程序?qū)崿F(xiàn)了解在二叉鏈表結(jié)構(gòu)下，一些常用遞歸程序的實現(xiàn)方法引例#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

成功創(chuàng)建了二叉樹!\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);}二、實驗內(nèi)容：