11、有n（n>0）个结点的二叉树，采用二叉链表作为存储结构，则二叉链表中空指针的个数为________。

一棵有n个结点的二叉树，它的链表中包含2n个指针，其中n+1个是指向结点的指针，另外n-1个是指向空指针的指针。

这里的n+1个指针包括根结点的指针和每个非叶子结点的左右子树指针。因为一棵有n个结点的二叉树中有n-1条边，所以有n个结点的二叉树中有n+1个指向结点的指针。

又因为采用二叉链表作为存储结构，每个结点都需要包含左右子树的指针，因此每个结点会贡献两个指针。因为有n个结点，所以总共有2n个指向结点的指针。

而每个结点的左右子树指针都有可能是空指针，因此总共有2n个指向空指针的指针。

因此，二叉链表中空指针的个数为2n个。

相关问题

含有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。

若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。

### 回答1：
这道题主要考察二叉树和链表的操作，给定一个二叉树，要求将其转换为链表存储，最后返回链表的头节点。在实现过程中需要注意细节，比如遍历二叉树的顺序以及如何将左子树和右子树的节点拼接到一起。在函数的参数中，n表示二叉树的节点个数，1个非空指针域 + 1个非空数据域，只有n-1个非空指针和n个非空数据正好满足二叉树的性质，因此只能有n-1个非空指针域作为节点，剩下的一个非空数据域则可以作为头节点。

### 回答2：
二叉树是一种树形数据结构，其中每个节点最多拥有两个子节点，被称为左子树和右子树。二叉树可以用数组、链表等不同的数据结构来存储。其中，采用二叉链表作为存储结构的方式，是最常见的一种方式。

二叉链表是指每个节点有三个域：一个数据域，以及两个指针域，分别指向该节点的左子树和右子树。如果某个节点没有左子树或右子树，则对应的指针域为空。因此，对于一个二叉树的二叉链表，在n个节点的情况下，总共有2n个指针域。但实际上，只有n-1个指针域是非空的。

为什么会出现这种情况呢？我们可以从二叉树的特性入手。在一个二叉树中，每个节点都只有一个父节点（根节点除外）。因此，对于除了根节点之外的所有节点来说，它们都是通过其父节点连通到根节点的。也就是说，对于一棵n个节点的二叉树，它有n-1条边，也就是n-1个节点之间的连线。而在二叉链表中，每个节点的两个指针域分别指向左子树和右子树。因此，正好有n-1个指针域是连接这n-1条边的。

从这个角度来看，可以理解为什么在n个节点的二叉树链表中，只有n-1个非空指针域了。这也是二叉树二叉链表存储结构的一个实际问题，因为存在很多指针域是空的情况，所以需要特殊处理。比如，在遍历二叉树过程中，需要判断每个节点指针域是否为空，以确定是否需要遍历它的左子树或右子树。在对二叉树进行插入、删除等操作时，也需要特别注意空指针的情况，否则会出现指针错误等问题。

总而言之，采用二叉链表作为二叉树的存储结构，能够满足不同需求的应用场景。但是，需要注意空指针域的问题，以保证程序正确性。

### 回答3：
二叉树是一种树形结构，由节点和连向子节点的指针组成，每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树可以用数组、链表或其他数据结构进行存储，而二叉链表是一种常见的存储结构。在二叉链表中，每个节点包含一个数据域和两个指针域，分别指向左子节点和右子节点。当一个节点没有左子节点或右子节点时，对应的指针域为空。

由于二叉树是一种树形结构，每个节点最多有两个子节点，因此在n个结点的二叉树中，最多有n*2个指针。而二叉链表中，每个节点只有两个指针域，因此有些指针域会为空，即某些节点没有左子节点或右子节点。因此，在n个结点的二叉树链表中，只有n-1个非空指针域。

这个结论可以通过归纳法证明。对于只有一个节点的二叉树，显然只有一个非空指针域。假设对于任意n-1个节点的二叉树，它们的链表表示中只有n-2个非空指针域。现在考虑一个有n个节点的二叉树，它的左子树有k个节点，右子树有n-k-1个节点（其中k为0到n-1之间的整数）。由归纳假设可知，左子树和右子树的链表表示中分别有k-1和n-k-2个非空指针域。因此，整棵树的链表表示中共有k+n-k-1=n-1个非空指针域，证毕。

总之，若二叉树用二叉链表作存储结构，则在n个结点的二叉树链表中只有n-1个非空指针域。这个结论在算法分析和二叉树操作中有重要的应用。