对任意给定的二叉树完成下列操作：
               （1）根据输入的序列，建立二叉链表存储结构；
               （2）输出该二叉树的先序、中序、后序遍历结果（递归算法）；
               （3）先序遍历二叉树（非递归算法）；
               （4）借助队列实现二叉树的层次遍历；
               （5）求二叉树的高度；
               （6）求二叉树叶子结点个数；
               （7）将二叉链表视为树或森林的孩子兄弟链表，计算其叶子结点个数。

/*
 * @Author: Vastsea(lyx8851@qq.com)
 * @Date: 2023-05-26 15:29:24
 * @LastEditors: Vastsea(lyx8851@qq.com)
 * @LastEditTime: 2023-05-31 11:52:45
 * @FilePath: \Development\Cpp\3_SecondSemesterCollege\Experiment\InClass_Experiment_1\树和二叉树.cpp
 * @Description: 对任意给定的二叉树完成下列操作：
            ok    （1）根据输入的序列，建立二叉链表存储结构；
            ok    （2）输出该二叉树的先序、中序、后序遍历结果（递归算法）；
            ok    （3）先序遍历二叉树（非递归算法）；
            ok    （4）借助队列实现二叉树的层次遍历；
            ok    （5）求二叉树的高度；
            ok    （6）求二叉树叶子结点个数；
            ok    （7）将二叉链表视为树或森林的孩子兄弟链表，计算其叶子结点个数。
 * Link:https://59888888.xyz/
 * Phone:18893558104
 */
#include <iostream>
#include <queue>
using namespace std;

typedef int ElemType;

struct node
{
    ElemType data;
    struct node *lchild = NULL;
    struct node *rchild = NULL;
};

typedef node *BTree;

/**
 * @description: 根据已有数组构建完全二叉树
 * @param {BTree} &root 当前操作节点
 * @param {ElemType} source 来源数据数组
 * @param {int} numOfSource Source数组的长度
 * @param {int} nowNum 现在在插入的是第几个元素
 * @return {*}
 */
void Structure(BTree &root, ElemType source[], int numOfSource, int nowNum = 1) // 根据数组构造
{
    if (nowNum > numOfSource)
    {
        return;
    }
    if (!root) // 往下看，只要root空&&nowNum合法就插入
    {
        root = new node;
        root->data = source[nowNum - 1];
    }
    Structure(root->lchild, source, numOfSource, nowNum * 2);
    Structure(root->rchild, source, numOfSource, nowNum * 2 + 1);
}

void Print(BTree T, int level = 0, int lr = 0) // 打印二叉树
{
    if (!T)
    {
        return;
    }
    Print(T->rchild, level + 1, 2);
    for (int i = 0; i < level; i++)
    {
        cout << "          ";
    }
    switch (lr)
    {
    case 1:
    {
        cout << "\\-";
        break;
    }
    case 2:
    {
        cout << "/-";
        break;
    }
    default:
        break;
    }
    cout << T->data << endl;
    Print(T->lchild, level + 1, 1); // 打印左子树，并将层次加1
}

void PreOrder(BTree &root) // 先序遍历
{
    if (!root)
    {
        return;
    }
    else
    {
        cout << root->data << " ";
        PreOrder(root->lchild);
        PreOrder(root->rchild);
    }
}

void MidOrder(BTree &root) // 中序遍历
{
    if (!root)
    {
        return;
    }
    else
    {
        MidOrder(root->lchild);
        cout << root->data << " ";
        MidOrder(root->rchild);
    }
}

void PostOrder(BTree &root) // 后序遍历
{
    if (!root)
    {
        return;
    }
    else
    {
        PostOrder(root->lchild);
        PostOrder(root->rchild);
        cout << root->data << " ";
    }
}

void PreOrder_NoRecursion(BTree &root) // 先序遍历_非递归
{
    node *p = root;
    node *s[500];
    int top = -1;
    while (p || top != -1)
    {
        while (p)
        {
            cout << p->data << " ";
            s[++top] = p;
            p = p->lchild;
        }
        if (top != -1)
        {
            p = s[top--];
            p = p->rchild;
        }
    }
}

void LevelOrder(BTree &root) // 层序遍历
{
    queue<node *> q;
    if (root)
    {
        q.push(root);
    }
    while (!q.empty())
    {
        node *n = q.front();
        cout << n->data << " ";
        if (n->lchild != NULL)
        {
            q.push(n->lchild);
        }
        if (n->rchild != NULL)
        {
            q.push(n->rchild);
        }
        q.pop();
    }
}

int Height(BTree &root) // 求高度
{
    if (!root)
    {
        return 0;
    }
    else
    {
        int HeightL = Height(root->lchild);
        int HeightR = Height(root->rchild);
        return max(HeightL, HeightR) + 1;
    }
}

int leafNodeNum = 0;
void CountleafNode(BTree &root) // 求叶子节点个数
{
    if (!root)
    {
        return;
    }
    if (!(root->lchild) && !(root->rchild))
    {
        leafNodeNum++;
    }
    else
    {
        CountleafNode(root->lchild);
        CountleafNode(root->rchild);
    }
}

int TreeleafNodeNum = 0;
void CountTreeleafNode(BTree &root)//求二叉链表视为树或森林的孩子兄弟链表后的叶子节点个数
{
    if (!root)
    {
        return;
    }
    if (!root->lchild)
    {
        TreeleafNodeNum++;
    }
    CountTreeleafNode(root->lchild);
    CountTreeleafNode(root->rchild);
}

int main()
{
    BTree T1 = NULL;
    ElemType tes[20] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
    cout << "根据已有数组{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20}构建完全二叉树:" << endl;
    Structure(T1, tes, 20);
    Print(T1);

    cout << endl
         << "先序遍历序列为:";
    PreOrder(T1);
    cout << endl
         << endl
         << "中序遍历序列为:";
    MidOrder(T1);
    cout << endl
         << endl
         << "后序遍历序列为:";
    PostOrder(T1);
    cout << endl
         << endl;

    cout << "先序遍历(非递归)结果为:";
    PreOrder_NoRecursion(T1);
    cout << endl
         << endl;

    cout << "层序遍历的结果为:";
    LevelOrder(T1);
    cout << endl
         << endl;

    cout << "该二叉树的高度为:" << Height(T1) << endl
         << endl;

    CountleafNode(T1);
    cout << "该二叉树的叶子节点个数为:" << leafNodeNum << endl
         << endl;

    CountTreeleafNode(T1);
    cout << "将二叉链表视为树或森林的孩子兄弟链表后的叶子节点个数为:" << TreeleafNodeNum << endl
         << endl;

    return 0;
}