二叉树结点入度等于出度
根据这一定理,可以衍生出许多计算题
例如给出不同出度的结点个数
如出度为2的点有a个,1的有b个,求叶子结点数
首先要知道一棵有n个结点的二叉树,总入度为n-1,因为除了根节点外每个结点的入度均为1
因此可以列出方程计算
n-1=a2+b1+x
又例如问线索二叉树的线索数
n个点的二叉树共有2n个可以放置线索的位置,其中出度等于入度等于n-1,剩余可以放置线索的位置是 2n-(n-1)=n+1
根据这一定理,可以衍生出许多计算题
例如给出不同出度的结点个数
如出度为2的点有a个,1的有b个,求叶子结点数
首先要知道一棵有n个结点的二叉树,总入度为n-1,因为除了根节点外每个结点的入度均为1
因此可以列出方程计算
n-1=a2+b1+x
又例如问线索二叉树的线索数
n个点的二叉树共有2n个可以放置线索的位置,其中出度等于入度等于n-1,剩余可以放置线索的位置是 2n-(n-1)=n+1
相关推荐