性质2:深度为k的二叉树至多有2k-1个结点(k>=1) 深度为k的二叉树的最大的结点数为二叉树中每层上的最大结点 数之和,由性质1得到每层上的最大结点数, ∑(第禔层上的最大结点数)=∑21=24-1 性质3:对任何一棵二叉树T,如果其终端结点数为no,度为2的 结点数为n2,则no=n2+1。 设二叉树中度为1的结点数为n1,二叉树中总结点数为N,因为二 叉树中所有结点均小于或等于2,所以有: notn,tn2 (6-1) ●再看二叉树中的分支数,除根结点外,其余结点都有一个进入分 支,设B为二叉树中的分支总数, ●则有 N=B+1。 北京邮电大学自动化学院北京邮电大学自动化学院 9 ⚫ 性质2：深度为k的二叉树至多有2 k－1个结点（k>=1). 2 2 1 1 1 1  =  = − = = − k k i k i i （第i层上的最大结点数） ⚫ 性质3： 对任何一棵二叉树T，如果其终端结点数为n0，度为2的 结点数为n2，则n0＝n2＋1。 ⚫ 深度为k的二叉树的最大的结点数为二叉树中每层上的最大结点 数之和，由性质1得到每层上的最大结点数， ⚫ 设二叉树中度为1的结点数为n1，二叉树中总结点数为N，因为二 叉树中所有结点均小于或等于2，所以有： ⚫ N＝n0＋n1＋n2 (6-1) ⚫ 再看二叉树中的分支数，除根结点外，其余结点都有一个进入分 支，设B为二叉树中的分支总数， ⚫ 则有： N＝B＋1