CSDP250_Project3/BinarySearchTree.h at main · FortuneKalu/CSDP250_Project3 · 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
#pragma once

#ifndef BINARY_SEARCH_TREE_H
#define BINARY_SEARCH_TREE_H

#include <string>
using namespace std;

// Node struct for the Binary Search Tree
struct Node {
    int data;
    Node* leftNext;
    Node* rightNext;

    Node(int value) : data(value), leftNext(nullptr), rightNext(nullptr) {}
};

// ListNode struct for the linked list
struct ListNode {
    int data;
    ListNode* next;

    ListNode(int value) : data(value), next(nullptr) {}
};

// LinkedList struct to store traversal results
struct LinkedList {
    ListNode* head;
    ListNode* tail;

    LinkedList() : head(nullptr), tail(nullptr) {}
    ~LinkedList();
    void add(int value);
    void print() const;
};

// Binary Search Tree class
class BinarySearchTree {
private:
    Node* root;

    Node* insertNode(Node* root, int value);
    void preOrderTraversal(Node* root, LinkedList& result) const;
    void inOrderTraversal(Node* root, LinkedList& result) const;
    void postOrderTraversal(Node* root, LinkedList& result) const;

public:
    BinarySearchTree();
    void insert(int value);
    void buildFromArray(const int* numbers, int size);
    void getPreOrderTraversal(LinkedList& result) const;
    void getInOrderTraversal(LinkedList& result) const;
    void getPostOrderTraversal(LinkedList& result) const;
};

#endif // BINARY_SEARCH_TREE_H