스택 , 큐, 트리 그리고 깊이탐색과 넓이탐색

/*
삽입
삭제
탐색
높이
bfs
dfs
*/
 
#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <cstdio>
#include <string.h>
using namespace std;
 
typedef struct tnode {
    int data;
    struct tnode* left;
    struct tnode* right;
    bool check;
}TNode;
 
typedef struct node {
    struct node* Next;
    struct node* prv;
    TNode* data;
}Node;
 
 
struct DataStructure {
    Node* Head;
    Node* Tail;
    virtual void push(TNode* data) = 0;
    virtual void pop() = 0;
    void print() {
        if (Head == nullptr) return;
        Node* temp = Head;
        while (temp) {
            cout << temp->data << ", ";
            temp = temp->Next;
        }
    }
    virtual TNode* back() = 0;
    void Initialize() {
        Head = nullptr;
        Tail = nullptr;
    }
};
 
struct Queue {
    Node* Head;
    Node* Tail;
    
    void initialize() {
        Head = nullptr;
        Tail = nullptr;
    }
 
    void push(TNode* data) {
        if (data == nullptr) return;
        Node* temp = (Node*)malloc(sizeof(Node));
        temp->Next = nullptr;
        temp->prv = nullptr;
        temp->data = data;
 
        if (Head == nullptr && Tail == nullptr) {
            Head = temp;
            Tail = temp;
            Head->Next = Tail;
            Tail->prv = Head;
            return;
        }
        Tail->Next = temp;
        temp->prv = Tail;
        Tail = temp;
    }
 
    void pop() {
        if (Tail == nullptr && Head == nullptr) return;
        if (Head == Tail) {
            Head = nullptr;
            Tail = nullptr;
        }
        else {
            Node* temp = Head;
            Head = Head->Next;
            free(temp);
        }
    }
    TNode* back() {
        if (Tail == nullptr && Head == nullptr) return nullptr;
        return Head->data;
    }
 
    void print() {
        if (Head == nullptr && Tail == nullptr) return;
        Node* temp = Head;
        while (temp) {
            cout << temp->data->data << ", ";
            temp = temp->Next;
        }
        cout << endl;
    }
};
 
struct Stack : DataStructure{
    
    void push(TNode* data) {
        if (data == nullptr) return;
        Node* temp = (Node*)malloc(sizeof(Node));
        temp->Next = nullptr;
        temp->prv = nullptr;
        temp->data = data;
        if (Head == nullptr) {
            Head = temp;
            return;
        }
        temp->Next = Head;
        Head->prv = temp;
        Head = temp;
    }
    void pop() {
        if (Head == nullptr) return;
        Node* temp = Head;
        Head = Head->Next;
        if(Head)
            Head->prv = nullptr;
        free(temp);
    }
    void print() {
        if (Head == nullptr) return;
        Node* temp = Head;
        while (temp) {
            cout << temp->data->data << ", ";
            temp = temp->Next;
        }
    }
 
    TNode* back() {
        if (Head == nullptr) return nullptr;
        return Head->data;
    }
};
 
TNode* createTNode(int data) {
    TNode* temp = (TNode*)malloc(sizeof(TNode));
    temp->left = nullptr;
    temp->right = nullptr;
    temp->data = data;
    temp->check = false;
    return temp;
}
 
TNode* InsertTNode(TNode* root, int data) {
    if (root == nullptr) {
        root = createTNode(data);
        return root;
    }
    
    if (root->data < data) return InsertTNode(root->right, data);
    else return InsertTNode(root->left, data);
 
}
 
void InsertTNode_DoubleP(TNode** root, int data) {
    if (*root == nullptr) {
        *root = createTNode(data);
        return;
    }
    if ((*root)->data > data)
        return InsertTNode_DoubleP(&(*root)->left, data);
    else
        return InsertTNode_DoubleP(&(*root)->right, data);
}
void print(TNode* root) {
    if (root == nullptr) return;
 
    print(root->left);
    cout << root->data << ", ";
    print(root->right);
}
 
void removeTNode(TNode** root, int data) {
    if (*root == nullptr) return;
    TNode* temp = *root;
    TNode* temp2 = nullptr;
    while (temp->data != data) {
        temp2 = temp;
        if (temp->data > data) temp = temp->left;
        else temp = temp->right;
    }
    if (temp == nullptr) return;
        
    if (!temp->left && !temp->right) {
        if (temp2->data > data) temp2->left = nullptr;
        free(temp);
    }
    else if (temp->left && temp->right) {
        TNode* temp3 = temp;
        temp3 = temp3->right;
        TNode* temp4 = nullptr;
        while (temp3->left != nullptr) {
            temp4 = temp3;
            temp3 = temp3->left;
        }
        if (temp3 == temp->right) {
            temp3 = temp->left;
            temp3->left = temp->right;
            if (temp2->data > data) temp2->left = temp3;
            else temp2->right = temp3;
        }
        else {
            temp4->left = nullptr;
            if (temp2->data > data) temp2->left = temp3;
            else temp2->right = temp3;
            temp3->left = temp->left;
            temp3->right = temp->right;
        }
    }
}
//
//int height(TNode* root) {
//    if (root == nullptr) return -1;
//    int level = 0;
//    if (root != nullptr) {
//        level = 1 + fmax(height(root->left), height(root->right));
//    }
//    return level;
//}
 
int height(TNode* root) {
    if (root == nullptr) return -1;
    return 1+ fmax(height(root->left), height(root->right));
}
 
int get_leaf(TNode* root) {
    if (root == nullptr) return 0;
    if (!root->left && !root->right) return 1;
    return get_leaf(root->left) + get_leaf(root->right);
}
 
int get_Count_Node(TNode* root) {
    if (root == nullptr) return 0;
    else return 1 + get_Count_Node(root->left) + get_Count_Node(root->right);
}
 
void BreathFirstSearch(TNode* root) {
    struct Queue q;
    q.initialize();
    q.push(root);
    while (q.Head != nullptr) {
        cout << q.back()->data <<", ";
        q.push(q.back()->left);
        q.push(q.back()->right);
        q.pop();
    }
}
 
void DepthFirstSearch(TNode* root) {
    TNode* temp = root;
    Stack s;
    s.Initialize();
    s.push(temp);
    cout << s.back()->data << ", ";
    while (s.Head != nullptr) {
        while (s.back()->left && !s.back()->left->check) {
            s.back()->left->check = true;
            s.push(s.back()->left);
            
            cout << s.back()->data << ", ";
        }
        if (s.back()->right && !s.back()->right->check) {
            s.back()->right->check = true;
            s.push(s.back()->right);
            cout << s.back()->data << ", ";
        }
        else
            s.pop();
        
    }
 
}
 
 
int main() {
 
    struct Queue q;
    q.initialize();
 
    TNode* root = nullptr;
    InsertTNode_DoubleP(&root, 4);
    InsertTNode_DoubleP(&root, 3);
    InsertTNode_DoubleP(&root, 7);
    InsertTNode_DoubleP(&root, 1);
    InsertTNode_DoubleP(&root, 2);
    InsertTNode_DoubleP(&root, 5);
    InsertTNode_DoubleP(&root, 8);
 
    print(root);
    cout << endl;
    
    cout << "Level : " << height(root) << endl;
    cout << "Count of Leaf : " << get_leaf(root);
    cout << "Get Count Node : " << get_Count_Node(root);
    cout << "Breath First Search : "; BreathFirstSearch(root);
    cout << endl;
    cout << "Depth First Search : "; DepthFirstSearch(root);
    return 0;
}