首页 / 软件开发 / 数据结构与算法 / 数据结构教程 第二十七课 实验六 二叉树实验

数据结构教程 第二十七课 实验六 二叉树实验2007-05-16教学目的： 掌握二叉树的链式存储结构

教学重点： 二叉树的链式存储实现方法

教学难点：

授课内容：

生成如下二叉树，并得出三种遍历结果：

一、二叉树的链式存储结构表示

typedef struct BiTNode{

TElemType data;

struct BitNode *lchild,*rchild;

}BiTNode,*BiTree;

二、二叉树的链式存储算法实现

CreateBiTree（&T,definition）;

InsertChild（T,p,LR,c）;

三、二叉树的递归法遍历

PreOrderTraverse（T,Visit（））;

InOrderTraverse（T,Visit（））;

PostOrderTraverse（T,Visit（））;

示例源程序

#include <alloc.h>#define ERROR 0;#define OK 1;typedef int ElemType;typedef struct BinaryTree{ElemType data;struct BinaryTree *l;struct BinaryTree *r;}*BiTree,BiNode;BiNode * new（）{return（ （BiNode *）malloc（sizeof（BiNode）） ）;}CreateSubTree（BiTree *T,ElemType *all,int i）{if （（all[i]==0）||i>16）{*T=NULL;return OK;}*T=new（）;if（*T==NULL） return ERROR;（*T）->data=all[i];CreateSubTree（&（（*T）->l）,all,2*i）;CreateSubTree（&（（*T）->r）,all,2*i+1）;}CreateBiTree（BiTree *T）{ElemType all[16]={0,1,2,3,0,0,4,5,0,0,0,0,6,0,0,0,};CreateSubTree（T,all,1）;}printelem（ElemType d）{printf（"%d
",d）;}PreOrderTraverse（BiTree T,int （*Visit）（ElemType d））{if（T）{if（Visit（T->data））if（PreOrderTraverse（T->l,Visit））if（PreOrderTraverse（T->r,Visit）） return OK;return ERROR;} elsereturn OK;}main（）{BiTree root;CreateBiTree（&root）;PreOrderTraverse（root,printelem）;}