A binary tree has n nodes, numbered 0 to n - 1; node 0 is the root. Build the tree with struct nodes and pointers, then print its preorder, inorder and postorder traversals.
What to build
A binary tree built from a table of nodes, and its three depth-first traversals.
Requirements
- Create all the nodes first, then link each one to its children.
- Write one recursive function for each traversal.
- Print each traversal on its own line.
Input
The first line has n (1 ≤ n ≤ 100). Line i of the next n lines describes node i: its value, then the numbers of its left and right children, or -1 for no child.
Output
Three lines: the values in preorder, inorder and postorder, separated by spaces.
Constraints
1 ≤ n ≤ 100.
Example
Input:
5
1 1 2
2 3 4
3 -1 -1
4 -1 -1
5 -1 -1
Output:
1 2 4 5 3
4 2 5 1 3
4 5 2 3 1
Why it works
The three traversals visit the same nodes by the same route. They differ only in whether a node is printed before, between or after its two subtrees.
Examples
5 1 1 2 2 3 4 3 -1 -1 4 -1 -1 5 -1 -1
1 2 4 5 3 4 2 5 1 3 4 5 2 3 1
1 7 -1 -1
7 7 7
Hints
Hint 1
First malloc all n nodes into an array Tree *nodes[100], then set each node's left and right from the numbers (-1 means NULL).
Hint 2
Each traversal is a recursive function with a NULL base case.
Hint 3
To avoid a trailing space, print a space before every value except the first one on the line.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
#include <stdlib.h>
typedef struct tree {
int value;
struct tree *left, *right;
} Tree;
int printed = 0; // values printed on the current line
void show(int value) {
if (printed > 0) printf(" ");
printf("%d", value);
printed++;
}
void preorder(Tree *t) {
if (t == NULL) return;
show(t->value);
preorder(t->left);
preorder(t->right);
}
void inorder(Tree *t) {
if (t == NULL) return;
inorder(t->left);
show(t->value);
inorder(t->right);
}
void postorder(Tree *t) {
if (t == NULL) return;
postorder(t->left);
postorder(t->right);
show(t->value);
}
int main(void) {
int n;
scanf("%d", &n);
Tree *nodes[100];
int left[100], right[100];
for (int i = 0; i < n; i++) {
nodes[i] = malloc(sizeof(Tree));
scanf("%d %d %d", &nodes[i]->value, &left[i], &right[i]);
}
for (int i = 0; i < n; i++) {
nodes[i]->left = left[i] == -1 ? NULL : nodes[left[i]];
nodes[i]->right = right[i] == -1 ? NULL : nodes[right[i]];
}
preorder(nodes[0]);
printf("\n");
printed = 0;
inorder(nodes[0]);
printf("\n");
printed = 0;
postorder(nodes[0]);
printf("\n");
return 0;
}