含有n个结点的二叉链表中的空链域链表中链域一共有2*n个(每个点有两个链域)。
对于除了根结点以外的每个点都是有一个父亲结点所以一共有n-1个指针指向某个结点,
於是形成n-1个有内容的链域(减1即是父亲结点)所以一共有2*n-(n-1)=n+1个链域没有指向任何东西
二叉链表中的空链域树中:结点数n=n1+n2+n0,(n0是度数为0的结点,吔称叶子结点;n1是度数为1的结点;n2是度数为2的结点)
解释为什么n0=n2+1(非空二叉链表中的空链域树上叶子结点数等于度数为2的结点数+1)
证明:设喥数为0,1,2的结点个数分别为N0N1,N2结点总数为N=N0+N1+N2
再看二叉链表中的空链域树中的分支数,除了根节点外其余结点都有一个分支进入,设B为分支总数则N=B+1。
由于这些分支是由度数为1或者2的结点射出来的所有又有B=1*N1+2*N2