数据结构05：树的定义与双亲、孩子表示法[更新中]

图源：BING AI 

考研笔记整理约2.2w字，小白友好、代码可跑的笔记整理，请小伙伴放心食用~👻👻

第1版：查资料、写BUG、画导图、画配图ing~

参考用书：王道考研《2024年 数据结构考研复习指导》

参考用书配套视频：5.1.1 树的定义和基本术语_哔哩哔哩_bilibili

特别感谢： Chat GPT老师[部分名词解释、修改BUG]、BING AI[配图]、文心一言[配图]~

目录

目录

目录

思维导图

树

树的概念

树的基本术语

树的基本性质

树的存储结构

双亲表示法

孩子表示法

孩子兄弟表示法

二叉树

二叉树的概念

定义

特殊的二叉树

二叉树的性质

二叉树的存储结构

二叉树的遍历

先序、中序、后序遍历的定义与手动推算

先序、中序、后序遍历的核心代码

结语

备注：模板篇幅限制就只能写这么长了，线索二叉树及树的应用见下篇~

思维导图

树

树的概念

树的定义：树是n（n≥0）个结点的有限集。当n=0时，称为空树。在任意一棵非空树应满足：

• 有且仅有一个特定的称为根的结点。
• 当n＞1时，其余结点可分为m(m>0)个互不相交的有限集T1，T2，...，Tm，其中每个集合本身又是一棵树，并且称为根的子树。 //因此，树是递归的数据结构

树的基本术语

图：树的图形表示+术语注释 

 （1）结点、度

• 结点：一种数据结构，包含数据和对一个或多个其他节点的引用（例如：指针）。
  • 根结点：树的根节点没有前驱，除根结点以外的所有结点有且仅有1个前驱；
  • 分支结点：除根节点外，度＞0的结点称为分支结点；
  • 分支结点：除根节点外，度 = 0的结点称为分支结点；
• 结点关系：
  • 祖先结点：从根结点到指定结点的路径上的所有结点，例如结点A、B、E均为结点K的祖先结点；
  • 子孙结点：从指定结点到叶子点的路径上的所有结点，例如结点K、L、F均为结点B的子孙结点；
  • 双亲结点：祖先结点中最接近指定结点的结点，例如结点E是结点K、L的双亲结点。
  • 孩子结点：子孙结点中最接近指定结点的结点，例如结点E、F是结点B的孩子结点。
  • 兄弟结点：具有相同父节点的两个结点，例如结点K与结点L是兄弟结点。
• 度数：
  • 结点的度：树中一个结点的孩子个数称为度数。
  • 树的度：树中结点的最大度数称为数的度。例如图中结点的度数为3，因此这棵树的结点就是3。

（2）层次、深度、高度：

• 层次：一个节点的层级是从根节点到该节点的边数。
• 高度：树中结点的最大层数。

（3）路径：

• 路径：两个结点之间的路径是由这两个结点之间所经过的结点序列构成的；
• 结点的路径长度：两个指定结点路径上经过的边的个数。
• 树的路径长度：树根到每个结点的路径长度的总和。

（4）有序、无序：

• 有序树：是节点按特定顺序排列的树，结点之间不能互换，例如二叉搜索树。
• 无序树：是指节点未按任何特定顺序排列的树。

树的基本性质

（1）结点与结点、结点与边

• n个结点的树 有 n-1条边；// 根节点无前驱，因此无指向根结点的边~
• 树中的结点数 - 1 =所有结点的度数； // 结点的度数代表孩子结点的个数，根节点为特殊的无前驱的结点，因此需要 -1；

（2）结点与度

• 度为m的树，在第 i 层上结点数 ≤ m^(i-1)； // 按照结点的度均为m的情况考虑，第1层最多有m^(1-1)=1个结点，第2层最多有m^(2-1)=m个结点...递推可求~

（3）结点与高

• 高度为h的m叉树 结点数 n ≤ （m^h -1）/（m-1）； // 等比公式可求，Sn=首项（1-公比的n次方）/（1-公比）

嗯，这个我们以满3叉树(m=3)举栗：

树的存储结构

双亲表示法

描述：(1)采用一组连续空间来存储每个结点(下图表中data位)，(2)同时在每个结点中增加一个伪指针，指示其双亲结点在数组中的位置(下图表中parent位)，其中根节点的parent=-1。

特点：

• 简洁直观：相比其它存储方式易于理解与实现。
• 存储结构：顺序存储和链式存储均可实现，其中顺序存储较为常见。
• 存取效率：可以很快得到每个结点的双亲结点，但求孩子结点时需要遍历整个结构；不过这并不是硬伤，可以根据需要在结构体中增加一个用于存放孩子结点的伪指针，这样做会牺牲一些存储空间。    // 所以这里叫做顺序存储法是不是比双亲存储法更合适一些~~
• 是否有序：双亲表示法不适合表示有序树，更适合表示无序树，因为无序树中节点的子节点没有明确的顺序关系。

图示：源于《王道》教材图5.14 树的双亲表示法

双亲表示法 核心代码：

#define MAX_TREE_SIZE 100   //树中可以存储的结点数

typedef struct{     //树中结点的结构，该结构有两个字段
    ElemType data;   //该字段存储结点的数据元素
    int parent;      //该字段存储结点的双亲指针（伪指针）
}PTNode;

typedef struct{     //树的结构，该结构有两个字段
    PTNode nodes[MAX_TREE_SIZE];   //结构数组，用于存储树中的结点
    int n;                         //树中的结点数
}PTree;

双亲表示法 案例：

要求：1 树的构建；2 树的遍历；3 按值查找某节点，并寻找其父结点与子节点；4 按位查找某节点，并输出其祖先结点与子孙结点~

思路：

LocateElem封装按值查找函数，并寻找双亲与孩子结点~

1. 用参数i记录并遍历本结点的位序；

2. 找到目标结点后，输出当前结点的信息，将父结点的信息赋值给j并输出；

