为什么在有N个结点且为完全二叉树的二叉搜索树中查找一个键值，其平均比较次数的数量级为

log2(N)？

对于完全二叉树的二叉搜索树，每个结点最多有两个子结点，且左子树中的所有键值小于该结点的键值，右子树中的所有键值大于该结点的键值。因此，在查找某个键值时，我们可以从根结点开始，每次比较当前结点的键值和要查找的键值，然后继续向左子树或右子树搜索，直到找到该键值或搜索到叶子结点为止。

由于完全二叉树的深度为log2(N)，因此在最坏情况下，需要比较log2(N)次才能找到要查找的键值。但是，在平均情况下，由于二叉搜索树的键值是随机分布的，每个结点的左右子树的大小也是随机的，因此每次比较的次数并不是固定的。根据概率论的知识，可以证明在平均情况下，每次比较的次数的期望值为log2(N)。因此，平均比较次数的数量级为log2(N)。

相关问题

C语言代码创建一个有n个结点的二叉链存储结构完全二叉树和非完全二叉树、判断该二叉树是否为完全二叉树

创建一个有n个结点的完全二叉树可以采用数组来存储，而非完全二叉树则需要使用链表来存储。以下是完全二叉树和非完全二叉树的创建方法：

完全二叉树的创建：

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

#define MAXSIZE 100

typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
}TreeNode, *Tree;

Tree CreateCompleteBinaryTree(int arr[], int n)
{
    Tree t[MAXSIZE];
    for (int i = 1; i <= n; i++) {
        t[i] = (TreeNode *)malloc(sizeof(TreeNode));
        t[i]->data = arr[i - 1];
        t[i]->left = t[i]->right = NULL;
    }
    for (int i = 1; i <= n / 2; i++) {
        if (i * 2 <= n) t[i]->left = t[i * 2];
        if (i * 2 + 1 <= n) t[i]->right = t[i * 2 + 1];
    }
    return t;
}

int main()
{
    int arr[] = {1, 2, 3, 4, 5, 6};
    int n = sizeof(arr) / sizeof(int);
    Tree root = CreateCompleteBinaryTree(arr, n);
    return 0;
}

非完全二叉树的创建：

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

typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
}TreeNode, *Tree;

void CreateNonCompleteBinaryTree(Tree *root)
{
    int val;
    scanf("%d", &val);
    if (val == -1) {
        *root = NULL;
        return;
    }
    *root = (TreeNode *)malloc(sizeof(TreeNode));
    (*root)->data = val;
    CreateNonCompleteBinaryTree(&((*root)->left));
    CreateNonCompleteBinaryTree(&((*root)->right));
}

int IsCompleteBinaryTree(Tree root)
{
    if (root == NULL) return 1;
    int level = 0;
    Tree q[MAXSIZE];
    int front = -1, rear = -1;
    q[++rear] = root;
    while (front != rear) {
        int len = rear - front;
        level++;
        while (len--) {
            front++;
            if (q[front] == NULL) {
                for (int i = front + 1; i <= rear; i++) {
                    if (q[i] != NULL) return 0;
                }
                return 1;
            }
            q[++rear] = q[front]->left;
            q[++rear] = q[front]->right;
        }
    }
    return 1;
}

int main()
{
    Tree root;
    CreateNonCompleteBinaryTree(&root);
    int isComplete = IsCompleteBinaryTree(root);
    if (isComplete) printf("This is a complete binary tree\n");
    else printf("This is not a complete binary tree\n");
    return 0;
}

判断二叉树是否为完全二叉树的方法：

在层次遍历的过程中，如果某个结点的左子树为空，而右子树不为空，则该树不是完全二叉树；或者在某一层中，如果某个结点没有左子树或右子树，那么这个结点后面的所有结点都必须是叶子结点，否则该树不是完全二叉树。

含有n个结点的二叉树的二叉链表中，其空的指针域的个数为

### 回答1：
对于一颗含有n个结点的二叉树，它的二叉链表中会包含2n个指针域，因为每个结点都有一个左孩子指针和右孩子指针，所以总共有2n个指针域。

又因为每个非叶子结点都有两个孩子指针，而叶子结点没有孩子指针，所以一颗含有n个结点的二叉树中叶子结点的个数为n/2（向上取整）。

因此，空的指针域的个数就是2n-（n/2），即3n/2。

### 回答2：
含有n个结点的二叉树的二叉链表中，空的指针域个数为n+1。

首先，二叉树中的每个结点除了包含数据域之外，还包含指向左子结点和右子结点的指针域。而对于每个结点而言，如果存在左子结点，则其左子结点的指针域不为空；如果存在右子结点，则其右子结点的指针域不为空。所以，空的指针域的数量等于不存在左子结点和右子结点的结点数量加1。

另一方面，一棵二叉树的总结点个数为n，其中每个结点都有两个指针域，也就是说总共有2n个指针域。而空的指针域不能够指向有效的结点，所以空的指针域的数量等于总指针域的数量减去有效指针域的数量。

有效指针域的数量可以通过计算每个结点的左子结点和右子结点的个数来得到。考虑到左子结点和右子结点也是二叉树的结点，而且二叉树中的结点总数为n，所以左子结点和右子结点的总数即为n。因此，有效指针域的个数为n。

综上所述，空的指针域的个数为2n - n = n，即n+1。

### 回答3：
含有n个结点的二叉树的二叉链表中，其空的指针域的个数为n+1。

二叉链表是一种以结点作为基本元素组成的链式存储结构，在每个结点中，都包含了指向该节点的左子树和右子树的指针。在二叉链表中，如果某个结点没有左子树或右子树，那么该结点的指针域为空。

对于一棵含有n个结点的二叉树，由于每个结点都包含左子树和右子树的指针域，总共需要(n+1)*2个指针域。然而，其中有n个结点的左子树和右子树正好占用了n*2个指针域，因此多出来的2个指针域是用于指向二叉树的根结点的。

所以，含有n个结点的二叉树的二叉链表中，其空的指针域的个数为n+1。