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

以下是C++的代码实现：

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

// 二叉树的结构体
typedef struct BiTNode {
    char data;              // 数据域
    struct BiTNode *lchild; // 左子树
    struct BiTNode *rchild; // 右子树
} BiTNode, *BiTree;

// 根据前序遍历序列和中序遍历序列构建二叉树
void createBiTree(BiTree &T, char *preorder, char *inorder, int len) {
    if(len <= 0) return;        // 空树
    T = new BiTNode;            // 创建根结点
    T -> data = *preorder;      // 填充数据域
    int rootIndex = 0;          // 根结点在中序遍历序列中的位置
    while(*(inorder + rootIndex) != *preorder) rootIndex++; // 查找根结点位置
    createBiTree(T -> lchild, preorder + 1, inorder, rootIndex); // 递归构建左子树
    createBiTree(T -> rchild, preorder + rootIndex + 1, inorder + rootIndex + 1, len - rootIndex - 1); // 递归构建右子树
}

// 判断是否为正则二叉树
bool isRegular(BiTree T) {
    if(T == NULL) return true;  // 空树一定是正则二叉树
    if(T -> lchild == NULL && T -> rchild == NULL) return true; // 叶子结点一定是正则二叉树
    if(T -> lchild == NULL && T -> rchild != NULL && (T -> rchild -> lchild != NULL || T -> rchild -> rchild != NULL)) return false; // 左子树为空，右子树不为空且不为单节点，则不是正则二叉树
    if(T -> rchild == NULL && T -> lchild != NULL && (T -> lchild -> lchild != NULL || T -> lchild -> rchild != NULL)) return false; // 右子树为空，左子树不为空且不为单节点，则不是正则二叉树
    return isRegular(T -> lchild) && isRegular(T -> rchild); // 递归判断左右子树是否都是正则二叉树
}

int main() {
    char preorder[100], inorder[100];  // 存储前序和中序遍历序列
    cin >> preorder >> inorder;
    int len = strlen(preorder);        // 序列长度
    BiTree T = NULL;                   // 初始化二叉树
    createBiTree(T, preorder, inorder, len);  // 构建二叉树
    if(isRegular(T)) cout << "Yes" << endl;   // 判断是否为正则二叉树
    else cout << "No" << endl;
    return 0;
}

输入样例：

ABHDCEFG
HBDAEFCG

输出样例：

No