3. 通过循环寻找并输出孩子结点的信息，同时记录子结点的数量；如果子结点的数量为0，则输出没有子结点的提示信息；[这一步时间开销会很高，仅寻找相邻结点]；

4. 如果遍历到末尾没有找到结点，则输出没有该结点的提示信息。

get封装按位查找函数，并寻找祖先与子孙结点~

1. 判断树中是为空，如果是，返回错误；如果否，继续执行；
2. 判断值是否越界，如果是，返回错误；如果否，继续执行；
3. 输出目标结点的data与parent；

4. 通过递归寻找并输出祖先/子孙结点的信息，同时记录子结点的数量；如果子结点的数量为0，则输出没有子结点的提示信息；如果父节点已为根结点，则反馈到第2步；[这一步时间开销会很高，可寻找所有祖先/子孙结点]； 

#include <iostream>
#define MAX_TREE_SIZE 100  // 树的最大节点数量

typedef struct {
    char data;  // 节点数据
    int parent;  // 双亲节点的索引
} PTNode;

typedef struct {
    PTNode nodes[MAX_TREE_SIZE];  // 节点数组
    int n;  // 当前节点数目
} PTree;

// 初始化树对象
void InitTree(PTree* tree) {
    for (int i = 0; i < MAX_TREE_SIZE; i++) {
        tree->nodes[i].data = 0;  // 将节点数据初始化为0
        tree->nodes[i].parent = -1;  // 将节点的双亲索引初始化为-1
    }
    tree->n = 0;  // 初始化节点数量为0
}

// 添加节点到树中
void addNode(PTree* tree, char data, int parentIndex) {
    if (tree->n >= MAX_TREE_SIZE) {  // 如果树已满，不能再添加数据
        std::cout << "错误：树已满，不能再添加数据。\n";
        return;
    }

    PTNode newNode;
    newNode.data = data;  // 设置新节点的数据

    if (parentIndex < 0) {
        newNode.parent = -1;  // 如果双亲索引小于0，则表示没有双亲节点
    }
    else {
        newNode.parent = parentIndex;  // 否则，将双亲索引设置为给定的索引值
    }

    tree->nodes[tree->n] = newNode;  // 将新节点添加到节点数组中
    tree->n++;  // 更新节点数量
}

// 按值查找节点
void LocateElem(const PTree* tree, char data) {
    int i, j;
    int childCount = 0;
    int firstChildPos = -1;

    for (i = 0, j = -1; i < tree->n; i++) {
        if (tree->nodes[i].data == data) {  // 如果找到匹配的节点
            std::cout << "找到结点 " << data << std::endl;
            std::cout << "当前结点信息：" << "位置: " << i << ", 数据: " << tree->nodes[i].data << ", 双亲位置: " << tree->nodes[i].parent << std::endl;

            j = tree->nodes[i].parent;
            if (j != -1) {
                std::cout << "父节点信息：" << "位置: " << j << ", 数据: " << tree->nodes[j].data << ", 双亲位置: " << tree->nodes[j].parent << std::endl;
            }

            for (int k = 0; k < tree->n; k++) {
                if (tree->nodes[k].parent == i) {
                    if (childCount == 0) {
                        firstChildPos = k;
                    }
                    std::cout << "子节点信息：" << "位置: " << k << ", 数据: " << tree->nodes[k].data << ", 双亲位置: " << tree->nodes[k].parent << std::endl;
                    childCount++;
                }
            }

            if (childCount == 0) {
                std::cout << "该结点没有子节点" << std::endl;
            }
            else {
                std::cout << "子节点数量: " << childCount << std::endl;
                //std::cout << "第一个子节点信息：" << "位置: " << firstChildPos << ", 数据: " << tree->nodes[firstChildPos].data << ", 双亲位置: " << tree->nodes[firstChildPos].parent << std::endl;
            }

            return;
        }
    }

    std::cout << "未找到结点 " << data << std::endl;
}

// 获取节点的子孙节点
void GetOffspring(const PTree& tree, int index) {
    if (index < 0 || index >= tree.n) {  // 检查索引是否越界
        std::cout << "错误：索引越界。\n";
        return;
    }

    const PTNode& currentNode = tree.nodes[index];

    std::cout << "结点位置: " << index << ", 数据: " << currentNode.data << ", 父节点位置: " << currentNode.parent << std::endl;

    int childCount = 0;

    for (int i = 0; i < tree.n; i++) {
        if (tree.nodes[i].parent == index) {  // 如果节点的双亲索引与给定索引相等，则表示是其子节点
            childCount++;
            GetOffspring(tree, i);  // 递归调用以获取孩子节点的子节点
        }
    }

    if (childCount == 0) {
        std::cout << "该结点没有孩子结点。\n";
    }
}

// 获取节点的祖先节点
void GetAncestors(const PTree& tree, int index) {
    if (index < 0 || index >= tree.n) {  // 检查索引是否越界
        std::cout << "错误：索引越界。\n";
        return;
    }

    const PTNode& currentNode = tree.nodes[index];

    std::cout << "结点位置: " << index << ", 数据: " << currentNode.data << ", 父节点位置: " << currentNode.parent << std::endl;

    int parentIndex = currentNode.parent;
    if (parentIndex >= 0) {
        GetAncestors(tree, parentIndex);  // 递归调用以获取祖先节点的祖先节点
    }
}

