EB8-判断二叉树是否为正则二叉树

代码实现

计算型实现（推荐）

/**
 * 判断二叉树是否为正则二叉树（每个结点的度均为0或2）
 * 正则二叉树：所有非叶子结点都有两个子结点，叶子结点没有子结点
 * @param p 当前检查的二叉树结点
 * @return 1表示是正则二叉树，0表示不是正则二叉树
 */
int isRegularBinaryTree(BiTree p) {
    // 空树是正则二叉树（递归终止条件）
    if (p == NULL) {
        return 1;
    }

    // 检查当前结点是否违反正则二叉树的定义
    // 如果左子树为空而右子树不为空，或左子树不为空而右子树为空
    if ((p->lchild == NULL && p->rchild != NULL) ||
        (p->lchild != NULL && p->rchild == NULL)) {
        return 0;  // 不是正则二叉树
    }

    // 递归检查左子树是否为正则二叉树
    int leftResult = isRegularBinaryTree(p->lchild);

    // 递归检查右子树是否为正则二叉树
    int rightResult = isRegularBinaryTree(p->rchild);

    // 只有当左右子树都是正则二叉树时，整棵树才是正则二叉树
    return leftResult && rightResult;
}

操作型实现

/**
 * 判断二叉树是否为正则二叉树（操作型实现）
 * 使用标志位来记录判断结果
 * @param p 当前检查的二叉树结点
 * @param flag 指向判断结果的标志位指针（1表示是正则二叉树，0表示不是）
 */
void checkRegularBinaryTree(BiTree p, int *flag) {
    // 如果当前结点不为空且标志位仍为真，则继续检查
    if (p != NULL && *flag) {
        // 检查当前结点是否违反正则二叉树的定义
        // 度为1的结点（只有一个子结点）违反正则二叉树定义
        if ((p->lchild == NULL && p->rchild != NULL) ||
            (p->lchild != NULL && p->rchild == NULL)) {
            *flag = 0;  // 发现违规结点，设置标志位为假
        }

        // 递归检查左子树
        checkRegularBinaryTree(p->lchild, flag);

        // 递归检查右子树
        checkRegularBinaryTree(p->rchild, flag);
    }
}

正则二叉树概念说明

正则二叉树（Regular Binary Tree）也称为严格二叉树（Strict Binary Tree）： - 定义：每个结点要么是叶子结点（度为0），要么有两个子结点（度为2） - 特点：不存在度为1的结点 - 示例：

正则二叉树示例：
      A
     / \
    B   C
   / \ / \
  D  E F  G

非正则二叉树示例：
      A
     / \
    B   C
   /     \
  D       F

代码执行流程图解

正则二叉树示例：
       A
      / \
     B   C
    / \ / \
   D  E F  G

检查过程：
1. 检查A：有左右子树，符合要求
2. 检查B：有左右子树，符合要求
3. 检查C：有左右子树，符合要求
4. 检查D、E、F、G：都是叶子结点，符合要求
结果：是正则二叉树

非正则二叉树示例：
       A
      / \
     B   C
    /   / \
   D   E   F

检查过程：
1. 检查A：有左右子树，符合要求
2. 检查B：只有左子树，不符合要求！
3. 立即返回false（计算型）或设置flag=0（操作型）
结果：不是正则二Bruce树

优化版本

计算型优化版本（提前终止）

/**
 * 判断二叉树是否为正则二叉树（优化版-提前终止）
 * 一旦发现不满足条件的结点就立即返回
 * @param p 当前检查的二叉树结点
 * @return 1表示是正则二叉树，0表示不是正则二叉树
 */
int isRegularBinaryTreeOptimized(BiTree p) {
    // 空树是正则二叉树
    if (p == NULL) {
        return 1;
    }

    // 检查当前结点是否违反正则二叉树的定义
    if ((p->lchild == NULL && p->rchild != NULL) ||
        (p->lchild != NULL && p->rchild == NULL)) {
        return 0;  // 发现违规结点，立即返回
    }

    // 递归检查左子树，如果左子树不是正则二叉树，则立即返回
    if (!isRegularBinaryTreeOptimized(p->lchild)) {
        return 0;
    }

    // 递归检查右子树
    return isRegularBinaryTreeOptimized(p->rchild);
}

操作型优化版本（提前终止）

/**
 * 判断二叉树是否为正则二叉树（操作型优化版）
 * 发现违规结点后立即停止递归
 * @param p 当前检查的二叉树结点
 * @param flag 指向判断结果的标志位指针
 */
void checkRegularBinaryTreeOptimized(BiTree p, int *flag) {
    // 如果结点为空或已发现违规结点，则停止检查
    if (p == NULL || !(*flag)) {
        return;
    }

    // 检查当前结点是否违反正则二叉树的定义
    if ((p->lchild == NULL && p->rchild != NULL) ||
        (p->lchild != NULL && p->rchild == NULL)) {
        *flag = 0;  // 发现违规结点
        return;     // 立即返回，不再继续检查
    }

    // 递归检查左子树
    checkRegularBinaryTreeOptimized(p->lchild, flag);

    // 如果左子树检查通过，继续检查右子树
    if (*flag) {
        checkRegularBinaryTreeOptimized(p->rchild, flag);
    }
}

