离散数学二叉树

本文概述

• 基本术语
• 二元表达树
• 区分一般树和二叉树

如果在有向树中每个节点的外度小于或等于2, 则该树称为二叉树。由节点组成的树（空树）也是二叉树。二叉树如图所示：

基本术语

根：二叉树有一个唯一的节点, 称为树的根。

左子节点：根左侧的节点称为其左子节点。

右子节点：根右边的节点称为其右子节点。

父节点：具有左子节点或右子节点或两者都有的节点称为节点的父节点。

兄弟姐妹：具有相同父节点的两个节点称为兄弟姐妹。

叶子：没有子节点的节点称为叶子。一棵二叉树的叶子数量可以从一棵树（最少）到一半数目（最大）不等。

后代：如果某个节点是该节点的子代或该节点的其他后代的子代, 则该节点称为另一个节点的后代。树中的所有节点都是根的后代。

左子树：其根是某个节点的左子节点的子树称为该节点的左子树。

示例：对于如图所示的树：

• 根是哪个节点？
• 哪些节点是叶子？
• 命名每个节点的父节点

解决方案：（i）节点A是根节点。 （ii）节点G, H, I, L, M, N, O是叶子。 （iii）节点父B, C A D, E B F C G, H D I, J E K F L, M J N, O K

右子树：根是某个节点的右子节点的子树称为该节点的右子树。

节点的级别：节点的级别是其与根的距离。根级别定义为零。所有其他节点的级别比其父节点多一。任何级别N的最大节点数为2N。

树的深度或高度：树的深度或高度定义为树的一个分支中的最大节点数。这大于树的最大级别, 即根的深度为1。深度为d的二叉树中的最大节点数为2d-1, 其中d≥1。

外部节点：没有子节点的节点称为外部节点或终端节点。

内部节点：具有一个或多个子节点的节点称为内部节点或非终端节点。

二元表达树

代数表达式可以通过其表达式树方便地表示。具有二进制运算符的表达式可以分解为<left操作数或expression>（operator）<right操作数或expression>

取决于评估的优先级。

表达式树是一个二叉树, 其根包含运算符, 左子树包含左表达式, 右子树包含右表达式。

示例：为表达式（a + b）*（d / c）构造二进制表达式树

解决方案：表达式（a + b）*（d / c）的二进制表达式树如图所示：

完整的二叉树：完整的二叉树是一个二叉树, 如果它的所有级别（除了最后一个级别）都具有尽可能多的节点。具有n个节点的完整二叉树的深度为log2 n + 1。

示例：图中所示的树是完整的二叉树。

完整的二叉树：完整的二叉树是一个二叉树, 其中所有叶子都处于同一级别, 每个非叶子节点都有两个子节点。

区分一般树和二叉树