int main() {
    PTree newtree;
    // 初始化树对象
    InitTree(&newtree);

    // 增加节点
    char data;
    int parentIndex;
    while (std::cout << "输入结点: " && std::cin >> data && data != '\\') {
        std::cout << "输入结点的双亲位置: ";
        std::cin >> parentIndex;
        addNode(&newtree, data, parentIndex);
    }

    std::cout << std::endl;

    // 输出结点
    for (int i = 0; i < newtree.n; i++) {
        std::cout << "结点位置: " << i << ", 数据: " << newtree.nodes[i].data << ", 父节点位置: " << newtree.nodes[i].parent << std::endl;
    }

    std::cout << std::endl;

    // 输出按值查找结点信息
    char target1;
    std::cout << "请输入要按值查找的结点: ";
    std::cin >> target1;
    LocateElem(&newtree, target1);

    std::cout << std::endl;

    // 输出子孙结点
    int targetIndex1;
    std::cout << "寻找该位序的子孙结点: ";
    std::cin >> targetIndex1;
    GetOffspring(newtree, targetIndex1);

    std::cout << std::endl;

    // 输出祖先结点
    int targetIndex2;
    std::cout << "寻找该位序的祖先结点: ";
    std::cin >> targetIndex2;
    GetAncestors(newtree, targetIndex2);

    return 0;
}

运行的效果如下图所示：

孩子表示法

描述：将每个结点都用单链表链接起来的线性结构，此时n个结点就有n个孩子链表（叶节点的孩子链表为空链表）。

特点：

• 存储结构：顺序存储法通常由顺序表和链表共同构成。在这种存储方式中，树的整体结构使用顺序表来表示，而每个结点则使用链表来表示其孩子结点。
• 存取效率：可以很快得到每个结点的孩子结点，方便地动态添加孩子节点，但求双亲结点时需要遍历指针域所指向的n个孩子链表。
• 是否有序：适用于任意树的存储，包括有序树。由于每个节点的孩子节点都以单链表的形式链接，因此可以灵活地表示任意数量的子节点，并且可以按照节点在链表中的顺序确定子节点的顺序。但是无法区分左右结点。

图示：源于《王道》教材图5.15 树的孩子表示法

孩子表示法 案例：

要求：1 树的构建；2 树的遍历~

备注：经过了多次的失败打击，考虑到时间有限，最后找gpt老师帮我重构逻辑写了一份代码~这段代码我也有很多不懂的地方，尤其是不懂<vector>这个头文件，因此增加了很啰嗦的注释~😢😢

思路：

1. 构建树的核心思想是层次遍历，需要用到辅助队列，关于队列的内容及特性可见👉数据结构03：栈、队列和数组_梅头脑-CSDN博客~
2. 代码中，我们使用向量 std::vector<CTNode*> nodeQueue 来模拟队列的行为。向量和队列的区别在于：

   1. 数据结构类型：

      • 向量是一种动态数组，可以在末尾快速添加和删除元素，并支持随机访问元素。
      • 队列是一种先进先出（FIFO）的数据结构，只能在队尾添加元素，在队首移除元素。

   2. 添加和删除元素：

      • 向量使用 push_back 方法在末尾添加元素，并使用 erase 方法删除指定位置的元素。
      • 队列使用 push 方法在队尾添加元素，并使用 pop 方法移除队首元素。

   3. 访问元素：

      • 向量可以通过索引直接访问元素，例如 vector[index]。
      • 队列只能访问队首元素，使用 front 方法。

3. 需要注意的是，向量和队列在底层实现和性能上可能存在差异。如果需要严格的队列行为，可以使用标准库中的 std::queue 类，它是专门用于队列操作的数据结构。

4. 构建树的流程图如下~

代码： 

#include <iostream>    //C++标准库中的头文件，提供了输入输出流的功能。在代码中使用std::cout和std::cin进行输出和输入操作。
#include <vector>    //这是C++标准库中的头文件，它包含了std::vector模板类，提供了动态数组的功能。在这段代码中，std::vector<CTNode*>被用来存储和管理树的子结点和结点队列。

// 定义树的结点结构
struct CTNode {
    char data;      // 用于存储结点的数据
    std::vector<CTNode*> children;  // 一个std::vector<CTNode*>类型的容器，用于存储子结点的指针
};

// 定义树的结构
struct CTree {
    CTNode* root;  // 根节点指针
};

// 创建新的树结点
CTNode* createNode(char data) {     //接受一个char类型的参数data，用于传输树结点的数据
    CTNode* newNode = new CTNode();     //创建新的树结点newnode
    newNode->data = data;       //将data的数据赋值给newnode
    return newNode;     //返回newnode的结点指针
}

// 添加孩子节点
void addChild(CTNode* parent, CTNode* child) {      //接受两个参数：parent代表父结点的指针，child代表要添加的子结点的指针。
    parent->children.push_back(child);     //调用 std::vector 类的 push_back() 方法，将 child 添加到 parent->children 的末尾，从而实现了添加子节点的操作。
}

// 初始化树
CTree* initTree() {
    CTree* tree = new CTree();     //创建新的树tree
    tree->root = nullptr;     //树的根节点指针设为空
    return tree;     //返回树的指针
}

// 构建树
void buildTree(CTree* tree) {     //接受树的结构体CTree*的指针tree，用于增加树结点的数据
    //用户键入树的结点数据data
    char data;
    std::cout << "输入根节点数据: ";
    std::cin >> data;

    // 创建根节点
    CTNode* root = createNode(data);    //创建根结点，并将用户输入的data赋值到根节点
    tree->root = root;      //根节点的指针赋值给tree的root成员变量，将根节点连接到树中

    std::vector<CTNode*> nodeQueue;  // 创建辅助队列nodeQueue，其数据类型为树的结点类型CTNode，用于辅助构建树
    nodeQueue.push_back(root);      //调用 std::vector 类的 push_back() 方法，将根节点的指针root添加到结点队列nodeQueue，作为开始构建树的起点

    while (!nodeQueue.empty()) {    //当辅助队列nodeQueue的结点不为空时，执行以下循环
        CTNode* currentNode = nodeQueue.front();    //从辅助队列nodeQueue中获取队首元素的值。nodeQueue.front()获取结点队列的第一个结点的指针，并将其赋值给变量currentNode
        nodeQueue.erase(nodeQueue.begin());     //辅助队列nodeQueue队首元素出队。这行代码使用erase()函数从结点队列中移除第一个结点。begin()函数返回队列的起始迭代器，它指向队列的第一个元素

        //用户键入树的当前结点data赋值到辅助队列的结点currentNode，并键入孩子结点数量childCount
        int childCount;
        std::cout << "输入节点 " << currentNode->data << " 的子节点数量: ";
        std::cin >> childCount;

        //当用户键入的子结点个数＜孩子结点数量childCount时，执行以下循环
        for (int i = 0; i < childCount; i++) {
            //用户键入树的孩子结点数据childData
            char childData;
            std::cout << "输入子节点 " << i + 1 << " 的数据: ";
            std::cin >> childData;

            // 创建孩子结点
            CTNode* childNode = createNode(childData);

            // 将孩子结点childNode的值添加到当前结点currentNode的末尾，形成当前结点的孩子链表
            addChild(currentNode, childNode);

            // 将孩子结点childNode加入辅助队列nodeQueue，在下一轮循环中作为父结点构建其孩子链表
            nodeQueue.push_back(childNode);
        }
    }
}

