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

好的，这是一个关于二叉树的问题，我会尽力回答。首先，我们需要了解正则二叉树的概念，即不存在子树个数为1的结点。接下来，我们需要根据前序和中序遍历序列构造二叉树，并判断该二叉树是否为正则二叉树。

针对这个问题，我们可以先根据前序和中序遍历序列构造二叉树，代码如下：

struct TreeNode {
    char val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char x) : val(x), left(NULL), right(NULL) {}
};
 
TreeNode* buildTree(vector<char>& preorder, vector<char>& inorder) {
    if(preorder.empty()) return NULL;
    char rootVal = preorder[0];
    TreeNode* root = new TreeNode(rootVal);
    int rootIndex = 0;
    while(inorder[rootIndex] != rootVal) rootIndex++;
    vector<char> leftPreorder(preorder.begin()+1, preorder.begin()+rootIndex+1);
    vector<char> leftInorder(inorder.begin(), inorder.begin()+rootIndex);
    vector<char> rightPreorder(preorder.begin()+rootIndex+1, preorder.end());
    vector<char> rightInorder(inorder.begin()+rootIndex+1, inorder.end());
    root->left = buildTree(leftPreorder, leftInorder);
    root->right = buildTree(rightPreorder, rightInorder);
    return root;
}

接下来，我们可以编写一个判断函数，判断一个二叉树是否为正则二叉树。具体思路是，对于每个结点，判断它的左右子树是否为空或者是否都不为空。如果左右子树都为空或都不为空，则继续递归判断左右子树是否为正则二叉树。如果左右子树中有一个为空，则该结点为叶子结点，不满足正则二叉树的定义。代码如下：

bool isRegular(TreeNode* root) {
    if(!root) return true;
    if((!root->left && !root->right) || (root->left && root->right)) {
        return isRegular(root->left) && isRegular(root->right);
    }
    return false;
}

最后，我们将二叉树的前序和中序遍历序列作为输入，构造出二叉树，再判断是否为正则二叉树即可。完整代码如下：

#include <iostream>
#include <vector>
using namespace std;
 
struct TreeNode {
    char val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char x) : val(x), left(NULL), right(NULL) {}
};
 
TreeNode* buildTree(vector<char>& preorder, vector<char>& inorder) {
    if(preorder.empty()) return NULL;
    char rootVal = preorder[0];
    TreeNode* root = new TreeNode(rootVal);
    int rootIndex = 0;
    while(inorder[rootIndex] != rootVal) rootIndex++;
    vector<char> leftPreorder(preorder.begin()+1, preorder.begin()+rootIndex+1);
    vector<char> leftInorder(inorder.begin(), inorder.begin()+rootIndex);
    vector<char> rightPreorder(preorder.begin()+rootIndex+1, preorder.end());
    vector<char> rightInorder(inorder.begin()+rootIndex+1, inorder.end());
    root->left = buildTree(leftPreorder, leftInorder);
    root->right = buildTree(rightPreorder, rightInorder);
    return root;
}
 
bool isRegular(TreeNode* root) {
    if(!root) return true;
    if((!root->left && !root->right) || (root->left && root->right)) {
        return isRegular(root->left) && isRegular(root->right);
    }
    return false;
}
 
int main() {
    vector<char> preorder = {'A', 'B', 'H', 'D', 'C', 'E', 'F', 'G'};
    vector<char> inorder = {'H', 'B', 'D', 'A', 'E', 'F', 'C', 'G'};
    TreeNode* root = buildTree(preorder, inorder);
    if(isRegular(root)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

输入样例：

ABHDCEFG
HBDAEFCG

输出样例：

No