|
|
知识路径： > 计算机科学基础 > 常用数据结构 > 树 > 树和二叉树 >
|
被考次数：2次
被考频率：低频率
总体答错率：57%
知识难度系数： 
|
由 软考在线 用户真实做题大数据统计生成
|
|
相关知识点：11个
|
|
|
|
|
|
|
性质1在二叉树的第i层上至多有2i-1个节点（i≥1）。
|
|
|
|
性质2深度为k的二叉树至多有2k-1个节点（k≥1）。
|
|
|
|
性质3对任何一棵二叉树T，如果其终端节点数为n0，度为2的节点数为n2，则n0=n2+1。
|
|
|
|
性质4具有n个节点的完全二叉树的深度为[log2n]+1。
|
|
|
|
性质5如果有n个节点的完全二叉树，对任一节点i（1<i≤n）满足：
|
|
|
|
.如果i=1，则i为根，无双亲；若i>1，则i的双亲为[i/2]。
|
|
|
|
|
|
.如果2i+1>n，则无右孩子，否则右孩子为2i+1。
|
|
|
|
二叉树的有关性质可推广到k叉树，如：一棵含有n个节点的二叉树共含有n+1个空指针；而一棵含有n个节点的三叉树共含有2n+1个空指针。推而广之，一棵含有n个节点的k叉树共含有（k-1）n+1个空指针。
|
|
|
|
不难看出，在k叉树的第i层上至多有ki-1个节点（i≥1）；深度为H的k叉树至多有（kH-1）/（k-1）个节点（H≥1）。
|
|
|
|
同理，可得到含N个节点和N个叶子节点的完全三叉树的高度分别为：
|
|
|
|
|
|
|
|
（1）设含N个节点的完全三叉树的高度为H，则1+3+…+3H-2+1≤N≤1+3+…+3H-1, 3H-1≤2N-1≤3H-2，即H=[log32N-1]+1。
|
|
|
|
（2）设含N个叶子节点的完全三叉树的高度为H，则3H-2≤N≤3H-1，即
|
|
|
|
|
|
|
|
|
