Data-Structure/binary_tree.hpp at master · HorizonFTT/Data-Structure · 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
#include <iostream>

class Algorithm;

template <typename T>
class BinaryTree {
    friend class Algorithm;

private:
    static const T end = std::is_same<char, T>::value ? '#' : 0;
    T data;
    BinaryTree<T> *lchild;
    BinaryTree<T> *rchild;

    BinaryTree(T elem) : data(elem) {}

public:
    static BinaryTree<T> *creatTree() {
        T elem;
        std::cin >> elem;
        if (elem == end) {
            return nullptr;
        }
        BinaryTree<T> *tree = new BinaryTree(elem);
        tree->lchild = creatTree();
        tree->rchild = creatTree();
        return tree;
    }

    void preOrder() {
        std::cout << data << " ";
        if (lchild != nullptr) {
            lchild->preOrder();
        }
        if (rchild != nullptr) {
            rchild->preOrder();
        }
    }

    void inOrder() {
        if (lchild != nullptr) {
            lchild->inOrder();
        }
        std::cout << data << " ";
        if (rchild != nullptr) {
            rchild->inOrder();
        }
    }

    void postOrder() {
        if (lchild != nullptr) {
            lchild->postOrder();
        }
        if (rchild != nullptr) {
            rchild->postOrder();
        }
        std::cout << data << " ";
    }
};