« Pre-Order traversal of tree

Copy
1#include <iostream>
2#include <iomanip>
3#include <algorithm>
4#include <string>
5#include <cstring>
6#include <vector>
7#include <cmath>
8#include <map>
9#include <climits>
10// climits for INT_MIN
11#include <unordered_map>
12using namespace std;
13#include <queue>
14
15template <typename T>
16class TreeNode
17{
18public:
19    T data;
20    vector<TreeNode<T> *> children;
21
22    TreeNode(T data)
23    {
24        this->data = data;
25    }
26
27    // current node won't be deleted before destructor is completed. So here we can do the cleanup
28    ~TreeNode()
29    {
30        for (int i = 0; i < children.size(); i++)
31        {
32            delete children[i];
33        }
34    }
35};
36
37TreeNode<int> *takeInputLevelWise()
38{
39    int rootData;
40    cout << "Enter root data: " << endl;
41    cin >> rootData;
42    TreeNode<int> *root = new TreeNode<int>(rootData);
43
44    queue<TreeNode<int> *> pendingNodes;
45
46    pendingNodes.push(root);
47    while (!pendingNodes.empty())
48    {
49        TreeNode<int> *front = pendingNodes.front();
50        pendingNodes.pop();
51        cout << "Enter number of children of " << front->data << endl;
52        int numChild;
53        cin >> numChild;
54
55        for (int i = 0; i < numChild; i++)
56        {
57            int childData;
58            cout << "Enter " << i << "th child of " << front->data << endl;
59            cin >> childData;
60            TreeNode<int> *child = new TreeNode<int>(childData);
61            front->children.push_back(child);
62            pendingNodes.push(child);
63        }
64    }
65    return root;
66}
67
68void preOrder(TreeNode<int> *root)
69{
70    if (root == NULL)
71    {
72        return;
73    }
74    cout << root->data << " ";
75    for (int i = 0; i < root->children.size(); i++)
76    {
77        preOrder(root->children[i]);
78    }
79}
80
81int main()
82{
83    TreeNode<int> *newRoot = takeInputLevelWise();
84    printTree(newRoot);
85
86    cout << "---------PREORDER---------" << endl;
87    preOrder(newRoot);
88    cout << endl;
89    cout << "---------PREORDER---------" << endl;
90
91    delete newRoot;
92
93    return 0;
94}