erchashu.c

假设自上而下按层次

#include <stdio.h>
#include <stdlib.h>


#define MAX 100
struct tree
{
    int key;
    struct tree* left;
    struct tree* right;
};
typedef struct tree treeT ;

typedef struct tree * pTreeT;

pTreeT BT_Insert(int data[],int fath[],int i,pTreeT p[])
{
    struct tree * pNode = (struct tree * ) malloc(sizeof(struct tree));



    pNode->key   = data[i];

    pNode->left  = NULL;
    pNode->right = NULL;
    if (fath[i]<0)
        p[-fath[i]]->left=pNode;
    else
        p[fath[i]]->right=pNode;
    return pNode;
}


void BT_PreOrder(pTreeT root)
{
    if (NULL != root)
    {
        printf("%d ",root->key);
        BT_PreOrder(root->left);
        BT_PreOrder(root->right);
    }
}


void BT_InOrder(pTreeT root)
{
    if (NULL != root)
    {
        BT_InOrder(root->left);
        printf("%d ",root->key);//visit(root);
        BT_InOrder(root->right);
    }
}

void BT_PostOrder(pTreeT root)
{
    if (NULL != root)
    {
        BT_PostOrder(root->left);
        BT_PostOrder(root->right);
        printf("%d ",root->key);//visit(root);
    }
}

//pTreeT BT_Insert(int data[],int fath[],int i,pTreeT p[]);

int main()
{
    int fath[MAX];
    int data[MAX];
    char lr;
    pTreeT p[MAX],root;
    int i=2,n,j;

    printf("请输入二叉树的根节点:\n");
    scanf("%d",&data[1]);
    printf("请输入三元组建立二叉树(输入0结束):\n");
    pTreeT pNode = (pTreeT) malloc(sizeof(treeT));
    pNode->key   = data[1];

    pNode->left  = NULL;
    pNode->right = NULL;
    p[data[1]]=pNode;

    scanf("%d",&data[i]);

    while (data[i]!=0)
    {
        scanf("%d %c",&fath[i],&lr);
        if (lr=='L')
            fath[i]=-fath[i];
        i++;
        scanf("%d",&data[i]);
    }

    n=i;
    for (i=2;i<n;i++)
    {
        p[i]=BT_Insert(data,fath,i,p);
    }
    root=p[data[1]];
    printf("先根遍历为:");
    BT_PreOrder(root);
    printf("\n");
    printf("中根遍历为:");
    BT_InOrder(root);
    printf("\n");
    printf("后根遍历为:");
    BT_PostOrder(root);
    printf("\n");
    printf("层序遍历为:");
    for (j=1;j<n;j++)
        printf("%d ",data[j]);
    return 0;
}