若二叉树用二叉链表做存储结构，则在N个结点的二叉树链表中只有N-1个非空指针域

求详解

2024年11月17日 21:24

有3个网友回答

网友（1）：

其实可以这样理解：N个节点的二叉树，若用二叉链表表示则每个节点都有两个链域也就是2N个，然后除了根节点外每个节点都能但只能被指一次，所以有N-1个链域不为空因而有N+1个链域为空,,

网友（2）：

一棵有n个结点的二叉树，除了根结点之外，其余每个结点均有一个出自其双亲的指针域的指向该结点的指针，因此，共有n-1个指针域非空。指针域的总数目为2n，所以恰好有n+1个空指针域。结合二叉树的链接表示图，可以更清晰的看出。或者采用特殊值，自己动手画出。
数据结构考点:二叉树的存储表示

网友（3）：

怎么说呢，假如有三个结点一个头结点和两个子节点，那么在头结点的指针域里面放的是两个子节点的地址，在子节点里面的指针域里都为NULL，这样就有两个指针域非空；
再假如有5个结点头结点两个，左子树有两个，也符合N-1个非空指针域；

这样可以么？希望您能明白。