数据结构（C语言描述）

Question

设具有n个结点的完全二叉树采用顺序存储结构存储在数值BT[n]中，实现下列算法，编写测试主函数
(1) 实现由该数组创建相应的二叉链存储结构的二叉树；
(2) 编写按层次(同一层自左至右)输出二叉树中所有结点的函数；
(3) 把二叉树用凹入表示法打印出来；

BiTreeNode* BuildBTree(DataType BT[], int n, int i)
{
}
BT[ ] 为所有结点的值所在的数组，n为数组元素个数，i为所创建的树的根节点所在数组的下标

请用C语言将上述要求代码写出

Answer 1

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define DataType int
#define MAXSIZE 1000
typedef struct node{
    DataType data;
    struct node *lchild;
    struct node *rchild;
}BiTreeNode;
DataType BT[MAXSIZE];
BiTreeNode* BuildBTree(DataType BT[], int n, int i)
{
    BiTreeNode * node;
    if(i>=n || (node=(BiTreeNode*)malloc(sizeof(BiTreeNode)))==NULL) return NULL;
    node->data = BT[i];
    node->lchild =  BuildBTree(BT, n, 2*i+1);
    node->rchild =  BuildBTree(BT, n, 2*i+2);
    return node;
}
void PrintLevel(BiTreeNode * bt, int level, int l)
{
    if(!bt) return;
    if(l < level)
        PrintLevel(bt->lchild, level,l+1);
    if(l == level)
        printf("%4d",bt->data);
    if(l < level)
        PrintLevel(bt->rchild, level,l+1);    
}
/* 先序凹入表示法输出, 一般通过前导的空格来凹入 #*/
/*pre，sur分别为前导后续字符,一般前导为空格字符，#*/
void PrintTree(BiTreeNode *bt,char pre,char sur,int depth,int level){
    if(bt==NULL) return ; /*如果为空树，return；*/
    int i=0;  /*先序输出根*/
    while(++i<level) printf("%c%c%c%c",pre,pre,pre,pre);   // 凹入，输出前导字符
    printf("%4d",bt->data);                // 输出当前节点
    while(i++<depth) printf("%c%c%c%c",sur,sur,sur,sur);    // 输出后续字符
    printf("\n");
    /*输出子树*/
    PrintTree(bt->lchild,pre,sur,depth,level+1);
    PrintTree(bt->rchild,pre,sur,depth,level+1);
}
void CTBT(int n)
{   // 建立初始n个节点的完全二叉树
    while(n--) BT[n] = n;
}
int main()
{
    int i,n,depth;
    BiTreeNode *bt;
    scanf("%d",&n);
    CTBT(n);
    bt = BuildBTree(BT, n, 0);
    depth = (int)(log(n)/log(2))+1;
    i=0;
    while(++i<=depth)
    {
  printf("\nThe %dth Level:",i);
        PrintLevel(bt, i,1);
    }
 printf("\n");
    PrintTree(bt,' ','-',depth,1);
 return 0;
}

经调试这个没问题，完成了要求的三个功能

Answer 2

这个我会，可以帮你写！追问

那请你写一写