Time limit: 5000ms
Memory limit: 256mb

Description:

A binary tree is a finite set of nodes that is either empty or consists of a root and two disjoint binary trees called the left subtree and the right subtree. Given the BinTree ADT, you need to implement the preorder and postorder traversal of a binary tree. Complete the following program.

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

// begin the definition of ADT BinTree
typedef void* element;
typedef void* Binary_Tree;
typedef Binary_Tree BinTree;
BinTree Create();
bool IsEmpty(BinTree tree);
BinTree MakeBT(BinTree bt1, element item, BinTree bt2);
BinTree Lchild(BinTree bt);
BinTree Rchild(BinTree bt);
element Data(BinTree bt);
// end of the definition

// helper functions
BinTree Read();
void print(element);

/* Note that you can only edit the source code between the comments "BEGIN
 * YOUR IMPLEMENTATION" and "END OF YOUR IMPLEMENTATION".
 */
// BEGIN YOUR IMPLEMENTATION

/* The source code for inorder traversal is given. You need to implement
 * postoder traversal and preoder traversal in a similar manner.
 */
void Inorder(BinTree bt) {
  if (!IsEmpty(bt)) {
    Inorder(Lchild(bt));
    print(Data(bt));
    Inorder(Rchild(bt));
  }
}

void Postorder(BinTree bt) {
  // Postorder: visit the left subtree, the	right subtree, then the root
}
void Preorder(BinTree bt) {
  // Preorder: visit the root, the left	subtree, then the right subtree
}

// END OF YOUR IMPLEMENTATION

int main() {
  BinTree bt = Read();
  Inorder(bt);
  printf("\n");
  Postorder(bt);
  printf("\n");
  Preorder(bt);
  printf("\n");
}

// YOU DO NOT NEED TO READ ALL THE FOLLOWING CODE TO SOLVE THIS PROBLEM!

/* You do not need to care about how BinTree is implemented here, so you don't
 * need to understand how the following code works. Your solution should work
 * even if we use a different implementation, e.g. we can use Array
 * Representation instead of Linked Representation.
 */
// begin a possible implementation of ADT BinTree
typedef struct node* treePointer;
struct node {
  element data;
  treePointer leftChild, rightChild;
};

BinTree Create() { return NULL; }

bool IsEmpty(BinTree tree) { return tree == NULL; }

BinTree MakeBT(BinTree bt1, element item, BinTree bt2) {
  treePointer bt = malloc(sizeof(struct node));
  bt->leftChild = bt1;
  bt->data = item;
  bt->rightChild = bt2;
  return bt;
}

BinTree Lchild(BinTree bt) { return ((treePointer)bt)->leftChild; }

BinTree Rchild(BinTree bt) { return ((treePointer)bt)->rightChild; }

element Data(BinTree bt) { return ((treePointer)bt)->data; }

// end of the implementation

// helper functions
BinTree Read() {
  int n;
  scanf("%d", &n);
  BinTree* nodes = (BinTree*)malloc(sizeof(BinTree) * n);
  for (int i = 0; i < n; i++) {
    int left, right;
    char data[1024];
    scanf("%d%d%1023s", &left, &right, data);
    BinTree bt1 = left == -1 ? NULL : nodes[left];
    BinTree bt2 = right == -1 ? NULL : nodes[right];
    void* item = strdup(data);
    nodes[i] = MakeBT(bt1, item, bt2);
  }
  BinTree root = nodes[n - 1];
  free(nodes);
  return root;
}

void print(element item) { printf("%s", (char*)item); }

Sample input:
6
-1 -1 hel
-1 -1 o_
0 1 l
2 -1 w
-1 -1 ld
3 4 or

Sample output:
hello_world
helo_lwldor
orwlhelo_ld