// 面试题32（二）：分行从上到下打印二叉树

// 题目：从上到下按层打印二叉树，同一层的结点按从左到右的顺序打印，每一层

// 打印到一行。

#include <cstdio>

#include "BinaryTree.h"

#include <queue>

void Print(BinaryTreeNode* pRoot)

{

    if (pRoot == nullptr)

        return;

    std::queue<BinaryTreeNode*> nodes;

    nodes.push(pRoot);

    int nextLevel = ;//相比上个题，多了两个变量，一个是下层结点个数，初始化为0

    int toBePrinted = ;//一个是待打印的点，初始化为1

    while (!nodes.empty())

    {

        BinaryTreeNode* pNode = nodes.front();

        printf("%d ", pNode->m_nValue);

        if (pNode->m_pLeft != nullptr)

        {

            nodes.push(pNode->m_pLeft);

            ++nextLevel;//每有一个孩子进入队列，下层结点加1

        }

        if (pNode->m_pRight != nullptr)

        {

            nodes.push(pNode->m_pRight);

            ++nextLevel;

        }

        nodes.pop();

        --toBePrinted;//每弹出一个节点，待打印节点就减1

        if (toBePrinted == )//直到当前层打印完

        {

            printf("\n");//换行

            toBePrinted = nextLevel;//把记住的下层结点总数给它

            nextLevel = ;//下层结点要打印的个数置零，从新计数

        }

    }

}

// ====================测试代码====================

//            8

//        6      10

//       5 7    9  11

void Test1()

{

    BinaryTreeNode* pNode8 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode6 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode10 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode5 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode7 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode9 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode11 = CreateBinaryTreeNode();

    ConnectTreeNodes(pNode8, pNode6, pNode10);

    ConnectTreeNodes(pNode6, pNode5, pNode7);

    ConnectTreeNodes(pNode10, pNode9, pNode11);

    printf("====Test1 Begins: ====\n");

    printf("Expected Result is:\n");

    printf("8 \n");

    printf("6 10 \n");

    printf("5 7 9 11 \n\n");

    printf("Actual Result is: \n");

    Print(pNode8);

    printf("\n");

    DestroyTree(pNode8);

}

//            5

//          4

//        3

//

void Test2()

{

    BinaryTreeNode* pNode5 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode4 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode3 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode2 = CreateBinaryTreeNode();

    ConnectTreeNodes(pNode5, pNode4, nullptr);

    ConnectTreeNodes(pNode4, pNode3, nullptr);

    ConnectTreeNodes(pNode3, pNode2, nullptr);

    printf("====Test2 Begins: ====\n");

    printf("Expected Result is:\n");

    printf("5 \n");

    printf("4 \n");

    printf("3 \n");

    printf("2 \n\n");

    printf("Actual Result is: \n");

    Print(pNode5);

    printf("\n");

    DestroyTree(pNode5);

}

//        5

//         4

//          3

//           2

void Test3()

{

    BinaryTreeNode* pNode5 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode4 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode3 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode2 = CreateBinaryTreeNode();

    ConnectTreeNodes(pNode5, nullptr, pNode4);

    ConnectTreeNodes(pNode4, nullptr, pNode3);

    ConnectTreeNodes(pNode3, nullptr, pNode2);

    printf("====Test3 Begins: ====\n");

    printf("Expected Result is:\n");

    printf("5 \n");

    printf("4 \n");

    printf("3 \n");

    printf("2 \n\n");

    printf("Actual Result is: \n");

    Print(pNode5);

    printf("\n");

    DestroyTree(pNode5);

}

void Test4()

{

    BinaryTreeNode* pNode5 = CreateBinaryTreeNode();

    printf("====Test4 Begins: ====\n");

    printf("Expected Result is:\n");

    printf("5 \n\n");

    printf("Actual Result is: \n");

    Print(pNode5);

    printf("\n");

    DestroyTree(pNode5);

}

void Test5()

{

    printf("====Test5 Begins: ====\n");

    printf("Expected Result is:\n");

    printf("Actual Result is: \n");

    Print(nullptr);

    printf("\n");

}

//        100

//        /

//       50

//         \

//

void Test6()

{

    BinaryTreeNode* pNode100 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode50 = CreateBinaryTreeNode();

    BinaryTreeNode* pNode150 = CreateBinaryTreeNode();

    ConnectTreeNodes(pNode100, pNode50, nullptr);

    ConnectTreeNodes(pNode50, nullptr, pNode150);

    printf("====Test6 Begins: ====\n");

    printf("Expected Result is:\n");

    printf("100 \n");

    printf("50 \n");

    printf("150 \n\n");

    printf("Actual Result is: \n");

    Print(pNode100);

    printf("\n");

}

int main(int argc, char* argv[])

{

    Test1();

    Test2();

    Test3();

    Test4();

    Test5();

    Test6();

    system("pause");

    return ;

}