2030: 树的中序遍历（C语言）

解题思路:

注意事项:

参考代码:

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

typedef struct node {
    int data;                       // 数据域
    struct node *father;            // 父结点指针
    struct node *left, *right;      // 左右孩子结点指针
} Node;

// 创建一个结点
Node *createNode(int data) {
    Node *node = (Node *) malloc(sizeof(Node));
    node->father = NULL;
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 递归中序遍历树结点
void inorderTransversal(Node *node) {
    if (node == NULL) {
        return;
    }

    inorderTransversal(node->left);
    printf("%d ", node->data);
    inorderTransversal(node->right);
}

int main() {
    int n;
    scanf("%d", &n);

    // 存放树中所有结点的数组
    Node *nodes[n + 1];
    for (int i = 0; i < n + 1; i++) {
        nodes[i] = NULL;
    }

    int li, ri;
    for (int i = 1; i <= n; i++) {
        // 当前的第i个结点为空
        if (nodes[i] == NULL) {
            nodes[i] = createNode(i);
        }

        scanf("%d %d", &li, &ri);

        // 左结点不是0，且为空
        if (li != 0 && nodes[li] == NULL) {
            nodes[li] = createNode(li);
            nodes[li]->father = nodes[i];           // 设置父结点指针，方便往上查找根节点
        }

        // 右结点不是0，且为空
        if (ri != 0 && nodes[ri] == NULL) {
            nodes[ri] = createNode(ri);
            nodes[ri]->father = nodes[i];
        }

        // 设置当前结点的左右孩子结点
        nodes[i]->left = nodes[li];
        nodes[i]->right = nodes[ri];
    }

    // 获取二叉树中任一结点，找到树的根节点
    Node *root = nodes[1];
    while (root->father != NULL) {
        root = root->father;
    }

    // 递归中序遍历
    inorderTransversal(root);

    // 释放树中所有结点
    for (int i = 0; i < n + 1; i++) {
        free(nodes[i]);
    }
    return 0;
}