二叉树的概念

二叉树的概念

树的基本概念

• 有序树：若兄弟之间有序，则称为有序树
• 深度：根到节点的路径经过的边数，根的深度为 0
• 树的高度：所有节点的最大深度，空树的高度为-1
• 节点的高度：后代的最大深度-自身深度
• 二叉树：节点度数不超过 2

特殊类型的二叉树

• 真二叉树：每个节点或有两个子节点，或没有子节点
• 满树：深度为 $k$ 的节点恰有 $2^k$ 个
• 多叉树与二叉树：通过长子和兄弟表示，可以将任意多叉树转化为二叉树