站内搜索

数据结构教程 第二十七课 实验六 二叉树实验

教学目的: 掌握二叉树的链式存储结构

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

教学难点:

授课内容:

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

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

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/n",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;  } else  return OK;}main(){  BiTree root;  CreateBiTree(&root);  PreOrderTraverse(root,printelem);}

 

  • 上一篇:数据结构教程 第二十八课 图的存储结构
  • 下一篇:数据结构教程 第二十六课 图的定义与术语