树形结构是指数据元素之间存在“一对多”（One-to-Many）的树形对应关系而形成的一类数据结构，树形结构是一类非常重要的非线性数据结构。一个树是由多个节点组成，每个节点又具有多个与其关联的子节点。现实中的很多事物的组织结构都可以用树来表示，例如一个公司的组织结构图，网页的DOM树。

树形结构一般都具有以下几个共同的特点：

  1. 只有一个根节点。根节点没有父节点。
  2. 除了根节点，所有的节点都只有一个父节点，不存在一个节点与两个或以上父节点存在关联的情况。
  3. 无环。以任意一个节点作为起始节点，都不存在任何能够返回该起始节点的路径。

    常用术语

  • 节点，树中的数据元素，由数据项和数据元素之间的关联关系组成。
  • 度，度主要表示子树的个数，根据观察位置不同，有不同的定义。
    • 节点的度，表示节点所拥有子树的数量。
    • 树的度，由树中所有节点的度的最大值决定。
  • 子节点，也称为孩子（child），节点所拥有的子树的根节点，称为该节点的子节点。
  • 父节点，如哦一个节点拥有子树，那么该节点就被成为子树根节点的父节点。
  • 兄弟节点，拥有相同父节点的节点成为兄弟节点。
  • 子孙节点，节点所拥有的子树上的节点。
  • 叶节点，没有子节点的节点。
  • 内节点，至少拥有一个子节点的节点。
  • 边，两个节点中间的连接。
  • 路径，从节点到子孙节点过程中所经历的边和节点组成的序列。
  • 层级，从根节点到树中某一个节点所经历路径上的分支数称为这个节点的层级。根节点是0级，根的子节点为1级。
  • 高度，也可以称为深度，指树中的层的数量。
  • 无序树，树中的任意一个节点与其子节点之间的次序没有紧要关联的树。

  • 有序树，树中任意一个节点与其子节点之间有严格排列次序的树。二叉树是有序树，因为其左孩子和右孩子都有确切定义。

    常见树的类型

  • 二叉查找树。

  • 自平衡二叉查找树。
  • B树。
  • 字典树。
  • 空间数据分割树。