复杂度分析

时间复杂度：O(N)

• 最坏情况：整棵树都是正则二叉树，需要检查所有N个结点
• 最好情况：根结点就不满足条件，计算型优化版为O(1)，操作型为O(1)
• 平均情况：需要检查部分结点，但最坏情况主导，仍为O(N)

空间复杂度：O(N)

• 递归调用栈：
• 最坏情况下（完全不平衡的二叉树），递归深度为N，空间复杂度为O(N)
• 最好情况下（完全平衡的二叉树），递归深度为logN，空间复杂度为O(logN)
• 综合考虑，空间复杂度为O(N)

相关知识点延伸

1. 完全二叉树判断

/**
 * 判断是否为完全二叉树
 * 完全二叉树：除最后一层外，其它各层的结点数都达到最大值，
 * 且最后一层的结点都集中在左侧
 */
int isCompleteBinaryTree(BiTree root) {
    if (root == NULL) return 1;

    Queue q;
    initQueue(&q);
    enqueue(&q, root);
    int foundNull = 0;  // 标记是否遇到空位置

    while (!isEmpty(&q)) {
        BiTree p = dequeue(&q);

        if (p == NULL) {
            foundNull = 1;
        } else {
            if (foundNull) return 0;  // 在空位置后又发现非空结点
            enqueue(&q, p->lchild);
            enqueue(&q, p->rchild);
        }
    }

    return 1;
}

2. 满二叉树判断

/**
 * 判断是否为满二叉树
 * 满二叉树：所有叶子结点都在最后一层，且每个非叶子结点都有两个子结点
 */
int isFullBinaryTree(BiTree p) {
    if (p == NULL) return 1;

    // 叶子结点
    if (p->lchild == NULL && p->rchild == NULL) {
        return 1;
    }

    // 有两个子结点
    if (p->lchild != NULL && p->rchild != NULL) {
        return isFullBinaryTree(p->lchild) && isFullBinaryTree(p->rchild);
    }

    // 只有一个子结点
    return 0;
}

3. 二叉树性质相关

/**
 * 正则二叉树的性质验证
 * 对于有n个叶子结点的正则二叉树，总结点数为2n-1
 */
int verifyRegularTreeProperty(BiTree p) {
    if (p == NULL) return 1;

    int leafCount = 0, nodeCount = 0;
    countLeafAndNode(p, &leafCount, &nodeCount);

    return (nodeCount == 2 * leafCount - 1) ? 1 : 0;
}

void countLeafAndNode(BiTree p, int* leafCount, int* nodeCount) {
    if (p == NULL) return;

    (*nodeCount)++;
    if (p->lchild == NULL && p->rchild == NULL) {
        (*leafCount)++;
    }

    countLeafAndNode(p->lchild, leafCount, nodeCount);
    countLeafAndNode(p->rchild, leafCount, nodeCount);
}

4. 迭代实现方式

/**
 * 迭代方式判断正则二叉树
 */
int isRegularBinaryTreeIterative(BiTree root) {
    if (root == NULL) return 1;

    Stack s;
    initStack(&s);
    push(&s, root);

    while (!isEmpty(&s)) {
        BiTree p = pop(&s);

        // 检查当前结点是否违反正则二叉树定义
        if ((p->lchild == NULL && p->rchild != NULL) ||
            (p->lchild != NULL && p->rchild == NULL)) {
            return 0;
        }

        // 将子结点入栈
        if (p->rchild != NULL) push(&s, p->rchild);
        if (p->lchild != NULL) push(&s, p->lchild);
    }

    return 1;
}

使用示例

// 计算型使用示例
int main() {
    BiTree root = createTree();  // 假设已有创建树的函数

    if (isRegularBinaryTree(root)) {
        printf("这是一棵正则二叉树\n");
    } else {
        printf("这不是一棵正则二叉树\n");
    }

    return 0;
}

// 操作型使用示例
int main() {
    BiTree root = createTree();
    int flag = 1;  // 初始假设是正则二叉树

    checkRegularBinaryTree(root, &flag);

    if (flag) {
        printf("这是一棵正则二叉树\n");
    } else {
        printf("这不是一棵正则二叉树\n");
    }

    return 0;
}

关键要点总结

1. 定义理解：正则二叉树要求每个结点的度只能是0或2，不能是1
2. 递归思想：整棵树是正则二叉树当且仅当根结点满足条件且左右子树都是正则二叉树
3. 边界处理：空树被认为是正则二叉树
4. 效率优化：可以在发现违规结点后立即停止检查
5. 两种实现方式：
6. 计算型：通过返回值传递结果
7. 操作型：通过参数指针传递结果

这个算法体现了树结构判断类问题的典型解法，理解其工作原理有助于掌握更复杂的树性质判断算法。