// #define NORM_BINARY_TREE
#define THREAD_BINARY_TREE

#include <iostream>
#include <queue>

using namespace std;

#pragma region BinaryTree

template <typename T>
class BinaryTree
{
public:
    // 左、右孩子结点对应的指针
    BinaryTree<T> *leftChild = nullptr;
    BinaryTree<T> *rightChild = nullptr;
    // 当前结点存放的值
    T value;

    BinaryTree(T nodeValue);
};

template <typename T>
BinaryTree<T>::BinaryTree(T nodeValue)
{
    value = nodeValue;
}

template <typename T>
BinaryTree<T> *createBinaryTreeNode(T nodeValue)
{
    return new BinaryTree<T>(nodeValue);
}

#pragma endregion

#pragma region Functions

template <typename T>
void preOrder(BinaryTree<T> *tree)
{
    if (tree != nullptr)
    {
        cout << "[" << tree->value << "] " << endl;
        preOrder(tree->leftChild);
        preOrder(tree->rightChild);
    }
}

template <typename T>
void inOrder(BinaryTree<T> *tree)
{
    if (tree != nullptr)
    {
        inOrder(tree->leftChild);
        cout << "[" << tree->value << "] " << endl;
        inOrder(tree->rightChild);
    }
}

template <typename T>
void postOrder(BinaryTree<T> *tree)
{
    if (tree != nullptr)
    {
        postOrder(tree->leftChild);
        postOrder(tree->rightChild);
        cout << "[" << tree->value << "] " << endl;
    }
}

template <typename T>
void levelOrder(BinaryTree<T> *tree)
{
    // 初始化一个队列
    queue<BinaryTree<T> *> bTreeQueue;
    // 将当前节点入队
    bTreeQueue.push(tree);

    // 若队列不为空，则说明这一层还有节点
    while (bTreeQueue.size() > 0)
    {
        // 出队队首元素，并输出该节点的值
        BinaryTree<T> *currentFront = bTreeQueue.front();
        bTreeQueue.pop();
        cout << "[" << currentFront->value << "] " << endl;

        if (currentFront->leftChild != nullptr)
        {
            // 将左孩子节点入队
            bTreeQueue.push(currentFront->leftChild);
        }
        if (currentFront->rightChild != nullptr)
        {
            // 将右孩子节点入队
            bTreeQueue.push(currentFront->rightChild);
        }
    }
}

#pragma endregion

int main(int argc, char *argv[])
{
    // 初始化节点
    BinaryTree<int> *root = createBinaryTreeNode(1);
    BinaryTree<int> *a = createBinaryTreeNode(2);
    BinaryTree<int> *b = createBinaryTreeNode(3);
    BinaryTree<int> *d = createBinaryTreeNode(4);
    BinaryTree<int> *e = createBinaryTreeNode(5);
    BinaryTree<int> *f = createBinaryTreeNode(6);

    // 为不同节点指定左、右孩子节点
    root->leftChild = a;
    root->rightChild = b;

    a->leftChild = d;
    a->rightChild = e;

    b->leftChild = f;

    // 调用 levelOrder 函数来进行前序遍历
    levelOrder(root);

    return 0;
}