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

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

教学难点：

授课内容：

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

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

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);



}