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

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

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

教学难点：

授课内容：

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

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

    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==0)||i>16)
        {
          *T=NULL;
          return OK;
        }
      *T=new();
      if(*T==NULL) return ERROR;
      (*T)->data=all;
      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);

    }