// 输出树的结构
void printTree(const CTree* tree) {
    // 若树为空，返回main函数
    if (tree->root == nullptr) {
        std::cout << "树为空。\n";
        return;
    }

    std::cout << "树的结构:\n";     // 输出文字：“树的结构”

    std::vector<const CTNode*> nodeQueue;   // 在树的结构输出中进行层次遍历。具体为，创建了一个空的向量 nodeQueue作为辅助队列，用于存储树的常量指针CTNode*。
    nodeQueue.push_back(tree->root);    //将根结点root添加到辅助队列nodeQueue的末尾

    while (!nodeQueue.empty()) {    //当辅助队列nodeQueue的结点不为空时，执行以下循环
        const CTNode* currentNode = nodeQueue.front();    //读取辅助队列nodeQueue的队首元素
        nodeQueue.erase(nodeQueue.begin());    //辅助队列nodeQueue的队首元素出队

        std::cout << "结点数据: " << currentNode->data;    // 输出文字：“结点数据”

        if (!currentNode->children.empty()) {    // 当前结点currentNode的孩子结点children不为空时，执行以下循环
            std::cout << "，子节点数据: ";    // 输出文字：“子节点数据”
            for (const CTNode* child : currentNode->children) {    //读取当前结点currentNode的队首孩子结点children
                std::cout << child->data << " ";    // 输出孩子结点的数据
                nodeQueue.push_back(child);    // 队首孩子结点出队
            }
        }

        std::cout << "\n";
    }
}

int main() {
    CTree* tree = initTree();  // 初始化树

    buildTree(tree);  // 构建树

    std::cout << "\n";
    printTree(tree);  // 输出树的结构

    delete tree;  // 释放内存

    return 0;
}

 运行的效果如下图所示：

孩子兄弟表示法

描述：孩子兄弟表示法又称为二叉树表示法，它使用二叉链表作为树的存储结构。在孩子兄弟表示法中，每个节点包括三个部分的内容：结点值、指向该结点的第一个孩子结点的指针，以及指向该结点的下一个兄弟结点的指针（通过这个指针可以找到该结点的所有兄弟结点）。 //因此在存储时会转换为二叉树~

树与二叉树的转换：每个结点左指针指向它的第一个孩子，右指针指向它在树中相邻的右兄弟，这个规则又称“左孩子右兄弟”。由于根结点没有右兄弟，所以对应的二叉树没有右子树。

特点：

• 存储结构：顺序存储法通常由链表构成。
• 存取效率：这种存储表示法比较灵活，其最大的优点是可以方便地实现树转换为二叉树的操作，易于查找结点的孩子等，但缺点是从当前结点查找其双亲结点比较麻烦。若为每个结点增设一个parent域指向其父结点，则查找结点的父结点也很方便。
• 是否有序：适用于任意树的存储，包括有序树。

图示：源于《王道》教材图5.15 树的孩子兄弟表示法

孩子兄弟表示法 案例：

要求：按照上图，1 构建树；2 递归算法输出树转二叉树的结点与深度；3 递归算法输出原树的结点与深度~

思路：

1. 构建树的核心思想是队列，与孩子表示法的构建思路很类似，区别在于这一步：addChild(currentNode, childNode); 孩子兄弟法不能将孩子结点直接挂在原结点的后面，而是需要根据左孩子右兄弟的原则转换为二叉树存储~思维导图如下，与之前孩子表示法的区别已经涂蓝了~
2. 输出和求树高用了递归的方式，效率偏低，但是代码会简洁一些~

代码：

#include <iostream>    //C++标准库中的头文件，提供了输入输出流的功能。在代码中使用std::cout和std::cin进行输出和输入操作。
#include <vector>    //这是C++标准库中的头文件，它包含了std::vector模板类，提供了动态数组的功能。在这段代码中，std::vector<CTNode*>被用来存储和管理树的子节点和节点队列。

// 定义树的结点结构
struct CSNode {
    char data;      // 用于存储结点的数据
    std::vector<CSNode*> firstchild;    // 孩子指针
    std::vector<CSNode*> nextsibling;    // 兄弟指针
};

// 定义树的结构
struct CSTree {
    CSNode* root;  // 根节点指针
};

// 创建新的树结点
CSNode* createNode(char data) {     //接受一个char类型的参数data，用于传输树结点的数据
    CSNode* newNode = new CSNode();     //创建新的树结点newnode
    newNode->data = data;       //将data的数据赋值给newnode
    return newNode;     //返回newnode的结点指针
}

// 添加孩子节点
void addChild(CSNode* parent, CSNode* child) {      //接受两个参数：parent代表父节点的指针，child代表孩子节点的指针。
    parent->firstchild.push_back(child);     //调用 std::vector 类的 push_back() 方法，将 child 添加到 parent->firstchild 的末尾。
}

// 添加兄弟节点
void addSibling(CSNode* parent, CSNode* sibling) {      //接受两个参数：parent代表父节点的指针，sibling代表兄弟的指针。
    parent->nextsibling.push_back(sibling);     //调用 std::vector 类的 push_back() 方法，将 sibling 添加到 parent->nextsibling 的末尾。
}

