为什么n各节点的的二叉链表中有n+1个空链域

发布网友发布时间：2022-04-19 09:51

共5个回答

热心网友时间：2023-10-23 21:44

因为n个节点有2n个指针

又因为n个节点中有n-1条边

除了头结点没有边，其余节点都有一个父节点，相当于都有1条边，共n-1条

剩下的空链域就是2n-(n-1)=n+1，即n+1个空指针

以二叉链表作为树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。

扩展资料：

typedef　struct CSNode{

ElemType data；

struct CSNode *firstchild ， *netsibling；

} CSNode，* CSTree；

由于二叉树的存储结构比较简单，处理起来也比较方便，所以有时需要把复杂的树，转换为简单的二叉树后再作处理。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。

热心网友时间：2023-10-23 21:44

很简单，因为每一个节点有左右两个指针，n个节点共有2n个链域，
而n个节点只需用n-1个指针就可互连（因为连接n个点只需n-1条直线），
所以还剩下2n-(n-1)=n+1个。

热心网友时间：2023-10-23 21:45

n个节点有2n个指针
数学中n个点中有几个线段？
n个节点用n-1个线就可以链接起来
剩下的不就是2n-(n-1)=n+1个空指针

热心网友时间：2023-10-23 21:45

可以这样考虑，链域一共有2*n个，（每个点有两个鲢鱼），对于除了根节点以外的每个点都是有一个父亲节点，所以一共有n-1个指针指向某个节点，形成n-1个有东西的链域（减1即是父亲节点）所以一共有2*n-(n-1)=n+1个链域没有指向任何东西

热心网友时间：2023-10-23 21:46

把空链域当做新的叶结点，这样树原来的结点度全为2，又由于度为0的节点数等于度为2的节点数+1，那么空链域的值就等于n+1