Implement Tree without STL in C++/JAVA

[problem]
Construct a tree with the given input and traverse the tree in preorder.
Then, print the visited node numbers.

[Input]
The first input line contains the number of total test cases, T.
The next line contains the number of total nodes, N and the number of edges, E.
On the following line, the edges will be given.
The edges consist of two vertices which are always given in the order “parent-child”.
For instance, 1 2 refers to the edge connecting vertex 1 and vertex 2: 1 stands for parent, 2 for child.
Parent can have two children nodes at most.
The number of nodes can be up to 10000.


[Output]
Traverse the tree in preorder, then print the visited node numbers.



 INPUT                                                
=============                                                
3 // number of total Test cases                                         
13 12 // N: number of Nodes, E: number of Edges                        
1 2 1 3 2 4 3 5 3 6 4 7 7 12 5 9 5 8 6 11 6 10 11 13 // Edge Information (“Parent-Child” order)
10 9
1 2 1 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10
50 49
31 7 2 17 27 32 14 30 1 21 45 26 44 27 39 11 26 3 48 6 3 44 2 49 42 13 48 8 23 33 11 10 8 42 41 31 17 4 8 22 25 23 21 41 28 25 13 16 46 2 31 35 42 19 32 18 27 50 45 15 28 20 46 28 44 40 40 5 15 48 9 34 1 46 17 29 35 36 21 45 14 37 23 14 6 39 11 9 19 24 26 47 16 38 40 12 47 43



OUTPUT
===============================
#1
1 2 4 7 12 3 5 9 8 6 11 13 10
#2
1 2 3 4 5 6 7 8 9 10
#3
1 21 41 31 7 35 36 45 26 3 44 27 32 18 50 40 5 12 47 43 15 48 6 39 11 10 9 34 8 42 13 16 38 19 24 22 46 2 17 4 29 49 28 25 23 33 14 30 37 20


C++ Source :

    #include<iostream>
    #include <stdio.h>

    using namespace std;

    #define MAX_NODE_NUM 10000
    #define MAX_CHILD_NUM 2

    typedef struct
    {
        int parent;
        int child[MAX_CHILD_NUM];
    } TreeNode;

    TreeNode tree[MAX_NODE_NUM];

    int nodeNum;
    int edgeNum;
    int root;
    void initTree(void);
    void addChild(int parent, int child);
    int getRoot(void);
    void preOrder(int root);

    int main(void)
    {
        int test_case;
        int T;
        int i;
        int parent;
        int child;
        freopen("CreateTree.txt", "r", stdin);
        cin >> T;

        for (test_case = 1; test_case <= T; ++test_case)
        {
            cin >> nodeNum >> edgeNum;

            initTree();

            for (i = 0; i < edgeNum; i++)
            {
                cin >> parent >> child;
                addChild(parent, child);
            }

            root = getRoot();

            cout << "#" << test_case <<" ";
            preOrder(root);
            cout << endl;
        }

        return 0;
    }

    void initTree(void)
    {
        int i;
        int j;
        for (i = 0; i <= nodeNum; i++)
        {
            tree[i].parent = -1;
            for (j = 0; j < MAX_CHILD_NUM; j++)
            {
                tree[i].child[j] = -1;
            }
        }
    }

    void addChild(int parent, int child)
    {
        int i;
        for (i = 0; i < MAX_CHILD_NUM; i++)
        {
            if (tree[parent].child[i] == -1)
            {
                break;
            }
        }
        tree[parent].child[i] = child;
        tree[child].parent = parent;
    }

    int getRoot(void)
    {
        int i;
        int j;
        for (i = 1; i <= nodeNum; i++)
        {
            if (tree[i].parent == -1)
            {
                return i;
            }
        }
        return -1;
    }

    void preOrder(int root)
    {
        int i;
        int child;
        printf("%d ", root);

        for (i = 0; i < MAX_CHILD_NUM; i++)
        {
            child = tree[root].child[i];
            if (child != -1)
            {
                preOrder(child);
            }
        }
    }

Java Source :

package com.datastructure;

    import java.io.FileInputStream;
    import java.io.FileNotFoundException;
    import java.util.Scanner;

    public class TreeView {

        static private final String INPUT = System.getProperty("user.dir") + "\\src\\data\\treeInput.txt";
        static Scanner sc;

        public static void main(String[] args) {
            FileInputStream instream = null;
            try {
                instream = new FileInputStream(INPUT);
                System.setIn(instream);
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }

            sc = new Scanner(System.in);
            int T = sc.nextInt();


            for (int test_case = 1; test_case <= T; ++test_case) 
            {
                int node = sc.nextInt();
                int edge = sc.nextInt();

                Tree tree = new Tree(node);

                for (int i = 0; i < edge; i++)
                {
                    int parent = sc.nextInt();
                    int child = sc.nextInt();
                    tree.addChild(parent, child);
                }
                int root = tree.getRoot();
                System.out.printf("#%d ", test_case);
                tree.preOrder(root);
                System.out.printf("\n");
            }

            sc.close();

        }
    }


    class Tree
    {
    static final int MAX_CHILD_NUM = 2;

        class TreeNode {
            int parent;
            int []child = new int[MAX_CHILD_NUM];
            public TreeNode(int parent)
            {
                this.parent = parent;
                for (int i = 0; i < MAX_CHILD_NUM; i++)
                {
                    child[i] = -1;
                }
            }
        }

        TreeNode []treenode;
        int nodeNum;

        public Tree(int nodeNum) {
            this.nodeNum = nodeNum;
            treenode = new TreeNode[nodeNum+1];
            for (int i = 0; i <= nodeNum; i++)
            {
                treenode[i] = new TreeNode(-1);
            }
        }

        public void addChild(int parent, int child) 
        {
            int found = -1;
            for (int i = 0; i < MAX_CHILD_NUM; i++)
            {
                if (treenode[parent].child[i] == -1)
                {
                    found = i;
                    break;
                }
            }
            if (found == -1) return;

            treenode[parent].child[found] = child;
            treenode[child].parent = parent;
        }

        public int getRoot() 
        {
            for (int i = 1; i < nodeNum; i++) 
            {
                if (treenode[i].parent == -1) 
                {
                    return i;
                }
            }
            return -1;
        }

        public void preOrder(int root)
        {
            System.out.printf("%d ", root);

            for (int i = 0; i < MAX_CHILD_NUM; i++) 
            {
                int child = treenode[root].child[i];
                if (child != -1)
                {
                    preOrder(child);
                }
            }
        }

    }