// 初始化树
CSTree* initTree() {
    CSTree* tree = new CSTree();     //创建新的树tree
    tree->root = nullptr;     //树的根节点指针设为空
    return tree;     //返回树的指针
}

// 构建树
void buildTree(CSTree* tree) {     //接受树的结构体CSTree*的指针tree，用于增加树结点的数据
    //用户键入树的结点数据data
    char data;
    std::cout << "输入根节点数据: ";
    std::cin >> data;

    // 创建根节点
    CSNode* root = createNode(data);    //创建根结点，并将用户输入的data赋值到根节点
    tree->root = root;      //根节点的指针赋值给tree的root成员变量，将根节点连接到树中

    std::vector<CSNode*> nodeQueue;  // 创建辅助队列nodeQueue，其数据类型为树的结点类型CSNode，用于辅助构建树
    nodeQueue.push_back(root);      //调用 std::vector 类的 push_back() 方法，将根节点的指针root添加到结点队列nodeQueue，作为开始构建树的起点

    while (!nodeQueue.empty()) {    //当辅助队列nodeQueue的结点不为空时，执行以下循环
        CSNode* currentNode = nodeQueue.front();    //从辅助队列nodeQueue中获取队首元素的值。nodeQueue.front()获取结点队列的第一个结点的指针，并将其赋值给变量currentNode
        nodeQueue.erase(nodeQueue.begin());     //辅助队列nodeQueue队首元素出队。这行代码使用erase()函数从结点队列中移除第一个结点。begin()函数返回队列的起始迭代器，它指向队列的第一个元素

        //用户键入树的当前结点data赋值到辅助队列的结点currentNode，并键入孩子结点数量childCount
        int childCount;
        std::cout << "输入节点 " << currentNode->data << " 的子节点数量: ";
        std::cin >> childCount;

        CSNode* prevChild = nullptr;    //在构建树的过程中，用于保存上一个添加的孩子节点的指针prevChild。

        //当用户键入的子结点个数＜孩子结点数量childCount时，执行以下循环
        for (int i = 0; i < childCount; i++) {
            //用户键入树的孩子结点数据childData
            char childData;
            std::cout << "输入子节点 " << i + 1 << " 的数据: ";
            std::cin >> childData;

            // 创建孩子结点
            CSNode* childNode = createNode(childData);

            if(prevChild == nullptr){
                addChild(currentNode, childNode);   //当 prevChild 指向null时，表示当前节点是前一个节点的孩子节点。
            }else{
                addSibling(prevChild, childNode);   //当 prevChild 指向结点时，表示当前节点是前一个节点的右兄弟节点。
            }
            
            prevChild = childNode;    // 将孩子结点childNode赋值为prevChild，用于判断下一个结点的输入
            nodeQueue.push_back(childNode);     // 将孩子结点childNode加入辅助队列nodeQueue，在下一轮循环中作为父结点构建其孩子链表
        }
    }
}

//递归输出树的结构
void printTreeWithDepth(CSNode* node, int depth){
    if(node == nullptr)
        return;

    std::cout << "树结点: " << node->data << " 深度: " << depth << std::endl;

    // 递归打印左子树和右兄弟
    for(CSNode* child : node->firstchild){
        printTreeWithDepth(child,depth = depth + 1);
    }
    for(CSNode* sibling : node->nextsibling){
        printTreeWithDepth(sibling,depth);
    }
}

// 获取输出二叉树的结构
void printBinaryTreeWithDepth(CSNode* node, int depth) {
    if(node == nullptr)
        return;

    std::cout << "二叉树结点: " << node->data << " 深度: " << depth << std::endl;

    // 递归打印二叉树
    for(CSNode* child : node->firstchild){
        printBinaryTreeWithDepth(child,depth = depth + 1);
    }
    for(CSNode* sibling : node->nextsibling){
        printBinaryTreeWithDepth(sibling,depth =  depth + 1);
    }
}

// 获取树的高度
int getHeight(CSNode* node){
    if(node == nullptr)
        return 0;

    int maxHeight = 0;

    for(CSNode* child : node->firstchild){
        int height = getHeight(child);
        maxHeight = std::max(maxHeight, height);
    }

    for(CSNode* sibiling : node->nextsibling){
        int height = getHeight(sibiling);
        maxHeight = std::max(maxHeight, height);
    }

    return maxHeight + 1;
}

int main() {
    CSTree* tree = initTree();  // 初始化树

    buildTree(tree);  // 构建树

    std::cout << std::endl;
    printTreeWithDepth(tree->root,0);  // 输出树的结点

    std::cout << std::endl;
    printBinaryTreeWithDepth(tree->root,0);  // 输出二叉树的结点

    std::cout << std::endl;
    int height = getHeight(tree->root);  // 输出二叉树的高度
    std::cout << "二叉树的高度：" << height <<std::endl;

    delete tree;  // 释放内存

    return 0;
}

运行的效果如下图所示：

备注：注意树的判定式if(prevChild == nullptr)，prevChild作为指针判定下一个结点应该是孩子结点或是兄弟结点，根据口诀“左孩子右兄弟”，这里手动模拟一下构建树的流程~

第一趟,用户键入根结点R，队列：[R]~

1） 树：null; 队首currentNode：R出队并记录；用户键入3个子结点A、B、C，进入孩子结点循环~
       R

2） 上一个孩子节点prevChild 指向null，childNode孩子结点 A接入 currentNode当前结点 R的左孩子指针，表示为R的孩子~树的结构如下：
       R
      /  
     A 
    上一个孩子结点prevChild指向结点A，结点A入队，队列：[A]；

3） 上一个孩子节点prevChild 指向结点A，不为空，因此childNode孩子结点 B接入 currentNode当前结点 A的右孩子指针，表示为A的兄弟~树的结构如下：
       R
      /      
     A        
      \        
       B 
    上一个孩子结点prevChild指向结点B，结点B入队，队列：[A，B]；
