树与二叉树的基本概念

树

树(Tree)是 n(n≥0)个结点的有限集。n=0 时为空树。在任意一棵非空树中:

  • 有且仅有一个根结点(root)
  • 其余结点可分为 m(m>0)个互不相交的有限集 T1,T2,…,TmT_1, T_2, \ldots, T_m,每个集合本身又是一棵树,称为根的子树

树的常用术语

  • 结点的度:结点拥有的子树个数
  • 树的度:树内各结点度的最大值
  • 叶子结点(终端结点):度为 0 的结点
  • 分支结点(非终端结点):度大于 0 的结点
  • 层次:根为第 1 层,根的孩子为第 2 层,依此类推
  • 深度(高度):结点的最大层次数
  • 森林:m(m≥0)棵互不相交的树的集合

树的性质

  1. 树中的结点数等于所有结点的度数之和加 1
  2. 度为 m 的树中,第 i 层上至多有 mi−1m^{i-1} 个结点(i≥1)
  3. 深度为 h 的 m 叉树至多有 mh−1m−1\frac{m^h-1}{m-1} 个结点

二叉树的定义

二叉树

二叉树(Binary Tree)是 n(n≥0)个结点的有限集,每个结点至多有两个孩子(左孩子、右孩子),且左右子树有严格的次序,不能颠倒。

二叉树的性质

  1. 非空二叉树的第 i 层上至多有 2i−12^{i-1} 个结点
  2. 深度为 h 的二叉树至多有 2h−12^h-1 个结点
  3. 对任意二叉树,叶子结点数 n0n_0 与度为 2 的结点数 n2n_2 满足:n0=n2+1n_0 = n_2 + 1
  4. 具有 n 个结点的完全二叉树的深度为 ⌊log⁡2n⌋+1\lfloor \log_2 n \rfloor + 1

特殊二叉树

  • 满二叉树:每层结点数都达到最大,叶子都在最底层
  • 完全二叉树:除最后一层外每层都满,最后一层的结点都集中在左侧连续位置
  • 二叉排序树(BST):左子树所有结点值 < 根 < 右子树所有结点值
  • 平衡二叉树(AVL):任意结点左右子树高度差不超过 1

习题

习题 1

在一棵二叉树中,度为 2 的结点数为 5,则叶子结点数为( )

A. 4 B. 5 C. 6 D. 无法确定

二叉树叶子结点结点度数性质推导

解题思路:

本题考查二叉树的结点度数性质。思路是回忆二叉树中三种度数结点数之间的关系式 n0=n2+1n_0 = n_2 + 1,把已知的度为 2 的结点数直接代入即可得到叶子结点数。

详细步骤:

  1. 二叉树中度为 0、1、2 的结点数分别记为 n0n_0、n1n_1、n2n_2,由结点的度数统计可得性质 n0=n2+1n_0 = n_2 + 1。
  2. 题目给出度为 2 的结点数 n2=5n_2 = 5。
  3. 代入得叶子结点数 n0=5+1=6n_0 = 5 + 1 = 6,对应选项 C。

最终答案:

C(6)。

习题 2

简述树和二叉树的主要区别。

树二叉树有序性逻辑结构

解题思路:

本题考查树与二叉树的主要区别。答题时从“孩子个数是否受限”和“子树是否有左右之分”两个角度对比,并特别澄清二叉树不是树的一种特殊情况。

详细步骤:

  1. 树:每个结点可以有任意多个孩子,结点的子树无左右之分,是无序的。
  2. 二叉树:每个结点最多有两个孩子(左、右),且左右子树有严格的次序,不能颠倒。
  3. 关键澄清:二叉树并不是树在孩子数上的特殊情形,而是另一种独立的结构——它额外引入了左右次序这一约束。

最终答案:

树:每个结点可以有任意多个孩子,结点的子树无左右之分(无序)。二叉树:每个结点最多有两个孩子(左、右),且左右子树有严格的次序,不能颠倒。二叉树不是树的特殊情况,而是另一种独立的结构。

发现内容有问题?

告诉我们哪里需要改进。