c语言 二叉树

发布网友 发布时间：2022-04-25 13:58

我来回答

共1个回答

热心网友 时间：2023-10-05 13:30

该题用二叉树的顺序存储结构比较容易实现。

#include <stdio.h>
#include <math.h>
#include <string.h>
char Bitree[100];
void InitTree( )
{
    int i;
    for(i = 0; i < 100; i++)
        Bitree[i] = 0;
}
void Create( ) {  /*创建顺序存储表示的二叉树*/
    char str[10], ch;
    int i, pindex, index, level;
    scanf("%s", str);  /*输入结点数据，包括层次信息*/
    if(strcmp(str, "0") == 0)   /*如果是结束符就结束*/
        return;
    ch = str[strlen(str) - 1];  /*取出结点值*/
    for(level = 0; str[level] == '-'; level++);  /*确定所在层次信息，根结点定为第1层*/
    level = level + 1;
    for(pindex=pow(2,level-1)-1; (pindex>1)&&!Bitree[pindex]; pindex--); /*找双亲编号*/
    if(pindex == 0) index = 1;  /*如果双亲编号为0，则当前结点为根结点*/
    else index = 2 * pindex; /*否则，左孩子编号等于双亲编号乘以2*/
    if(Bitree[index]) index++;  /*如果左孩子已经有了，则当前是双亲的右孩子*/
    Bitree[index] = ch;
    Create( );
}
void PreOrder(int root) {   /*前序遍历*/
    if(Bitree[root] == 0 || Bitree[root] == '*')   /*如果根为空*/
        return;
    printf("%c\t", Bitree[root]);
    PreOrder(root * 2);
    PreOrder(root * 2 + 1);
}
void InOrder(int root) {  /*中序遍历*/
    if(Bitree[root] == 0 || Bitree[root] == '*')
        return;
    InOrder(root * 2);
    printf("%c\t", Bitree[root]);
    InOrder(root * 2 + 1);
}
void PostOrder(int root) {  /*后序遍历*/
    if(Bitree[root] == 0 || Bitree[root] == '*')
        return;
    PostOrder(root * 2);
    PostOrder(root * 2 + 1);
    printf("%c\t", Bitree[root]);
}
void main( ) {
    Create();
    PreOrder(1);
    printf("\n");
    InOrder(1);
    printf("\n");
    PostOrder(1);
    printf("\n");
}

运行结果