4） 上一个孩子节点prevChild 指向结点B，不为空，因此childNode孩子结点 C接入 currentNode当前结点 B的右孩子指针，表示为B的兄弟~树的结构如下：
       R
      /      
     A        
      \        
       B 
        \        
         C 
    上一个孩子结点prevChild指向结点C，结点C入队，队列：[A，B, C]；
5）用户键入的子结点个数=孩子结点数量childCount; 本轮孩子结点循环结束~


第二趟,队首currentNode：A出队并记录，用户键入结点A的2个子结点D、E，进入孩子结点循环~

1） 上一个孩子节点prevChild 指向null[代码重置]，childNode孩子结点 D接入 currentNode当前结点 A的左孩子指针，表示为A的孩子~树的结构如下：
       R
      /      
     A        
    / \        
   D   B 
        \        
         C 
    上一个孩子结点prevChild指向结点D，结点D入队，队列：[B, C，D]；
2） 上一个孩子节点prevChild 指向结点D，childNode孩子结点 E接入 currentNode当前结点 D的右孩子指针，表示为D的兄弟~树的结构如下：
       R
      /      
     A        
    / \        
   D   B 
    \   \        
     E   C 
    上一个孩子结点prevChild指向结点E，结点E入队，队列：[B, C，D，E]；

第三趟,队首currentNode：B出队并记录，用户键入结点B的子结点为0，不会进入孩子结点循环~树的结构与第二趟相同，队列：[C，D，E]；

第四趟，队首currentNode：C出队并记录，用户键入结点C的1个子结点F，进入孩子结点循环~

1） 上一个孩子节点prevChild 指向null[代码重置]，childNode孩子结点 F接入 currentNode当前结点 C的左孩子指针，表示为C的孩子~树的结构如下：
       R
      /      
     A        
    / \        
   D   B 
    \   \        
     E   C 
        /
       F
    上一个孩子结点prevChild指向结点F，结点F入队，队列：[D，E，F]；

第五~六趟,队首currentNode：D、E出队并记录，用户键入结点D、E的子结点为0，不会进入孩子结点循环~树的结构与第四趟相同，队列：[F]；


第七趟,队首currentNode：E出队并记录，用户键入结点C的3个子结点G、H、K，进入孩子结点循环，过程略，树的结构如下~
       R
      /      
     A        
    / \        
   D   B 
    \   \        
     E   C 
        /
       F
      /
     G
      \
       H
        \
         K
    上一个孩子结点prevChild指向结点K，结点K入队，队列：[G，H，K]；

第八~十趟,队首currentNode：G，H，K出队并记录，用户键入结点G，H，K的子结点为0，不会进入孩子结点循环~树的结构与第七趟相同，队列为空，退出循环~

图源：文心一言

二叉树

二叉树的概念

定义

(1)每个结点至多只能有两棵子树（即二叉树中不存在度大于2的结点），可以为空树;

(2)二叉树的子树有左右之分，其次序不能任意颠倒。

特殊的二叉树

(1)满二叉树：高度为h，且含有2^h - 1个结点的的二叉树，即树中的每层都含有最多的结点。

(2)完全二叉树：高度为h，有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时，称为完全二叉树。

(3)二叉排序树：左子树上所有结点的关键字均小于根结点的关键字；右子树上的所有结点的关键字均大于根节点的关键字；左子树和右子树又各是一棵二叉排序树。

(4)平衡二叉树：树上任意一个结点的左子树和右子树的深度之差不超过1。

二叉树的性质

（1）普通二叉树

• 结点与结点：非空二叉树上，叶结点数 = 度为2的结点数 + 1，即 n0 = n2 + 1；

        //  二叉树的结点总数=n0+n1+n2，二叉树的分支或边总数=n1+2n2；树的结点总数=树的分支总数+1(根节点)，则n0+n1+n2=n1+2n2+1，得n0=n2+1。

        //  另，在完全二叉树，最多只会有1个是度为1的结点，n1的取值范围为0或1。

• 结点与度：非空二叉树上，在第 k 层上结点数 ≤ 2^(k-1)；
• 结点与高：高度为h的二叉树 结点数 n ≤ 2^h -1;

        //  以上性质均与树的性质相互对照。

（2）完全二叉树

• 结点与编号：
  • i > 1时，结点 i 的双亲编号为 ⌊ i / 2 ⌋("⌊⌋"表示向上取整)；
  • 2i ≤ n时，结点 i 的左孩子编号为 2i , 否则无左孩子；
  • 2i + 1 ≤ n时，结点 i 右孩子编号为2i+1，否则无右孩子；
• 结点与高度：
  • 结点 i 所在层次（深度为）⌊ log i ⌋ + 1("log"无底数时默认以2为底数)；
  • 具有 n 个结点的完全二叉树高度为 ⌈ log (n+1) ⌉ 或⌊ log n ⌋ + 1。

                  //  以上性质均与树“结点与高”性质相互对照，完全二叉树的树高 2^(h-1) -1 ＜n ≤ 2^h -1 ，或 2^(h-1) ≤ n ＜ 2^h -1~

二叉树的存储结构

（1）顺序存储结构

• 定义：用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素。即将完全二叉树上编号为 i 的结点元素存储在一维数组下边为 i-1 的分量中。
• 适用：依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，逻辑直观，且节省存储空间。    //所以顺序存储应该不是重点
• 结构：顺序表即可，增删改查操作可见👉线性表[顺序表+链表]

#define MaxSize 16

typedef struct {
    ElemType data[MaxSize];  // 存储二叉树的数组
    int length;     // 树的当前长度
} BiTree;

（2）链式存储结构

• 定义：采用链式存储结构，用链表结点来存储二叉树中的每个结点。
• 适用：一般都采用二叉树的性质存储。
• 结构：结点结构通常包括若干数据域和指针域，二叉链表中至少包含3个域：数据域、左指针域、右指针域。

typedef struct BiTNode{
    ElemType data;    //数据域；
    struct BiTNode *lchild, *rchild;    //左、右孩子指针；
}BiTNode,*BiTree;

