第50章树

树(Tree)是一种重要的非线性数据结构，它由 $n(n ≥0)$ 个节点组成，节点之间通过边连接，呈现出层次化的分支结构。树结构在计算机科学中应用广泛，如文件系统的目录结构、数据库索引、语法解析树等。

50.1 树的基本定义与术语

50.1.1 树的定义

树是由 $n(n ≥0)$ 个节点组成的有限集合：当 $n=0$ 时，称为空树。当 $n>0$ 时，有且仅有一个特定的节点称为根节点(Root)，其余节点可分为 $m(m ≥0)$ 个互不相交的有限集合，每个集合本身又是一棵树，称为根节点的子树(Subtree)。

树的定义具有递归性：一棵树由根节点和若干棵子树构成，而每棵子树又符合树的定义。

50.1.2 基本术语

节点(Node)：树的基本组成单位，包含数据元素及指向子树的指针(或引用)。
根节点(Root)：树中没有前驱的节点(即最顶层的节点)。
叶子节点(LeafNode)：没有子树的节点(即度为0的节点)。
父节点(ParentNode)：若节点A是节点B的直接前驱(即B是A的子树的根)，则A是 B的父节点。
子节点(Child Node)：若节点B是节点A的子树的根，则B是A的子节点。
兄弟节点(Sibling Node)：具有相同父节点的节点互称为兄弟节点。
度(Degree)：节点拥有的子树数量称为该节点的度；树的度是树中有度的最大值。
层次(Level)：根节点的层次为1，其余节点的层次为其父节点的层次加1。
深度(Depth)：节点的深度是从根节点到该节点的路径上的节点数；树的深度是树中所有节点深度的最大值(又称高度)。
路径(Path)：从节点到节点B的路径是指从A到B的一系列节点，其中每个节点都是前一个节点的子节点；路径长度是路径上的边数。

示例树形结构文字描述：

A(根节点,Level=1,Depth=1)
├─ B
└─ C
   ├─ D ├─ E └─ F

B和C是兄弟节点；D、E、F是叶子节点，深度为3。

50.1.3 树的特性

树中没有回路不存在从一个节点出发又回到自身的路径。
树中任意两个节点之间有且仅有一条路径。
若树有n个节点，则有n-1条边(根节点到各子节点的边数总和)。
删除树的根节点后，会得到若干棵子树；删除任意非根节点，会导致该节点所在的子树与原树分离。

50.2 树的表示与构造

50.2.1 双亲表示法

双亲表示法通过数组存储树的节点，每个节点包含数据和其父节点在数组中的索引，适用于频繁查找父节点的场景。

#define MAX_TREE_SIZE 100
//节点结构
typedef struct{
    int data;//节点数据
    int parent;//父节点索引(-1表示无父节点)
} PTNode;
//树结构
typedef struct{
    PTNode nodes [MAX_TREE_SIZE];
    int root;//根节点索引
    int n;//节点总数
} PTree;

//构造一棵简单的树
void createPTree (PTree &tree) {
    tree.n=5;//5个节点
    //节点0:根节点,数据10,无父节点
    tree.nodes[0].data=10;
    tree.nodes[0].parent= -1;
    tree.root=0;
    //节点1:数据20,父节点0
    tree.nodes[1].data= 20;
    tree.nodes[1].parent= 0;
    //节点2:数据30,父节点0
    tree.nodes[2].data = 30;
    tree.nodes[2].parent= 0;
    //节点3:数据40,父节点1
    tree.nodes[3].data = 40;
    tree.nodes[3].parent=1;
    //节点4:数据50,父节点2
    tree.nodes[4].data = 50;
    tree.nodes[4].parent=2;
}

50.2.2 孩子表示法

孩子表示法结合数组和链表，每个节点的所有子节点通过链表连接，数组中存储节点数据及对应子链表的头指针，适用于频繁查找子节点的场景。

