1.定义

正则二叉树是指满足以下条件的二叉树：

🐣每个节点要么是叶子节点（没有子节点）

🐤要么恰好有两个子节点（一个左子节点和一个右子节点）

🐥换句话说，正则二叉树中不存在只有一个子节点的节点。

2.特点

🍫节点数量关系：

叶子节点数 = 内部节点数 + 1

总节点数 = 2 × 叶子节点数 - 1

🍬高度与节点数（对于高度为h的正则二叉树）：

最小节点数：2h + 1

最大节点数：2^(h+1) - 1（此时也是完美二叉树）

🍭递归性质：

正则二叉树的每个子树也是正则二叉树

 3.典型案例

【问题描述】设二叉树按二叉链表存放，写算法判别一棵二叉树是否是一棵正则二叉树。正  则二叉树是指在二叉树中不存在子树个数为1的结点。
【输入说明】二叉树的前序和中序遍历序列，以此构造二叉树的链式存储
【输出说明】若该二叉树是一棵正则二叉树，则输出Yes，否则输出No
【样例输入】
ABHDCEFG
HBDAEFCG
【样例输出】
No

#include<bits/stdc++.h>
using namespace std;
char mid[1000], front[1000]; // 存储中序遍历和前序遍历结果的字符数组
int num = 0; // 用于统计不符合正则二叉树条件的节点数量

// 二叉树结点结构定义
typedef struct BiTNode {
    char data; // 结点数据
    struct BiTNode *lchild, *rchild; // 左右孩子指针
} BiTNode, *BiTree;

// 根据前序和中序遍历结果构建二叉树
// 参数说明：a-b是前序遍历的区间，c-d是中序遍历的区间
BiTNode* build(int a, int b, int c, int d) {
    BiTNode *T; // 创建新结点
    T = new BiTNode;
    T->data = front[a]; // 前序遍历第一个元素是根结点
    T->lchild = T->rchild = NULL; // 初始化左右孩子为空
    
    // 如果区间不合法，返回空指针
    if(a > b || c > d)
        return NULL;
    
    // 在中序遍历中找到根结点的位置
    int t = c;
    while(mid[t] != front[a])
        t++;
    
    // 计算左子树的长度
    int len = t - c;
    
    // 递归构建左子树和右子树
    // 左子树：前序遍历区间[a+1, a+len]，中序遍历区间[c, c+len-1]
    T->lchild = build(a+1, a+len, c, c+len-1);
    // 右子树：前序遍历区间[a+len+1, b]，中序遍历区间[t+1, d]
    T->rchild = build(a+len+1, b, t+1, d);
    
    return T; // 返回构建好的子树根结点
}

// 检查二叉树是否为正则二叉树（即每个结点要么是叶子，要么有两个孩子）
void check(BiTree bt) {
    if(bt != NULL) {
        // 如果当前结点只有一个孩子（不符合正则二叉树定义）
        if((!bt->lchild && bt->rchild) || (bt->lchild && !bt->rchild)) {
            num++; // 计数器增加
            return;
        }
        // 递归检查左右子树
        check(bt->lchild);
        check(bt->rchild);
    }
    else
        return;
}

int main() {
    // 输入前序和中序遍历结果
    cin >> front;
    cin >> mid;
    
    // 计算树的大小（结点数-1）
    int size = strlen(mid) - 1;
    
    // 构建二叉树
    BiTree T;
    T = build(0, size, 0, size);
    
    // 检查是否为正则二叉树
    check(T);
    
    // 输出结果（注意：原代码两处都输出"No"，可能是笔误）
    if(num == 0)
        cout << "Yes"; // 如果没有不符合的结点，输出Yes
    else
        cout << "No"; // 否则输出No
    
    return 0;
}