二叉树的遍历

先序、中序、后序遍历的定义与手动推算

二叉树的遍历：是指按某条搜索路径访问树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。常见的遍历次序有先序、中序和后序三种遍历算法~目的是使树这种非线性结构最后能以线性的方式输出~

• 先序遍历：如果树不为空，则依次访问树的根节点、左子树、右子树 ；
• 中序遍历：如果树不为空，则依次访问树的左子树、根节点、右子树 ；
• 后序遍历：如果树不为空，则依次访问树的左子树、右子树、根节点。

举栗：在这里简单复现一下 机智的王道咸鱼老师 教的两种树的手算法~

递归遍历算法思想概要： 

• 递归切分法（非官方称呼）：适用于程序递归算法——
  • 先序遍历：如果树非空，访问根节点，调用递归访问左子树，调用递归访问右子树，完结撒花~
  • 中序遍历：如果树非空，调用递归访问左子树，访问根节点，调用递归访问右子树，完结撒花~
  • 后序遍历：如果树非空，访问根节点，调用递归访问左子树，调用递归访问右子树，完结撒花~

递归遍历手动推算及案例： 

• 递归切分法（非官方称呼）：手动推算版本，个人就觉得有点绕，大致就是将树以结点为单位，从顶至底无限切分，然后以遍历顺序开始访问~
• 以配图为例说明手动推算步骤——
  • 将树切分为根（1）、左子树（2、4、6）、右子树（3、5）；
  • 将左子树（2、4、6）看作整体，继续细分，又可以得到局部根结点（2）与右子树（4、6），其左子树为空；
  • 将左子树（4、6）看作整体，继续细分，又可以得到局部根结点（4）与左子树（6），其右子树为空；
  • 将右子树（3、5）看作整体继续细分，又可以得到局部根结点（3）与右子树（5），其左子树为空；
• 先序遍历：按照根、左、右的顺序，访问
  • →1（总树的根结点）
  • →2（1作为根结点，左子树的局部根结点2）
  • →4（2作为局部根结点无左子树，则访问右子树的局部根结点4）
  • →6（4作为局部根结点相连的左子树，至此总根的左子树访问完成）
  • →3（1作为根结点，右子树的局部根结点3）
  • →5（3作为局部根结点无左子树，访问右子树）
• 中序遍历：按照左、根、右的顺序，访问
  • →2（1作为根结点的左子树，局部根结点2，无左子树则访问根结点2）
  • →6（2作为局部根结点无左子树，其右子树4作为局部根结点，具有左子树为6）
  • →4（4作为局部根结点无右子树，至此总根结点1左侧访问完成）
  • →1（总根结点1）
  • →3（1作为局部根结点无左子树，局部根结点3，无左子树则访问根结点3）
  • →5（3作为局部根结点，左子树与根访问完成，则访问右子树）
• 后序遍历：按照左、右、根的顺序，访问
  • →6（跳过根结点1-及其左子树的局部根结点2-及其右子树的局部根结点4）
  • →4（6属于左子树，无右兄弟，访问父结点4）
  • →2（4属于右子树，访问父结点2）
  • →5（2属于左子树，有右兄弟3，但3有子树5，则跳过局部根结点3先访问5）
  • →3（5属于右子树，访问父结点3）
  • →1（3属于右子树，访问父结点1）

 非递归遍历算法思想概要： 

• 环绕计数法（非官方称呼）：适用于程序非递归算法——
  • 先序|中序，将指针的位置赋给树的根，树不为空且指针不为空时，循环：
    • 如果指针指向 非空结点——
      • 若是先序遍历，此处访问结点~
      • 指针指向的结点入栈~
      • 指针依次访问结点指向的左孩子，进行下一轮循环~
    • 如果指针指向 空结点——
      • 指针退回父结点的位置（指针指向栈顶元素）~
        • 指针指向结点的右孩子~
        • 若是中序遍历，此处访问结点~
        • 栈顶元素出栈，进行下一轮循环~
  • 后序，将指针的赋给树的根，树不为空且指针不为空时，循环：
    • 如果指针指向 非空结点——
      • 指针指向的结点入栈~
      • 指针依次访问结点指向的左孩子~
    • 如果指针指向 空结点——
      • 指针退回父结点的位置（指针指向栈顶元素）~
      • 如果该结点有未被记录的右孩子~
        • 访问结点的右孩子，进行下一轮循环~
      • 如果该结点没有右孩子，或右孩子已被记录（说明当前节点及其子树已经遍历完成）~
        • 栈顶元素访问并出栈~
        • 记录指针当前的位置（作为下一个待处理节点的父结点）~
        • 指针置空，进行下一轮循环~

 非递归遍历手动推算及案例： 

• 环绕计数法（非官方称呼）：手动推算理解版本——
  • 先序遍历记录第1次经过的结点，中序遍历记录第2次经过的结点，后序遍历记录第3次经过的结点~
  • 从根结点的上方开始沿着树的轮廓开始逆时针画线~
  • 如上图，将树的分支结点与叶子结点均补全为度为2的分支结点~
• 以配图为例说明手动推算步骤——
• 先序遍历：按照根、左、右的顺序，访问
  • →1（父结点null经过1次）
  • →2（父结点1经过1次）
  • →4（父结点2经过1次）
  • →6（父结点4经过1次）
  • →3（父结点1经过1次）
  • →5（父结点3经过1次）
• 中序遍历：按照左、根、右的顺序，访问
  • →2（父结点1经过1次，2的左孩子null结点经过1次）
  • →6（父结点4经过1次，6的左孩子null结点经过1次）
  • →4（父结点2经过1次，4的左孩子5结点经过1次）
  • →1（父结点null经过1次，1的左孩子2结点经过1次）
  • →3（父结点1经过1次，3的左孩子null结点经过1次）
  • →5（父结点3经过1次，5的左孩子null结点经过1次）
