树

基本概念

定义

• 一对多的非线性数据结构
• 由n(n>=0)个结点组成的有限集合
• 节点可分为不相交的子集
• 每个子集又是一棵树（或空树）

术语

关系

• 父节点：子节点的上层节点
• 子节点：父节点的下层节点
• 兄弟节点：拥有共同父节点的节点
• 祖先节点：从根节点到该节点路径上的所有节点
• 后代节点：以该节点为根的子树中的所有节点

特殊节点

• 根节点：没有父节点的节点
• 叶子节点：没有子节点的节点
• 内部节点：至少有一个子节点的节点

属性

• 度
  • 节点的度：节点的子树数量
  • 树的度：树中节点的最大度
• 深度
  • 节点的深度：从根节点到该节点的路径长度
  • 树的深度：树中节点的最大深度
• 高度
  • 节点的高度：以该节点为根的子树的深度
  • 树的高度：树中节点的最大高度 树：深度 = 高度
• 森林：由m(m>=0)棵树组成的集合

分类方式

• n叉树：每个节点最多有n个子节点
• 有序/无序树：每个节点的子节点是否有固定顺序
• 类型树：根据节点类型划分，如搜索树、线段树、AVL树、红黑树等

性质

变量定义

• $m$叉树
• 高度$h$
• 节点总数$n$，各节点度数$n_i$
• 边总数$e$

公式

• $n_i \leq m^i$
• $n = \sum_{i=0}^{k} n_i \leq \frac{m^{h}-1}{m-1}$
• $e = n - 1$

存储

一般表示法有

• 双亲表示法
• 孩子表示法
• 孩子兄弟表示法

双亲表示法

定义

每个结点存储一个指向其父结点的指针（或索引）

特点

访问父结点方便，访问子结点不方便

结构体定义

struct PTNode {
    char data; // 结点数据
    struct PTNode* parent; // 父结点指针
};

孩子表示法

定义

每个结点存储所有子结点的链表（或数组）

特点

访问父结点不方便，访问子结点方便

结构体定义

顺序存储

struct CTNode {
    char data; // 结点数据
    vector<CTNode*> children;// 子结点在数组中的位置
};

链式存储

struct CTNode {
    char data; // 结点数据
    CTNode* firstChild; // 子节点链表头指针
};

孩子兄弟表示法

定义

每个结点存储

• 一个指向第一个子结点的指针
• 一个指向下一个兄弟结点的指针

特点

访问父结点不方便，访问子结点和兄弟结点方便

结构体定义

struct CSNode {
    char data; // 结点数据
    struct CSNode* firstChild; // 第一个子结点指针
    struct CSNode* nextSibling; // 下一个兄弟结点指针
};

全tm连上表示法（一般不用）

定义

每个结点存储

• 一个指向父结点的指针
• 一个指向第一个子结点的指针
• 一个指向下一个兄弟结点的指针

特点

访问父结点、子结点和兄弟结点都方便，但存储空间大

结构体定义

struct FullNode {
    char data; // 结点数据
    struct FullNode* parent; // 父结点指针
    struct FullNode* firstChild; // 第一个子结点指针
    struct FullNode* nextSibling; // 下一个兄弟结点指针
};