米娜桑好久不见，国庆期间没有更新博客，属实有点摆烂

今天我们的主题是树与二叉树的转换，以及树的储存方法，遍历方法与二叉树的区别等

首先，我们要明白的是，树可以有多个子节点，而二叉树最多只有两个，所以二叉树是特殊的树

一.树的存储与转换

1.父亲表示法（双亲表示法）

使用一个数组来存储每个节点，其中每个节点只包含一个指针（或索引），指向其父节点。这种表示法的缺点是无法快速找到子节点，但优点是节省了存储空间。
1
2
3
4
struct TreeNode {
int data;
int parentIndex; // 指向父节点在数组中的索引
};

2.孩子链表表示法

使用一个数组来存储每个节点，每个节点包含一个链表，链表中的每个节点指向该节点的子节点。这样，查找子节点的时间较快，但会增加空间开销。

// 孩子链表中的节点
struct ChildNode {
    int childIndex;        // 子节点的索引（或指针）
    ChildNode* next;       // 指向下一个子节点的指针
};

// 树的节点
struct TreeNode {
    int data;              // 数据域，存储该节点的值
    ChildNode* childList;  // 指向孩子链表的指针
};

（1）孩子链表表示法的特点

灵活性：
- 每个节点的子节点数量不受限制，子节点数量可以动态扩展，因此这种表示法适合多叉树（即节点可以有多个子节点的树）。
存储空间：
- 每个节点只存储一个指向其孩子链表的指针，而不是为所有可能的子节点预留空间，因此相比顺序存储更加节省空间，特别适合子节点数量较不确定的树结构。
节点操作：
- 插入节点：插入新子节点只需要在孩子链表的末尾添加一个节点，操作比较简单。
- 删除节点：删除某个子节点时，只需要从孩子链表中移除相应的节点，但需要额外处理该子节点的所有子节点。
- 查找子节点：查找某个节点的子节点时，需要遍历该节点的孩子链表，这可能导致查找子节点的效率较低。

（2）孩子链表表示法的示例

假设有如下树结构：

对应的孩子链表表示法如下：

节点 1 的孩子链表指向节点 2、3 和 4。
节点 3 的孩子链表指向节点 5 和 6。

图解：

1 2	TreeNode(1) -> ChildList -> [TreeNode(2)] -> [TreeNode(3)] -> [TreeNode(4)] -> NULL TreeNode(3) -> ChildList -> [TreeNode(5)] -> [TreeNode(6)] -> NULL

对应的代码结构：

// 定义孩子链表中的节点
struct ChildNode {
    int childIndex;         // 孩子的索引或指针
    ChildNode* next;        // 下一个孩子的指针
};

// 定义树的节点
struct TreeNode {
    int data;               // 节点的值
    ChildNode* childList;   // 孩子链表的头指针
};

// 示例：创建节点和孩子链表
TreeNode node1, node2, node3, node4, node5, node6;
node1.data = 1;
node2.data = 2;
node3.data = 3;
node4.data = 4;
node5.data = 5;
node6.data = 6;

// 为节点1创建孩子链表
ChildNode* child1 = new ChildNode{2, NULL};  // 指向节点2
ChildNode* child2 = new ChildNode{3, NULL};  // 指向节点3
ChildNode* child3 = new ChildNode{4, NULL};  // 指向节点4

child1->next = child2;
child2->next = child3;
node1.childList = child1;  // 节点1的孩子链表

// 为节点3创建孩子链表
ChildNode* child5 = new ChildNode{5, NULL};  // 指向节点5
ChildNode* child6 = new ChildNode{6, NULL};  // 指向节点6
child5->next = child6;
node3.childList = child5;  // 节点3的孩子链表

3.孩子兄弟表示法

在树结构中，孩子和兄弟是指节点之间的一种关系：

孩子（Child）：

孩子节点是指某个节点的直接下级节点。
如果一个节点有若干子节点，这些子节点就是它的孩子。
每个树节点可以有0个、1个或多个孩子。

兄弟（Sibling）：

兄弟节点是指同一个父节点的多个子节点之间的关系。
如果两个或多个节点有相同的父节点，这些节点互为兄弟。

（1）

孩子兄弟表示法，是以左孩子的形式存储最左边的孩子，以右孩子的形式存储第一个右兄弟

// 定义多叉树节点结构
struct MultiTreeNode {
    int data;                    // 数据域
    vector<MultiTreeNode*> children; // 子节点列表
};

// 定义二叉树节点结构
struct BinaryTreeNode {
    int data;                    // 数据域
    BinaryTreeNode* left;        // 左子节点，表示第一个子节点
    BinaryTreeNode* right;       // 右子节点，表示兄弟节点
};

通过这样的形式将树以二叉树的形式存储了起来，进而实现了树向二叉树的转换

转换步骤：

保持第一个子节点为左孩子：
- 在多叉树中，某个节点的第一个子节点转换为二叉树中的左孩子。
其他子节点变为右兄弟：
- 在多叉树中，该节点的第二个及以后的子节点依次作为第一个子节点的右兄弟节点。
兄弟之间的关系通过右子节点表示：
- 在二叉树中，右子节点用来表示多叉树中的兄弟节点。

转换示意图

假设有如下的多叉树结构：

     A
   / | \
  B  C  D
 / \
E   F

转换成二叉树的步骤如下：

节点 A 的第一个子节点 B 作为 A 的左孩子，C 和 D 作为 B 的右兄弟。
节点 B 的第一个子节点 E 作为 B 的左孩子，F 作为 E 的右兄弟。

转换成二叉树后的结构如下：

    A
   /
  B
 / \
E   C
 \   \
  F   D

可以看到，在转换后的二叉树中：

原来多叉树中节点 A 的子节点 B、C、D 被通过左孩子和右兄弟关系串联在一起。
原来节点 B 的子节点 E、F 也通过相同的方式连接。

// 多叉树转二叉树的递归转换函数
BinaryTreeNode* convertToBinaryTree(MultiTreeNode* root)
{
if (root == nullptr) return nullptr;
// 创建对应的二叉树节点
BinaryTreeNode* newNode = new BinaryTreeNode();
newNode->data = root->data;
newNode->left = nullptr;
newNode->right = nullptr;

if (!root->children.empty())
{
// 将第一个孩子作为左子树
newNode->left = convertToBinaryTree(root->children[0]);

// 将其他孩子作为兄弟通过右子树连接
BinaryTreeNode* current = newNode->left;
for (size_t i = 1; i < root->children.size(); ++i)
{
current->right = convertToBinaryTree(root->children[i]);
current = current->right;
}
}

return newNode;
}

4.森林与二叉树的转换

将森林中的每棵树都转换成二叉树

然后从第二棵树开始，每棵树的根节点都是前一棵树的根节点的兄弟

二.树和森林的遍历

1.树的遍历

树的前序遍历和其转换成的二叉树的前序遍历相同

树的后序遍历与其转换成的二叉树的中序遍历相同

树的中序遍历

中序遍历树最左边的孩子，访问根节点，再依次访问中序遍历其他孩子