离散数学二叉树 _离散数学二叉树

本文概述

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

如果在有向树中每个节点的外度小于或等于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。
示例：图中所示的树是完整的二叉树。

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

区分一般树和二叉树

普通树	二叉树
1.没有这样的树, 它有零个节点或一个空的通用树。	1.可能有一个空的二叉树。
2.如果某个节点有孩子, 则没有这种区别。	2.如果某个节点有一个孩子, 则将其区分为左孩子或右孩子。
3.当我们将它们视为普通树时, 图中显示的树是相同的。	3.当我们将它们视为二叉树时, 图中所示的树是不同的, 因为（4）中的树是2的右子, 而（ii）4中的树是2的左子。