一、树的基本概念

  • 1.1 树的定义

    树是一种非线性的数据结构,由n(n≥0)个有限节点组成一个具有层次关系的集合。

  • 1.2 树的示意图

    1. A 根节点
    2. / \
    3. B C A的子节点
    4. / \ \
    5. D E F 叶节点
  • 1.3 树的组成部分

    • 根节点(Root): 树的最顶层节点(如A)
      • 父节点/子节点: B是A的子节点,A是B的父节点
      • 叶节点(Leaf): 没有子节点的节点(如D,E,F)
      • 边(Edge): 连接两个节点的线
      • 深度: 从根到该节点的边数(A深度为0,B为1,D为2)
      • 高度: 从该节点到最深叶节点的边数

二、树的常见类型

  • 2.1 二叉树

    • 每个节点最多有两个子节点(左子节点和右子节点)
      1. A
      2. / \
      3. B C
      4. / \ \
      5. D E F
  • 满二叉树

    • 每个节点都有0或2个子节点,且所有叶节点在同一层
      1. A
      2. / \
      3. B C
      4. / \ / \
      5. D E F G
  • 2.3 完全二叉树

    • 除最后一层外,其他层都填满,且最后一层节点靠左排列
      1. A
      2. / \
      3. B C
      4. / \ /
      5. D E F

三、树的应用场景

  • 文件系统: 文件夹和文件的层级结构
  • 组织结构图: 公司部门层级关系
  • 家谱图: 家族成员关系
  • HTML DOM树: 网页元素嵌套关系
  • 决策树: 机器学习中的分类模型

四、树的基本操作示意图

  • 4.1 遍历方式
    • 前序遍历: 根→左→右
    • 中序遍历: 左→根→右
    • 后序遍历: 左→右→根
  • 4.2 查找操作

    1. 查找E节点路径: A B E
  • 4.3 插入操作

    1. C节点下插入G:
    2. A
    3. / \
    4. B C
    5. / \ \
    6. D E G

逻辑结构 第四章 ——树 - 图1 第四章 ——树 - 图2 树的几要素: 第四章 ——树 - 图3 二叉树 第四章 ——树 - 图4 满二叉树 第四章 ——树 - 图5 完全二叉树 第四章 ——树 - 图6 满二叉树与完全二叉树的关系: 第四章 ——树 - 图7 第四章 ——树 - 图8 使用总边数一致推导:

  1. N0 = N2 + 1

第四章 ——树 - 图9

题目

一棵节点已知的二叉树,求至多有多少个节点有2个子节点公式:

  • 2 * n2 + 1 + n1 = 10

n2:度数为2的节点,n1度数为1的节点,n0度数为0的节点 第四章 ——树 - 图10