acadia/c++/algorithm/datastructure/TreeTraversal.cpp at master · billyean/acadia · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
//Copyright [2018] [Haibo Yan]
//
//Licensed under the Apache License, Version 2.0 (the "License");
//you may not use this file except in compliance with the License.
//You may obtain a copy of the License at
//
//    http://www.apache.org/licenses/LICENSE-2.0
//
//Unless required by applicable law or agreed to in writing, software
//distributed under the License is distributed on an "AS IS" BASIS,
//WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//See the License for the specific language governing permissions and
//limitations under the License.
//
// Created by Haibo Yan on 4/20/18.
//

#include "TreeTraversal.h"

template <class T>
vector<T> TreeTraversal::preOrder(TreeNode<T>* root) {
    vector<T> ordered;
    stack<TreeNode<T>*> nodes;
    if (root != NULL) {
        nodes.push(root);

        while (!nodes.empty()) {
            TreeNode<T>* top = nodes.top();
            ordered.push_back(top->t_);
            nodes.pop();
            if (top->right_ != NULL) {
                nodes.push(top->right_);
            }
            if (top->left_ != NULL) {
                nodes.push(top->left_);
            }
        }
    }

    return ordered;
}

template <class T>
vector<T> TreeTraversal::inOrder(TreeNode<T>* root) {
    vector<T> ordered;

    if (root != NULL) {
        TreeNode<T>* current = root;
        stack<TreeNode<T>*> nodes;

        while (!nodes.empty() || current != NULL) {
            if (current != NULL) {
                if (current->left_ != NULL) {
                    nodes.push(current->left_);
                }
                current = current->left_;
            } else {
                TreeNode<T>* top = nodes.top();
                nodes.pop();
                ordered.push_back(top->t_);
                current = current->right_;
            }
        }
    }

    return ordered;
}

template <class T>
vector<T> TreeTraversal::postOrder(TreeNode<T>* root) {
    vector<T> ordered;

    if (root != NULL) {
        TreeNode<T>* prev = NULL;
        stack<TreeNode<T>*> nodes;
        nodes.push(root);

        while (!nodes.empty()) {
            TreeNode<T>* current = nodes.top();
            if (prev == NULL || current == prev->left_ || current == prev->right_) {
                if (current->left_ != NULL) {
                    nodes.push(current->left_);
                } else if (current->right_ != NULL) {
                    nodes.push(current->right_);
                }
            } else if (current->left_ == prev) {
                if (current->right_ != NULL) {
                    nodes.push(current->right_);
                } else {
                    ordered.push_back(current->t_);
                    nodes.pop();
                }
            } else {
                ordered.push_back(current->t_);
                nodes.pop();
            }
            prev = current;
        }
    }

    return ordered;
}