[資結] Expression Tree

答案是14

說明
輸入給予下列資訊：
第一行會給定一個整數n，代表節點的個數。 n 最多不超過100,000。
接下來會有 n 行，每一行代表一個節點的資訊，其內容如下：
第一個數字代表節點的ID，分別是1~n不重複(不一定照順序)。
接下來會有一個字串，可能會是SUM, MIN, MAX, VAL 四種其中之一，分別代表總和、最小值、最大值、或是Leaf node。
接下來會是一個數字，代表此節點的parent ID。
如果這個節點是Leaf node (即第二個字串是VAL)，該行最後會有一個數字代表此節點的值。
(parent 是 -1 表示該node是root)
output用%d即可。

input
13
1 SUM 2
2 MAX -1
3 SUM 2
4 MAX 3
5 VAL 1 3
6 MIN 1
7 VAL 1 2
8 VAL 3 6
9 VAL 6 4
10 VAL 6 2
11 VAL 4 5
12 VAL 4 3
13 VAL 4 8

output
14

解法：
因為不是binary tree。
所以做left child right sibling。
再做traverse即可。

太久沒寫tree，我的指標又在飄了 lol~

#include <stdio.h>
#include <string.h>

#define MAXNODE 100001

typedef struct node {
    char data[4];
    int value;
    struct node *left;
    struct node *right;
} Node;

void init(Node *nodes, int n);
void addchild(Node *node, Node *child);
int traverse(Node *node);
int sum(Node *node);
int max(Node *node);
int min(Node *node);

int main(void)
{
    int n, i, p, root, index;
    Node nodes[MAXNODE];

    scanf("%d", &n);
    init(nodes, n);
    for (i = 0; i < n; i++) {
        // input
        scanf("%d", &index);
        scanf("%s %d", nodes[index].data, &p);
        if (strcmp(nodes[index].data, "VAL") == 0) {
            scanf("%d", &nodes[index].value);
        }

        if (p == -1)
            root = index;
        else
            addchild(&nodes[p], &nodes[index]);
    }
    printf("%d\n", traverse(&nodes[root]));

    return 0;
}

void init(Node *nodes, int n)
{
    int i;
    for (i = 1; i <= n; i++) {
        nodes[i].left = nodes[i].right = NULL;
    }
}

void addchild(Node *node, Node *child)
{
    if (node->left == NULL) {
        node->left = child;
        return;
    }
    else
        node = node->left;
    while (node->right != NULL)
        node = node->right;
    node->right = child;
}

int traverse(Node *node)
{
    // no child is leaf
    if (node->left == NULL) {
        return node->value;
    }

    if (strcmp(node->data, "SUM") == 0) {
        return sum(node->left);
    }
    else if (strcmp(node->data, "MAX") == 0) {
        return max(node->left);
    }
    else if (strcmp(node->data, "MIN") == 0) {
        return min(node->left);
    }
}

int sum(Node *node)
{
    int sum = traverse(node);

    while (node->right != NULL) {
        sum += traverse(node->right);
        node = node->right;
    }
    return sum;
}

int max(Node *node)
{
    int max = traverse(node);
    int temp;

    while (node->right != NULL) {
        temp = traverse(node->right);
        if (max < temp)
            max = temp;
        node = node->right;
    }
    return max;
}

int min(Node *node)
{
    int min = traverse(node);
    int temp;

    while (node->right != NULL) {
        temp = traverse(node->right);
        if (min > temp)
            min = temp;
        node = node->right;
    }
    return min;
}