tree.cpp

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <utility>
#include <bitset>

#define fi first
#define sc second

using namespace std;

class Node{
public:
    Node* left;
    Node* right;
    int value;
};

class Tree{
private:
    Node* root;
public:
    Tree()
    {
        root = NULL;
    }
    Node* insertChild(Node* currentNode, int value)
    {
        if(value <= currentNode->value && currentNode->left == NULL)
        {
            Node* newNode = new Node();
            newNode->left = NULL;
            newNode->right = NULL;
            newNode->value = value;
            currentNode->left = newNode;

            return newNode;
        }
        else if(value > currentNode->value && currentNode->right == NULL)
        {
            Node* newNode = new Node();
            newNode->left = NULL;
            newNode->right = NULL;
            newNode->value = value;
            currentNode->right = newNode;

            return newNode;
        }
        else if(value <= currentNode->value)
        {
            return insertChild(currentNode->left, value);
        }
        else if(value > currentNode->value)
        {
            return insertChild(currentNode->right, value);
        }
    }
    Node* insert(int value)
    {
        if(root == NULL)
        {
            root = new Node();
            root->left = NULL;
            root->right = NULL;
            root->value = value;

            return root;
        }
        else if(value <= root->value && root->left == NULL)
        {
            Node* newNode = new Node();
            newNode->left = NULL;
            newNode->right = NULL;
            newNode->value = value;
            root->left = newNode;

            return newNode;
        }
        else if(value > root->value && root->right == NULL)
        {
            Node* newNode = new Node();
            newNode->left = NULL;
            newNode->right = NULL;
            newNode->value = value;
            root->right = newNode;

            return newNode;
        }
        else if(value <= root->value)
        {
            return insertChild(root->left, value);
        }
        else if(value > root->value)
        {
            return insertChild(root->right, value);
        }

        return NULL;
    }
    Node* find(int value)
    {
        Node* currentNode = root;
        Node* emptyNode = NULL;

        while(currentNode != NULL)
        {
            if(value == currentNode->value)
            {
                return currentNode;
            }
            else if(value <= currentNode->value)
            {
                currentNode = currentNode->left;
            }
            else if(value > currentNode->value)
            {
                currentNode = currentNode->right;
            }
        }

        return emptyNode;
    }
    void preOrderTraverse(Node* currentNode)
    {
        if(currentNode != NULL)
        {
            printf("%d ", currentNode->value);
            preOrderTraverse(currentNode->left);
            preOrderTraverse(currentNode->right);
        }
    }
    void preOrder()
    {
        Node* currentNode = root;
        preOrderTraverse(currentNode);
        printf("\n");
    }
    void inOrderTraverse(Node* currentNode)
    {
        if(currentNode != NULL)
        {
            inOrderTraverse(currentNode->left);
            printf("%d ", currentNode->value);
            inOrderTraverse(currentNode->right);
        }
    }
    void inOrder()
    {
        Node* currentNode = root;
        inOrderTraverse(currentNode);
        printf("\n");
    }
    void postOrderTraverse(Node* currentNode)
    {
        if(currentNode != NULL)
        {
            postOrderTraverse(currentNode->left);
            postOrderTraverse(currentNode->right);
            printf("%d ", currentNode->value);
        }
    }
    void postOrder()
    {
        Node* currentNode = root;
        postOrderTraverse(currentNode);
        printf("\n");
    }
    void printAllOrder()
    {
        this->preOrder();
        this->inOrder();
        this->postOrder();
    }
};

int main()
{
    Tree* tree = new Tree();
    int values[9] = {6,4,8,2,5,7,9,1,3};

    for(int i=0; i<9; i++)
    {
        if(!tree->insert(values[i]))
        {
            printf("Error!\n");
            break;
        }
    }

    tree->printAllOrder();

    printf("%s\n", tree->find(9) ? "Found" : "Not Found");
    printf("%s\n", tree->find(0) ? "Found" : "Not Found");

    return 0;
}