//孩子节点结构(链表节点)
typedef struct ChildNode {
    int childIndex;//子节点在数组中的索引
    struct ChildNode *next; //下一个子节点
} ChildNode;

//数组中的节点结构
typedef struct{
    int data;//节点数据
    ChildNode *firstChild;//第一个子节点的指针
} CTNode;

//树结构
typedef struct {
    CTNode nodes [MAX_TREE_SIZE];
    int root;//根节点索引
    int n;//节点总数
} CTree;

//为节点添加子节点
void addChild (CTree &tree, int parentIndex, int childIndex) {
    ChildNode *newNode = (ChildNode*) malloc (sizeof (ChildNode));
    newNode->childIndex = childIndex;
    newNode->next = tree.nodes[parentIndex].firstChild;
    tree.nodes[parentIndex].firstChild = newNode; //头插法
}

//构造树
void createCTree (CTree &tree) {
    tree.n = 5;
    //初始化节点数据
    tree.nodes[0].data = 10;
    tree.nodes[0].firstChild = NULL;
    tree.nodes[1].data = 20;
    tree.nodes[1].firstChild = NULL;
    tree.nodes[2].data = 30;
    tree.nodes[2].firstChild = NULL;
    tree.nodes[3].data = 40;
    tree.nodes[3].firstChild = NULL;
    tree.nodes[4].data = 50;
    tree.nodes[4].firstChild = NULL;
    tree.root=0;
    //添加子节点:0的子节点为1、2
    addChild(tree,0, 1);
    addChild(tree, 0, 2);
    //添加子节点:1的子节点为3
    addChild(tree, 1, 3);
    //添加子节点:2的子节点为4
    addChild(tree,2, 4);
}

50.2.3 孩子-兄弟表示法(二叉树表示法)

孩子-兄弟表示法通过二叉链表存储树，每个节点包含数据、第一个子节点的指针和右兄弟节点的指针，可将任意树转换为二叉树表示，是最常用的树表示方法之一。

//节点结构
typedef struct CSNode {
    int data;//节点数据
    struct CSNode *firstChild; //第一个子节点
    struct CSNode *nextSibling;//右兄弟节点
} CSNode,*CSTree;

//创建节点
CSNode* createNode (int data) {
    CSNode *node = (CSNode*) malloc (sizeof (CSNode));
    node->data = data;
    node->firstChild = NULL;
    node->nextSibling = NULL;
    return node;
}

//构造树
CSTree createCSTree(){
    CSNode *root = createNode (10);
    CSNode *n1 = createNode (20);
    CSNode *n2 = createNode (30);
    CSNode *n3 = createNode (40);
    CSNode *n4 = createNode (50);
    //建立关系:root的第一个子节点是n1,n1的右兄弟是n2
    root->firstChild = n1;
    n1->nextSibling = n2;
    //n1的第一个子节点是n3;n2的第一个子节点是n4
    n1->firstChild = n3;
    n2->firstChild =n4;
    return root;
}

50.3 树的遍历

树的遍历是指按某种规则访问树中的所有节点，且每个节点仅被访问一次。由于树是层次化结构，常用的遍历方式有先根遍历、后根遍历和层次遍历。

50.3.1 先根遍历(Preorder Traversal)

先根遍历的规则是:先访问根节点，再依次对根节点的每棵子树进行先根遍历(递归定义)。遍历步骤:

访问当前根节点。
若当前节点有子节点，按从左到右的顺序，对每个子节点对应的子树执行先根遍历。

//先根遍历
void preorderTraversal (CSTree root) {
    if (root == NULL) return;
    printf("%d ", root->data); //访问根节点
    //遍历第一个子节点(左子树)
    preorderTraversal (root->firstChild);
    //遍历右兄弟节点(其他子树)
    preorderTraversal (root->nextSibling);
}

示例树结构：10的子节点20、30；20子节点40；30子节点50 先根遍历输出：10 20 40 30 50

50.3.2 后根遍历(Postorder Traversal)

