离散数学二叉树

本文概述

  • 基本术语
  • 二元表达树
  • 区分一般树和二叉树
如果在有向树中每个节点的外度小于或等于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的左子。

    推荐阅读