数据结构中用二叉链表保存有n个结点的二叉树，则结点中有n+1个空指针域，问这个n+1是怎么出来的？

如题，问一下这个n+1是怎么出来的，我应该怎样理解这到题呢

推荐答案 2017-10-22

n个结点的二叉树有n+1个空指针。
下面用数学归纳法证明。

证明：n=1时，1个结点的二叉树有2个空指针域，成立。
假设当n=k时成立，即k个结点的二叉树有k+1个空指针。
那么，放入第k+1个结点会占用一个空指针，然后又产生2个空指针
所以，k+1个结点有k+1-1+2=k+2个空指针，即当n=k+1时也成立。
所以假设成立。

温馨提示：答案为网友推荐，仅供参考

当前网址：http://88.wendadaohang.com/zd/MVcBBMS1M1ggctBBVaa.html

其他回答

第1个回答 2019-04-06

因为n个节点有2n个指针
又因为n个节点中有n-1条边（除了头结点没有边，其余节点都有一个父节点，相当于都有1条边，共n-1条）
剩下的空链域就是2n-(n-1)=n+1，即n+1个空指针

相似回答

为什么n各节点的的二叉链表中有n+1个空链域答：剩下的空链域就是2n-(n-1)=n+1，即n+1个空指针 以二叉链表作为树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。

...二叉树的储存结构,在具有n个结点的二叉链表中n(n>0),空链域的个数...答：以二叉链表作为二叉树的储存结构，在具有n个结点的二叉链表中n（n＞0），空链域的个数为n+1。二叉链表结构描述：typedef struct CSNode{ ElemType data;struct CSNode *firstchild ， *netsibling;} CSNode，* CSTree;由于二叉树的存储结构比较简单，处理起来也比较方便，所以有时需要把复杂的树，...

在一颗二叉树中,假设有N个结点,那么有多少答：有n+1个为空指针。（用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。由于二叉树中，除根结点外，每一个结点有且仅有一个双亲，所以只有n-1个结点的链域存放指向非空子结点的指针，还有n+1个空指针。）即有后继链接的指针仅n-1个。除根节点外，每个节点都有且仅有一个射向自己的分支...

证明含有n个结点的二叉链表中共有n+1个空链域答：可以这样考虑，链域一共有2*n个，（每个点有两个鲢鱼），对于除了根节点以外的每个点都是有一个父亲节点，所以一共有n-1个指针指向某个节点，形成n-1个有东西的链域（减1即是父亲节点）所以一共有2*n-(n-1)=n+1个链域没有指向任何东西参考资料：本人大脑 ...

数据结构的线索二叉树,为什么在有n个结点的二叉链表中必定存在n+1个...答：n个结点的二叉链表中必定存在n＋1个空链域 因为n个结点的二叉链表中有2n个孩子指针,而n个结点除根结点外,均有一个指针指向它,所以2n-(n-1)=n+1个指针是空的

n个结点的二叉链表表示的二叉树中共有n+1个空链域。答：则对应的指针为空（NULL），也就是说，这个指针指向了一个空链域。在一个有 n 个结点的二叉链表表示的二叉树中，每个结点都有左子树指针和右子树指针，因此一共有 n2 个指针。又因为根结点没有父节点，所以它的指针不算在空链域中。因此，该二叉树中的空链域数目是 n2-1，而不是 n+1。

...在有n个节点的二叉链表中,一定存在n+1个空链域,怎么理解啊?什么是...答：呵呵，这个吗，首先每两个之间都可以有2*n个域，如A 和B 可以有A->B和B->A；而我们知道总共n个点就只有n-1条边，说以说空链域2n-(n-1)=n+1;数据结构最好那本好书看看，厚点的好，很重要的

用二叉链表存储包含N个结点的二叉树,结点的2N个指针域中有N+1个空指...答：二叉树的节点都有2个指针。每个节点有0个、1个或2个空指针。对应的有2个、1个、0个非空指针。非空指针的总数就是二叉树的边的个数。设一个二叉树x个节点含有0个空指针，y个节点有1个空指针，z个节点有2个空指针有如下等式 1、 x+y+z=N 节点总数为N，题目叙述 2、 y+2*z=N+1空...

大家正在搜

二叉链表中空链域的个数二叉树只能用二叉链表表示统计二叉树中叶子节点的个数二叉树叶子结点数怎么算对于一棵具有n个节点的二叉树以二叉链表为存储结构利用二叉链表存储树深度为5的二叉树至多有几个节点设计算法求二叉树的节点个数