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

以下是实现该算法的C++代码：

#include <iostream>
using namespace std;

// 二叉树结点的定义
struct TreeNode {
    char val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char x) : val(x), left(NULL), right(NULL) {}
};

// 根据前序遍历和中序遍历序列构造二叉树
TreeNode* buildTree(string preorder, string inorder) {
    if (preorder.empty()) {
        return NULL;
    }
    char rootVal = preorder[0];
    int pos = inorder.find(rootVal);
    TreeNode* root = new TreeNode(rootVal);
    root->left = buildTree(preorder.substr(1, pos), inorder.substr(0, pos));
    root->right = buildTree(preorder.substr(pos + 1), inorder.substr(pos + 1));
    return root;
}

// 判断一棵二叉树是否是正则二叉树
bool isRegularBinaryTree(TreeNode* root) {
    if (root == NULL) {
        return true;
    }
    if (root->left != NULL && root->right != NULL) {
        return isRegularBinaryTree(root->left) && isRegularBinaryTree(root->right);
    } else if (root->left != NULL) {
        return isRegularBinaryTree(root->left) && root->left->left == NULL && root->left->right == NULL;
    } else if (root->right != NULL) {
        return isRegularBinaryTree(root->right) && root->right->left == NULL && root->right->right == NULL;
    } else {
        return true;
    }
}

int main() {
    string preorder = "ABDECFG";
    string inorder = "DBEAFCG";
    TreeNode* root = buildTree(preorder, inorder);
    if (isRegularBinaryTree(root)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

该算法的核心思想是递归地判断每个结点的左右子树是否都存在（不为NULL），如果都存在则继续递归判断左右子树是否为正则二叉树；如果只有左子树存在，则判断左子树是否为单结点树；如果只有右子树存在，则判断右子树是否为单结点树。如果左右子树都不存在，则认为当前结点是正则二叉树。