数据结构中用二叉链表保存有n个结点的二叉树，则结点中有n1个空指针域，问这个n1是怎么出来的？
推荐回答
一棵有n个结点的二叉树，除了根结点之外，其余每个结点均有一个出自其双亲的指针域的指向该结点的指针，因此，共有n-1个指针域非空。指针域的总数目为2n，所以恰好有n+1个空指针域。结合二叉树的链接表示图，可以更清晰的看出。或者采用特殊值，自己动手画出。数据结构考点:二叉树的存储表示。
齐新萍2019-12-21 18:58:28
提示您：回答为网友贡献，仅供参考。
其他回答
-
500个结点，深度最少为9，完全9层二叉树501个结点，最后一层共256个点，但少一个点，所以空指针域是256*2-2+1＝501。
黄目张2019-12-21 19:39:35
-
有n+1个为空指针。所以N个节点的二叉树，需要N-1个指针域，空余N+1个n个节点则有2n个链域,除了根节点没有被lchild和rchild指向,其余的节点必然会被指到.所以空链域公有2n-n-1=n+1;非空链域有2n-n+1=n-1；在一棵二叉树的二链表中,空指针域数等于结点数加什么一颗二叉树中，假设有N个点，则有N+1个空指针域，N-1个非空域n个结点的二叉链表中必定存在n＋1个空链域因为n个结点的二叉链表中有2n个孩子指针,而n个结点除根结点外,均有一个指针指向它,所以2n-n-1=n+1个指针是空的。
连亚琴2019-12-21 19:15:21