7-1 二叉树的遍历

根据输入构造二叉树，输出该二叉树的先序序列。二叉树共有N个节点，节点编号是1到N。约定1号节点是根节点。

输入格式:

第一行输入整数N。
接下来有N行，依次给出1到N节点的左孩子和右孩子。对于这N行中的每一行，有两个整数。第i（i=1, 2, ..., N）行中，第一个整数指出左孩子的编号，第二个整数指出右孩子的编号。如果整数值为0，表示没有左孩子或右孩子。

输出格式:

输出一行，内容是二叉树的先序序列。节点编号之间用空格隔开，行末有1个空格。

输入样例:

6
2 5
3 4
0 0
0 0
0 6
0 0

输出样例:

1 2 3 4 5 6 

#include<stdio.h>
#include<stdlib.h>
#define M 100
typedef struct TreeNode{
    int val;
    struct TreeNode* left;
    struct TreeNode* right;//因为这里typedef还没有把struct T变成T，所以要TreeNode用不了 
}TreeNode;

TreeNode* creatNode(int val)
{
    TreeNode* BT = (TreeNode*)malloc(sizeof(TreeNode));
    BT->val=val;
    BT->left=NULL;
    BT->right=NULL;
    return BT;
}

TreeNode* constructTree(int N,int** node)//先用整型储存类似于int a; 
{
    //创建所有的节点
    TreeNode* BT[M+1];//已知个数的指向指针的结构数组
     for(int i=1;i<=N;i++){
         BT[i] = creatNode(i);//为什么写i? 不用管只是初始化；可以为任意数 
     }
     for(int i=1;i<=N;i++){
         int left = node[i][0];
         int right = node[i][1];
         if(left!=0){
             BT[i]->left=BT[left];
         }
         if(right!=0){
             BT[i]->right=BT[right];
         }
     }
     return BT[1]; 
     
}

void PreorderTraversal(TreeNode* root){
    
    if(root==NULL){
        return;
    }
    
        printf("%d ",root->val);
        PreorderTraversal(root->left);
        PreorderTraversal(root->right);
    
}

int main()
{
    int N;
    scanf("%d",&N);
    
    int** node = (int**)malloc((N+1)*sizeof(int*));//为什么要N+1； 
    for(int i=1;i<=N;i++){
        node[i] = (int*)malloc(2*sizeof(int));
        scanf("%d %d",&node[i][0],&node[i][1]);// 因为node【i】包括【i】【0】和【i】【1】，所以申请两个int 
        //左0右1； 
    }
    
    TreeNode* root = constructTree(N,node);//返回指针节点，传入节点个数和指向指针的指针数组node 
    //指针当数组用，为什么不直接写二维数组？因为函数传入必须用指针
    PreorderTraversal(root);
    return 0; 
}