• 后序遍历：按照左、右、根的顺序，访问
  • →6（父结点1经过1次，左孩子null经过1次、右孩子null经过1次）
  • →4（父结点2经过1次，左孩子6经过1次、右孩子null经过1次）
  • →2（父结点1经过1次，左孩子null经过1次、右孩子4经过1次）
  • →5（父结点3经过1次，左孩子null经过1次、右孩子null经过1次）
  • →3（父结点1经过1次，左孩子null经过1次、右孩子5经过1次）
  • →1（父结点null经过1次，左孩子2经过1次、右孩子3经过1次）

先序、中序、后序遍历的核心代码

要求：复现上一张图中的树，篇幅限制，代码注释见算法思想概要~

#include <iostream>
#include <stack>
#include <queue>

typedef struct BiTNode {
    int data;
    struct BiTNode* lchild, * rchild;
} BiTNode, * BiTree;

void visit(int data) {
    std::cout << data << " ";
}

void PreOrder(BiTree T) {
    if (T != NULL) {
        visit(T->data);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

void InOrder(BiTree T) {
    if (T != NULL) {
        InOrder(T->lchild);
        visit(T->data);
        InOrder(T->rchild);
    }
}

void PostOrder(BiTree T) {
    if (T != NULL) {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        visit(T->data);
    }
}

void PreOrder2(BiTree T) {
    std::stack<BiTree> S;
    BiTree p = T;

    while (p || !S.empty()) {
        if (p) {
            visit(p->data);
            S.push(p);
            p = p->lchild;
        }
        else {
            p = S.top();
            S.pop();
            p = p->rchild;
        }
    }
}

void InOrder2(BiTree T) {
    std::stack<BiTree> S;
    BiTree p = T;

    while (p || !S.empty()) {
        if (p) {
            S.push(p);
            p = p->lchild;
        }
        else {
            p = S.top();
            S.pop();
            visit(p->data);
            p = p->rchild;
        }
    }
}

void PostOrder2(BiTree T) {
    std::stack<BiTree> S;
    BiTree p = T;
    BiTree r = NULL;

    while (p || !S.empty()) {
        if (p) {
            S.push(p);
            p = p->lchild;
        }
        else {
            p = S.top();
            if (p->rchild && p->rchild != r)
                p = p->rchild;
            else {
                S.pop();
                visit(p->data);
                r = p;
                p = NULL;
            }
        }
    }
}

// 构建树
void buildTree(BiTree* tree) {
    int data;
    std::cout << "输入根节点数据: ";
    std::cin >> data;

    BiTNode* root = new BiTNode;
    root->data = data;

    std::queue<BiTNode*> nodeQueue;
    nodeQueue.push(root);

    while (!nodeQueue.empty()) {
        BiTNode* currentNode = nodeQueue.front();
        nodeQueue.pop();

        int childCount;
        std::cout << "输入节点 " << currentNode->data << " 的子节点数量: ";
        std::cin >> childCount;

        switch (childCount) {
        case 2:
            {
                for (int i = 0; i < 2; ++i) {
                    int childData;
                    std::cout << "输入第 " << i + 1 << " 个子节点的数据: ";
                    std::cin >> childData;

                    char childType;
                    std::cout << "输入第 " << i + 1 << " 个子节点是左孩子还是右孩子（L/R）: ";
                    std::cin >> childType;

                    BiTNode* childNode = new BiTNode;
                    childNode->data = childData;
                    childNode->lchild = NULL;
                    childNode->rchild = NULL;

                    if (childType == 'L') {
                        currentNode->lchild = childNode;
                    } else if (childType == 'R') {
                        currentNode->rchild = childNode;
                    }

                    nodeQueue.push(childNode);
                }
            }
            break;
        case 1:
            {
                int childData;
                std::cout << "输入子节点的数据: ";
                std::cin >> childData;

                char childType;
                std::cout << "输入子节点是左孩子还是右孩子（L/R）: ";
                std::cin >> childType;

                BiTNode* childNode = new BiTNode;
                childNode->data = childData;
                childNode->lchild = NULL;
                childNode->rchild = NULL;

                if (childType == 'L') {
                    currentNode->lchild = childNode;
                } else if (childType == 'R') {
                    currentNode->rchild = childNode;
                }

                nodeQueue.push(childNode);
            }
            break;
        case 0:
            // 跳过判定，不添加子节点
            break;
        }
    }

    *tree = root;
}

// 释放树的内存
void releaseTree(BiTree tree) {
    if (tree == NULL) {
        return;
    }

    releaseTree(tree->lchild);
    releaseTree(tree->rchild);
    delete tree;
}

int main() {
    BiTree tree = nullptr;

    std::cout << "层次遍历构建树:\n";
    buildTree(&tree);

    std::cout << "递归先序遍历: ";
    PreOrder(tree);

    std::cout << "\n递归中序遍历: ";
    InOrder(tree);

    std::cout << "\n递归后序遍历: ";
    PostOrder(tree);

    std::cout << "\n非递归先序遍历: ";
    PreOrder2(tree);

    std::cout << "\n非递归中序遍历: ";
    InOrder2(tree);

    std::cout << "\n非递归后序遍历: ";
    PostOrder2(tree);

    releaseTree(tree);

    return 0;
}

代码运行结果如下~

结语

博文到此结束，写得模糊或者有误之处，欢迎小伙伴留言讨论与批评，包括但不限于以下内容~😶‍🌫️文章来源地址https://www.toymoban.com/news/detail-476408.html

• 小白视角：这段代码不理解，博主需要增加语法注释、逻辑注释、配图或者动图说明~
• 大佬视角：这写的是什么玩意儿？！C++是这么写的嘛，老子有意见！
• 路人视角：随便翻到，与我无关。确实挺长，写得不容易，不如默默给个赞支持一下博主？
• 福利视角：直接翻到最后，博文不重要，记得经常发红包就可以了，好人一生平安，懂？！

到了这里，关于数据结构05：树的定义与双亲、孩子表示法[更新中]的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！