n个节点的链表有多少个非空指针域

问题描述

精选答案

若二叉树用二叉链表作存贮结构,则在 n 个结点的二叉树链表中只有 n—1 个非空指针域。n个节点的二叉树中，每个节点有两个链域，也就是2n个，除了根节点外，每个节点能且只能被指一次，所以有n-1个指针域非空，空指针域 = 2 n − ( n − 1 ) = n + 1 2n-(n-1) = n+1 2n−(n−1)=n+1.