cs536/BTMain.cpp at master · shiftf8/cs536 · 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
#include "BTNode.h"
#include <iostream>

using namespace std;


int getHeight(BTNode* root)
{
    if (root == nullptr) return 0;

    int heightLeft = getHeight(root->getLeft());
    int heightRight = getHeight(root->getRight());

    return 1 + std::max(heightLeft, heightRight);
}

int getNumNodes(BTNode* root)
{
    if (root == nullptr) return 0;
    return 1 + getNumNodes(root->getLeft()) + getNumNodes(root->getRight());
}

void inOrder(BTNode* root)
{
    if (root != nullptr)
    {
        inOrder(root->getLeft());
        cout << root->getItem() << " ";
        inOrder(root->getRight());
    }
}

void postOrder(BTNode* root)
{
    if (root != nullptr)
    {
        postOrder(root->getLeft());
        postOrder(root->getRight());
        cout << root->getItem() << " ";

    }
}

int main()
{
    // Build a sample tree by brute force
    //          A
    //       B     C
    //     D   E      F
    //

    BTNode* b = new BTNode('B');
    BTNode* c = new BTNode('C');
    BTNode* d = new BTNode('D');
    BTNode* e = new BTNode('E');
    BTNode* f = new BTNode('F');

    BTNode* root = new BTNode('A', b, c);
    b->setLeft(d);
    b->setRight(e);
    c->setRight(f);

    // Get Height and Number of Nodes
    cout << "Height: " << getHeight(root) << "  Num Nodes: " << getNumNodes(root) << endl;

    // InOrder Traversal
    cout << "InOrder: ";
    inOrder(root);
    cout << endl;

    // PostOrder Traversal
    cout << "PostOrder: ";
    postOrder(root);
    cout << endl;
}