树的基本概念

1 树的定义

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

2 树的示意图

  1.         A        ← 根节点
  2.        / \
  3.       B   C      ← A的子节点
  4.      / \   \
  5.     D   E   F    ← 叶节点

3 树的组成部分

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

    树的常见类型

    1 二叉树

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

    2 满二叉树

    每个节点都有0或2个子节点，且所有叶节点在同一层
    1.      A
    2.     / \
    3.    B   C
    4.   / \ / \
    5.  D  E F  G

    3 完全二叉树

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

    树的应用场景

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

树的基本操作示意图

1 遍历方式

  • 前序遍历: 根→左→右
  • 中序遍历: 左→根→右
  • 后序遍历: 左→右→根

    2 查找操作

    1. 查找E节点路径: A → B → E

    3 插入操作

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