满二叉树和正则二叉树

满二叉树是一种特殊的二叉树结构，其中每个节点最多有两个子节点，并且除了最后一个层次外，每一层的节点都被完全填满。换句话说，从根节点到最底层的所有叶子节点都形成连续的层。如果树的高度为h，那么它有2^(h-1)个节点。

正则二叉树，也称为梅森树或完全二叉树，它与满二叉树类似，但是最后一个层次的节点可以不满。也就是说，除最后一层外，所有其他层都是完全填充的，而最后一层的节点从左向右排列，尽可能多地占据空间，但允许左边还有空位。这种特性使得正则二叉树常用于构建哈夫曼树（最优二叉树）等数据结构中。

相关问题

完全二叉树和正则二叉树

完全二叉树是一种特殊的二叉树，其中除了最后一层，其他层的节点都是满的，最后一层的节点都靠左排列。正则二叉树是一种特殊的二叉树，其中每个节点要么没有子节点，要么有两个子节点。

完全二叉树和正则二叉树的区别在于，完全二叉树可以有只有一个子节点的节点，而正则二叉树不可以。另外，完全二叉树的高度可以是 $log_2(n)$，其中 $n$ 是节点数，而正则二叉树的高度可以是 $n$，其中 $n$ 是节点数。

需要注意的是，完全二叉树和正则二叉树并不是互斥的概念。例如，一个只有根节点的二叉树既是完全二叉树，也是正则二叉树。

用c语言判断一颗二叉树是不是正则二叉树

在C语言中，判断一个二叉树是否是正则二叉树可以使用递归的方式。首先定义一个辅助函数来检查某个节点是否符合正则二叉树的规则，然后主函数对根节点进行判断并递归处理左右子树。以下是简单的伪代码和步骤：

1. 定义一个结构体表示二叉树节点，包含指向前一个、后一个和左右孩子的指针。
2. 设计一个函数`isRegularBST(node *root)`，接受一个二叉树节点作为输入。
3. 函数内部先检查根节点是否为NULL，然后检查特殊情况：如果根节点为叶节点（无左右子节点），直接返回真；
4. 对于非叶节点，分别检查左子树和右子树是否都是正则二叉树，且左子树的最后一个节点的右孩子应该是当前节点；
5. 使用递归，分别调用`isRegularBST(leftChild)`和`isRegularBST(rightChild)`；
6. 如果上述条件全部满足，返回真，否则返回假。

// 假设有一个二叉树结构体定义为TreeNode
bool isRegularBST(TreeNode* root) {
    if (root == NULL) return true; // 空树或叶节点视为正则二叉树

    if (!isRegularBST(root->left)) return false; // 左子树不是正则二叉树直接返回false
    if (root->left->last != NULL && root->left->last->right != root) return false; // 检查左子树最后一个节点的右孩子

    if (!isRegularBST(root->right)) return false; // 右子树不是正则二叉树

    return true;
}