网络收藏

设t为扩充2叉树或2-树。即t为每个点n或没有孩子或有两个孩子的二叉树，没有孩子的点秋为外点，而有两个孩子的点称为内点。  
          书上说，若t有n个外点，则t有n-1个内点。请问这是为什么？

推荐阅读

n=1   显然成立  
   
  假设n=1,3,...,2*k-1   成立，内节点为k-1，外界点k  
  那么n=2*k+1=根＋左子树＋右子树=1+1+2*k-1=1+3+2*k-3.....,显然1个节点退化成内节点，所以  
           
  内节点＝左子树内节点＋右子树内节点＋根=1+(k-2)+1=2+(k-3)+1...=k  
  外节点＝左子树外节点+右子树外节点＝1+k=2+(k-1)=3+(k-2)=k+1