二叉树
节点度数 不超过2 的树称作二叉树 (binary tree)
同一节点的孩子和子树，均以左、右区分
lChild() ~ lSubtree()
rChild() ~ rSubtree()
隐含有序
基数
深度为 $ k $ 的节点，至多 $ 2^k $ 个
含 $ n $ 个节点、高度为 $ h $ 的二叉树中，$ h < n < 2^(h+1)$
当 $ n = h + 1 $ 时，二叉树退化为一条单链
当 $ n = 2^(h+1) - 1 $ 时，即所谓满二叉树 (full binary tree)
真二叉树
所谓真二叉树，就是节点的出度只能为 2 或 0 的二叉树
用二叉树描述多叉树
二叉树是多叉树的特例，但在有根且有序时，其描述能力却足以覆盖后者
多叉树均可转化并表示为二叉树 —— 回忆长子兄弟表示法
本文由
Oscaner
创作, 采用
知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外, 均为本站原创或翻译, 转载前请务必署名
