2叉树.c.txt

用顺序存储的方式递归的创建 2插树 并显示2插树 最后遍历2插树

 #include<stdio.h>                                        /*由已知数组构建二叉树*/
#include<malloc.h>
#include<stdlib.h>

struct binode                                            /*定义结构体*/
{
    char data;
    struct binode *lchild,*rchild;
};
                                                         /*宏定义*/
typedef struct binode *bitree;

bitree createbitree(char *a,int i,int l)                 /*递归调用创建二叉树*/
{
    bitree t;
    char ch;

    if(i<l)
    {                                                    /*判断是否存在数据*/
        ch=a[i];
        if(ch==' ')
            t=NULL;
        else                                             /*插入数据*/
        {
            t=(bitree)malloc(sizeof(struct binode));
            t->data=ch;
            t->lchild=createbitree(a,2*i+1,l);           /*对孩子结点数据进行判断*/
            t->rchild=createbitree(a,2*i+2,l);
        }
        return t;
    }
    else
    {
        t=NULL;
        return t;
    }
}

void print(bitree bt,int n)                              /*输出二叉树*/
{
   int i;
   if(bt==NULL)
       return;
   if(bt->rchild!=NULL)
       print(bt->rchild,n+1);
   for(i=0;i<n-1;i++)
       printf("   ");
   if(n>=1)
        printf(" --"); printf("%c\n",bt->data);
   if(bt->lchild!=NULL)
        print(bt->lchild,n+1);
}

void preOrder(bitree t)                                 /*先根序列遍历,递归访问*/
{
    if(t==NULL) return;
    printf("%c ",t->data);
    preOrder(t->lchild);
    preOrder(t->rchild);
}
void inOrder(bitree t)
{                                                      /*对称序列遍历*/
    if(t==NULL) return;
    inOrder(t->lchild);
    printf("%c ",t->data);
    inOrder(t->rchild);
}

void postOrder(bitree t)                               /*后根序列遍历*/
{
    if(t==NULL) return;
    postOrder(t->lchild);
    postOrder(t->rchild);
    printf("%c ",t->data);
}

void main()                                            /*主函数*/
{   char a[30]={'a','b','c','d','e','f','g',' ',' ','h','i'};
                                                       /*存放二叉树数据的数组*/
                                                       /*如果为空则表示不存在孩子结点bitree bt;
    int i=0;
    int l=0;
 for(;a[l]!='\0';l++);                              /*提取数组的长度*/
 bt=createbitree(a,i,l);                            /*构建二叉树*/
    print(bt,0);
  printf("\npreorder:\n");                           /*先根序列遍历*/
       preOrder(bt);
  printf("\ninpreorder:\n");                         /*对称序列遍历*/
       inOrder(bt);
  printf("\npostOrder:\n");                          /*后根序列遍历*/    postOrder(bt);

    printf("\n"); getchar();
}