后根遍历的规则是:先依次对根节点的每棵子树进行后根遍历，再访问根节点(递归定义)。遍历步骤:

若当前节点有子节点，按从左到右的顺序，对每个子节点对应的子树执行后根遍历。
访问当前根节点。

//后根遍历
void postorderTraversal (CSTree root) {
    if (root == NULL) return;
    //先遍历所有子树
    postorderTraversal (root->firstChild);
    //再访问当前节点
    printf("%d ", root->data);
    //遍历右兄弟节点
    postorderTraversal (root->nextSibling);
}

同上示例树，后根遍历结果：40 20 50 30 10

50.3.3 层次遍历(Levelorder Traversal)

层次遍历(又称广度优先遍历)的规则是:按节点的层次顺序访问，先访问第一层(根节点)，再访问第二层(根节点的子节点)，依次类推，同一层次的节点按从左到右的顺序访问。遍历步骤:

使用队列存储待访问的节点，初始时将根节点入队。
若队列非空，出队一个节点并访问。
将该节点的所有子节点按从左到右的顺序入队。
重复步骤2、3，直至队列为空。

#include <queue>
using namespace std;
//层次遍历
void levelorderTraversal (CSTree root) {
    if (root == NULL) return;
    queue<CSNode*> q;
    q.push (root);//根节点入队
    while (!q.empty()){
        CSNode *current = q.front();
        q.pop ();
        printf("%d ",current->data);
        //子节点入队(按从左到右顺序)
        CSNode *child = current->firstChild;
        while (child!= NULL){
            q.push (child);
            child = child->nextSibling; //下一个兄弟节点
        }
    }
}

同上示例树，层次遍历结果：10 20 30 40 50

50.4 森林的概念与遍历

森林是m(m ≥0)棵互不相交的树的集合。森林与树可以相互转换:给森林中的所有树添加一个共同的根节点，森林就成为一棵树；删除树的根节点，树就成为森林(根节点的子树构成森林)。

50.4.1 森林的遍历

森林的遍历方式与树类似，主要有:

先序遍历:依次对森林中的每棵树进行先根遍历。
中序遍历:依次对森林中的每棵树进行后根遍历。

示例:若森林由树A和树B组成，先序遍历为"先根遍历A→先根遍历B"，中序遍历为 "后根遍历A→后根遍历B"。

50.5 树的应用场景

文件系统:操作系统的文件目录结构是典型的树结构(根目录为根节点，文件和文件夹为子节点)。
数据库索引:B树、B+树等索引结构基于树的层次特性，用于高效查询数据。
语法分析:编译原理中，语法树用于表示程序的语法结构。
决策树:机器学习中，决策树通过层次化的判断节点实现分类或回归。
组织结构:企业或机构的层级结构(如部门、员工)可通过树表示。

50.6 注意事项

递归实现的理解:树的定义和遍历算法具有递归性，理解递归调用的过程是掌握树操作的关键。
节点存储的选择:根据实际需求选择表示方法如双亲表示法适合查父，孩子-兄弟表示法适合通用操作。
空树处理:在遍历和构造树时，需先判断根节点是否为NULL，避免空指错误。
内存管理:使用动态分配(malloc、new)创建节点时，需在树销毁时释放内存，避免内存泄漏。

50.1 树的基本定义与术语​

50.1.1 树的定义​

50.1.2 基本术语​

50.1.3 树的特性​

50.2 树的表示与构造​

50.2.1 双亲表示法​

50.2.2 孩子表示法​

50.2.3 孩子-兄弟表示法(二叉树表示法)​

50.3 树的遍历​

50.3.1 先根遍历(Preorder Traversal)​

50.3.2 后根遍历(Postorder Traversal)​

50.3.3 层次遍历(Levelorder Traversal)​

50.4 森林的概念与遍历​

50.4.1 森林的遍历​

50.5 树的应用场景​

50.6 注意事项​