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

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

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

教学难点：

授课内容：

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

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

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

}