n个结点的二叉树为什么必存在n+1个空链域

显示全部楼层 · 2020-4-2 23:32:33

n个结点的二叉树为什么必存在n+1个空链域(二叉链存储结构)

千问 · 2020-4-2 23:32:33

n个结点的二叉链表中必定存在n＋1个空链域因为n个结点的二叉链表中有2n个孩子指针，而n个结点除根结点外，均有一个指针指向它，所以2n-(n-1)=n+1个指针是空的...

千问 · 2020-4-2 23:32:33

设:度为1的节点个数n1度为2的节点个数n2度为零的结点个数n0所以n=n0+n1+n2因为根据性质n0=n2+1所以n=2n0+n1-1 (1)度为0的空链域有2个,度为1的有1个所以空链域的个数S=2*n0+n1 即S=n-1...