第1关：先序创建二叉树

#include<iostream>
using namespace std;

typedef struct BiTNode
{
	char data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;


void CreateBiTree(BiTree &T)
{
    // 先序创建二叉树：递归实现，输入'#'表示空节点
    char ch;
    // 注意：此处必须使用 cin.get() 或 scanf(" %c", &ch) 来读取字符，
    // 以避免跳过空格或换行符。如果题目保证输入是连续的字符流（无空格），
    // 也可以直接使用 cin >> ch。
    cin >> ch;

    // 如果输入的是'#'，表示当前节点为空
    if (ch == '#') {
        T = NULL;
    } else {
        // 1. 创建当前根节点
        T = new BiTNode;
        if (!T) { // 检查内存分配是否成功
            cout << "内存分配失败！" << endl;
            exit(1); 
        }
        T->data = ch;

        // 2. 递归创建左子树
        CreateBiTree(T->lchild);

        // 3. 递归创建右子树
        CreateBiTree(T->rchild);
    }
}

第2关：两棵树是否相同

#include<iostream>
using namespace std;

typedef struct BiTNode
{
	char data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;


int CmpTree(BiTree T1, BiTree T2)
{
    // 情况1：两棵树当前节点都为空，相等
    if (T1 == NULL && T2 == NULL) {
        return 1;
    }
    // 情况2：其中一棵树为空，另一棵不为空，不相等
    if (T1 == NULL || T2 == NULL) {
        return 0;
    }
    // 情况3：当前节点值不相等，不相等
    if (T1->data != T2->data) {
        return 0;
    }
    // 情况4：递归比较左子树和右子树（需同时相等才整体相等）
    return CmpTree(T1->lchild, T2->lchild) && CmpTree(T1->rchild, T2->rchild);
}

第3关：合并两棵二叉树

#include<iostream>
using namespace std;

typedef struct BiTNode
{
	int data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;


BiTree MergeTree(BiTree T1, BiTree T2)
{
    // 情况1：T1和T2都为空，合并后也为空
    if (T1 == NULL && T2 == NULL) {
        return NULL;
    }

    // 创建合并后的新节点
    BiTree newNode = new BiTNode;

    // 情况2：T1为空，复用T2的节点值
    if (T1 == NULL) {
        newNode->data = T2->data;
        // 递归合并左、右子树
        newNode->lchild = MergeTree(NULL, T2->lchild);
        newNode->rchild = MergeTree(NULL, T2->rchild);
    }
    // 情况3：T2为空，复用T1的节点值
    else if (T2 == NULL) {
        newNode->data = T1->data;
        // 递归合并左、右子树
        newNode->lchild = MergeTree(T1->lchild, NULL);
        newNode->rchild = MergeTree(T1->rchild, NULL);
    }
    // 情况4：T1和T2都存在，节点值相加
    else {
        newNode->data = T1->data + T2->data;
        // 递归合并左、右子树
        newNode->lchild = MergeTree(T1->lchild, T2->lchild);
        newNode->rchild = MergeTree(T1->rchild, T2->rchild);
    }

    return newNode;
}

第4关：交换二叉树左右孩子

#include<iostream>
using namespace std;

typedef struct BiTNode
{
	char data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;


void SwapBiTree(BiTree &T)
{
    // 若当前节点为空，直接返回（递归终止条件）
    if (T == NULL) {
        return;
    }

    // 1. 交换当前节点的左、右子树指针
    BiTree temp = T->lchild;
    T->lchild = T->rchild;
    T->rchild = temp;

    // 2. 递归交换左子树的所有节点
    SwapBiTree(T->lchild);

    // 3. 递归交换右子树的所有节点
    SwapBiTree(T->rchild);
}

第5关：完全二叉树判断

#include<iostream>
#include<queue>
using namespace std;

typedef struct BiTNode
{
	char data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;


int isCompleteTree(BiTree T)
{
    // 空树也是完全二叉树
    if (T == NULL) {
        return 1;
    }

    queue<BiTree> q;
    q.push(T);
    // 标记是否已经遇到空节点
    bool hasNull = false;

    while (!q.empty()) {
        BiTree node = q.front();
        q.pop();

        if (node == NULL) {
            // 遇到空节点，标记后续需全为空
            hasNull = true;
        } else {
            // 若已遇到空节点，又出现非空节点 → 不是完全二叉树
            if (hasNull) {
                return 0;
            }
            // 不管子节点是否为空，都入队（用于检测后续是否有非空节点）
            q.push(node->lchild);
            q.push(node->rchild);
        }
    }

    // 遍历结束，未出现违规情况 → 是完全二叉树
    return 1;
}