【数据结构与算法】树，森林，二叉树之间的转换

树的定义递归定义树是满足以下条件的结构有且仅有一个根节点没有父节点的节点其他节点分成m 个互不相交的子树每个子树本身也是一棵树树的基本术语术语解释例子根节点最顶层的节点没有父节点文件夹系统的根目录父节点直接上层节点上一级文件夹子节点直接下层节点文件夹里的内容兄弟节点同一父节点的节点同一文件夹下的子文件夹叶子节点没有子节点的节点文件不是文件夹度一个节点拥有的子节点个数文件夹里有几个项目深度/层次根节点到该节点的路径长度文件在第几层目录树的图示根节点 A第1层度为3 / | \ B C D第2层C的度为2 / \ E F第3层叶子节点树的特点没有回路不会形成环节点之间有明确的层级关系每个节点只有一个父节点除了根树是连通的从根可以到达任何节点森林Forest是什么森林就是m 棵互不相交的树的集合m ≥ 0。通俗理解一棵树就像你电脑里的一个文件夹系统森林就像整个硬盘里的多个独立的文件夹系统C盘、D盘、E盘它们之间没有关联森林的图示森林 多棵独立的树 树1 树2 树3 A X M / \ | | B C Y N | | D O 这三棵树之间没有连线相互独立森林与树的关系关系说明树是特殊的森林森林可以是1棵树m1森林可以变成树加一个虚拟根节点把多棵树连起来树可以变成森林删除根节点剩下的子树就是森林关键联系删掉树的根节点剩下的就是森林给森林加一个虚拟根节点就变成一棵树三、树的分类类型特点例子二叉树每个节点最多2个子节点表达式树、排序树满二叉树所有节点都有0或2个子节点完美平衡的二叉树完全二叉树除了最后一层其他层都填满堆Heap二叉搜索树左子树 根 右子树快速查找多叉树每个节点可以有多个子节点文件系统、B树平衡树左右子树高度差不超过1AVL树、红黑树二叉树Binary Tree是什么二叉树是一种特殊的树结构它的核心约束是每个节点最多只能有两个子节点分别称为左子节点和右子节点。二叉树 vs 普通树对比普通树二叉树节点度数任意可以有多个子节点最多2个0、1或2子节点顺序通常无序严格区分左右有序表示方式孩子兄弟表示法转二叉树标准二叉链表关键区别普通树一个节点可以有 3 个、5 个甚至更多孩子二叉树一个节点最多 2 个孩子并且区分左右二、二叉树的五种基本形态1. 空二叉树 2. 只有根节点 3. 只有左子树 ( ) A A / / B 4. 只有右子树 5. 左右子树都有 A A \ / \ B B C三、特殊二叉树类型定义图示特点满二叉树所有非叶子节点都有两个子节点且所有叶子节点在同一层每层都填满节点数 2^h - 1h为高度完全二叉树除了最后一层其他层都填满最后一层节点尽量靠左堆的结构可以用数组存储索引计算方便二叉搜索树左子树所有节点 根节点 右子树所有节点中序遍历有序查找/插入/删除 O(log n)平衡二叉树任意节点的左右子树高度差 ≤ 1AVL树、红黑树防止退化成链表完美二叉树同满二叉树每个节点都有0或2个子节点-图示对比满二叉树 完全二叉树 不完全二叉树 1 1 1 / \ / \ / \ 2 3 2 3 2 3 / \ / \ / \ / / \ 4 5 6 7 4 5 6 4 5 \ 6四、二叉树的重要性质性质公式说明第i层最多节点数2^(i-1)i ≥ 1高度为h的树最多节点数2^h - 1h ≥ 1根高度为1叶子节点数关系n0 n2 1n0叶子数n2度为2的节点数完全二叉树节点编号左孩子2i右孩子2i1根从1开始完全二叉树高度⌊log2 n⌋ 1n为节点数树 → 二叉树的转换方法一三步法容易理解原树textA / | \ B C D / \ E FStep 1加线连接兄弟将同一父节点的兄弟节点用线连起来textA / | \ B--C--D / \ E--FStep 2删线只保留长子每个节点只保留与第一个孩子的连线删除与其他孩子的连线textA / B \ C / \ E D \ F解释A只保留与B的连线删除与C、D的连线C只保留与E的连线删除与D的连线等等D不是C的孩子是兄弟实际上这一步要小心处理让我重新做Step 2正确版删线text原树连线 A-B, A-C, A-D, C-E, C-F 删除A-C, A-D只保留A-B C-F? C-E保留E是第一个孩子 C-D? C和D不是父子关系 结果 A → B C → E 其他连线B、C、D之间的关系还没处理其实更清晰的方法是直接用法二。方法二直接法推荐直接按照左孩子右兄弟规则构建原树textA / | \ B C D / \ E F逐节点转换节点第一个孩子下一个兄弟二叉树表示AB无A.left B, A.right nullB无CB.left null, B.right CCEDC.left E, C.right DD无无D.left null, D.right nullE无FE.left null, E.right FF无无F.left null, F.right null最终二叉树textA / B \ C / \ E D \ F验证A的左孩子是B ✓B是A的第一个孩子B的右孩子是C ✓C是B的下一个兄弟C的左孩子是E ✓E是C的第一个孩子C的右孩子是D ✓D是C的下一个兄弟E的右孩子是F ✓F是E的下一个兄弟三、更复杂的例子原树text1 / | \ 2 3 4 / \ | 5 6 7 | 8逐节点分析节点第一个孩子下一个兄弟二叉树12无left2, rightnull253left5, right33无4leftnull, right447无left7, rightnull5无6leftnull, right668无left8, rightnull7无无leftnull, rightnull8无无leftnull, rightnull转换后的二叉树text1 / 2 / \ 5 3 \ \ 6 4 / / 8 7图解text1 / 2 / \ 5 3 \ \ 6 4 / 8 \ 7? 等等这里有问题 让我重新画正确的实际上更清晰的画法用缩进表示层级text1 └─ 2 (左) ├─ 5 (左) │ └─ 6 (右) │ └─ 8 (左) └─ 3 (右) └─ 4 (右) └─ 7 (左)#include iostream #include vector #include queue using namespace std; // 原树的节点普通树度不限 struct TreeNode { int val; vectorTreeNode* children; // 可以有多个孩子 TreeNode(int x) : val(x) {} }; // 二叉树的节点 struct BinaryTreeNode { int val; BinaryTreeNode* left; // 第一个孩子 BinaryTreeNode* right; // 下一个兄弟 BinaryTreeNode(int x) : val(x), left(NULL), right(NULL) {} }; // 树 → 二叉树 BinaryTreeNode* treeToBinaryTree(TreeNode* root) { if (root NULL) return NULL; // 创建二叉树节点 BinaryTreeNode* binaryRoot new BinaryTreeNode(root-val); // 处理第一个孩子左指针 if (!root-children.empty()) { binaryRoot-left treeToBinaryTree(root-children[0]); } // 处理兄弟节点右指针 // 注意原树的兄弟关系需要额外处理 BinaryTreeNode* current binaryRoot-left; for (int i 1; i root-children.size(); i) { current-right treeToBinaryTree(root-children[i]); current current-right; } return binaryRoot; } // 更简洁的递归版本推荐 BinaryTreeNode* convert(TreeNode* root) { if (root NULL) return NULL; BinaryTreeNode* binaryNode new BinaryTreeNode(root-val); // 第一个孩子成为左孩子 if (!root-children.empty()) { binaryNode-left convert(root-children[0]); } // 剩下的孩子成为右链兄弟关系 BinaryTreeNode* p binaryNode-left; for (int i 1; i root-children.size(); i) { p-right convert(root-children[i]); p p-right; } return binaryNode; } // 辅助函数打印二叉树先序遍历 void printBinaryTree(BinaryTreeNode* root) { if (root NULL) return; cout root-val ; printBinaryTree(root-left); printBinaryTree(root-right); } // 测试 int main() { // 构建原树 // 1 // /|\ // 2 3 4 // / \ // 5 6 TreeNode* root new TreeNode(1); root-children.push_back(new TreeNode(2)); root-children.push_back(new TreeNode(3)); root-children.push_back(new TreeNode(4)); root-children[0]-children.push_back(new TreeNode(5)); root-children[0]-children.push_back(new TreeNode(6)); // 转换 BinaryTreeNode* binaryRoot convert(root); // 输出转换结果 cout 转换后的二叉树先序遍历: ; printBinaryTree(binaryRoot); // 预期输出1 2 5 6 3 4 // 这对应原树的先根遍历顺序 return 0; }就是按每一层来看每一层的某几个节点如果是同一个父节点就把最左边的那个点和父节点相连接其他点变成最左边那个点右的孩子对于同一父节点的多个孩子 第1个孩子 → 挂在父节点的【左指针】上 第2个孩子 → 挂在第1个孩子的【右指针】上 第3个孩子 → 挂在第2个孩子的【右指针】上 ... 第k个孩子 → 挂在第(k-1)个孩子的【右指针】上森林 → 二叉树的转换你的理解已经非常好了森林转换就是在树转二叉树的基础上再多做一步把多棵树的根节点串起来。核心规则在你的理解上扩展森林 多棵独立的树转换步骤先将每棵树分别转换成二叉树用你刚学会的方法父连长子长子连兄弟把第一棵树的根作为总根把第二棵树的根作为第一棵树根的右孩子把第三棵树的根作为第二棵树根的右孩子以此类推...口诀树转二叉根串成链