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

叉树是正则二叉树，则输出"YES"，否则输出"NO"。

算法思路：

1. 对于每个结点，判断其左右子树是否为空，若均为空，则返回1；若一个为空一个不为空，则返回0。

2. 对于非叶子结点，递归判断其左右子树是否是正则二叉树。

算法实现：

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 100

// 二叉树结点结构体
typedef struct TreeNode {
    char data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode, *Tree;

// 根据前序和中序遍历序列构造二叉树
Tree buildTree(char* preOrder, char* inOrder, int n) {
    if (n <= 0) return NULL;
    char rootData = preOrder[0];
    int i;
    for (i = 0; i < n; i++) {
        if (inOrder[i] == rootData) break;
    }
    Tree root = (Tree)malloc(sizeof(TreeNode));
    root->data = rootData;
    root->left = buildTree(preOrder+1, inOrder, i);
    root->right = buildTree(preOrder+i+1, inOrder+i+1, n-i-1);
    return root;
}

// 判断一棵二叉树是否是正则二叉树
int isRegularTree(Tree root) {
    if (root == NULL) return 1;
    if (root->left == NULL && root->right == NULL) return 1;
    if (root->left == NULL || root->right == NULL) return 0;
    return isRegularTree(root->left) && isRegularTree(root->right);
}

int main() {
    char preOrder[MAXSIZE], inOrder[MAXSIZE];
    scanf("%s%s", preOrder, inOrder);
    int n = strlen(preOrder);
    Tree root = buildTree(preOrder, inOrder, n);
    if (isRegularTree(root)) {
        printf("YES\n");
    } else {
        printf("NO\n");
    }
    return 0;
}