树和森林的遍历是 408 的重要考点特别是树的存储结构、森林与二叉树之间的转换关系。一、树的存储结构1. 双亲表示法classPTreeNode{intdata;intparent;// 父节点在数组中的下标}classPTree{PTreeNode[]nodes;introot;// 根节点下标intsize;}2. 孩子表示法classCTreeNode{intdata;ListIntegerchildren;// 孩子节点下标}3. 孩子兄弟表示法最常用classCSNode{intdata;CSNodefirstChild;// 第一个孩子CSNodenextSibling;// 下一个兄弟}二、树的遍历1. 先根遍历publicvoidpreOrder(CSNoderoot){if(rootnull)return;// 访问根节点System.out.print(root.data );// 遍历所有孩子第一个孩子的兄弟CSNodechildroot.firstChild;while(child!null){preOrder(child);childchild.nextSibling;}}2. 后根遍历publicvoidpostOrder(CSNoderoot){if(rootnull)return;CSNodechildroot.firstChild;while(child!null){postOrder(child);childchild.nextSibling;}System.out.print(root.data );}3. 层序遍历publicvoidlevelOrder(CSNoderoot){if(rootnull)return;QueueCSNodequeuenewLinkedList();queue.offer(root);while(!queue.isEmpty()){CSNodenodequeue.poll();System.out.print(node.data );// 所有孩子入队CSNodechildnode.firstChild;while(child!null){queue.offer(child);childchild.nextSibling;}}}三、森林与二叉树的转换1. 转换规则树 → 二叉树左孩子右兄弟 每个节点的左指针指向第一个孩子 每个节点的右指针指向下一个兄弟 森林 → 二叉树 将每棵树的根节点视为兄弟关系 第一棵树的根为二叉树的根 其他树的根依次作为右子树连接原始森林 树1A 树2E / \ / \ B C F G / D 转换为二叉树 A / \ B E / \ \ D C F \ G2. 二叉树 → 森林的还原publicclassForestConverter{/** * 二叉树还原为森林 * 根节点的左子树是第一棵树 * 右链上的所有节点都是单独的树 */publicListTreeNodebinaryTreeToForest(TreeNoderoot){ListTreeNodeforestnewArrayList();TreeNodecurrentroot;while(current!null){// 保存当前树的根TreeNodetreeRootcurrent;// 断开右链分离下一棵树TreeNodenextcurrent.right;current.rightnull;// 当前树的左子树还原为普通二叉树// 不需要额外操作左子树已经是二叉树的形态forest.add(treeRoot);currentnext;}returnforest;}}四、线索二叉树1. 为什么需要线索二叉树普通二叉树中中序遍历需要栈或递归 n 个节点的二叉树有 2n 个指针域只用了 n-1 个 大量空指针被浪费 线索二叉树利用空指针 左指针指向前驱 右指针指向后继2. 节点结构classThreadedNode{intdata;ThreadedNodeleft;ThreadedNoderight;intltag;// 0: left 指向左孩子, 1: left 指向前驱intrtag;// 0: right 指向右孩子, 1: right 指向后继publicThreadedNode(intdata){this.datadata;this.ltag0;this.rtag0;}}3. 中序线索化publicclassInorderThreading{privateThreadedNodeprev;/** * 中序线索化 */publicThreadedNodeinorderThreaded(ThreadedNoderoot){prevnull;inorder(root);// 处理最后一个节点if(prev!null){prev.rtag1;// 右指针指向后继null}returnroot;}privatevoidinorder(ThreadedNodenode){if(nodenull)return;// 1. 线索化左子树inorder(node.left);// 2. 处理当前节点if(node.leftnull){// 左指针指向前驱node.leftprev;node.ltag1;}if(prev!nullprev.rightnull){// 前驱的右指针指向当前节点prev.rightnode;prev.rtag1;}prevnode;// 3. 线索化右子树inorder(node.right);}/** * 中序遍历线索二叉树非递归 */publicvoidinorderTraversal(ThreadedNoderoot){ThreadedNodecurrentroot;// 找到中序第一个节点while(current!nullcurrent.ltag0){currentcurrent.left;}while(current!null){System.out.print(current.data );if(current.rtag1){// 有后继线索直接走线索currentcurrent.right;}else{// 没有后继线索走右子树的最左节点currentcurrent.right;while(current!nullcurrent.ltag0){currentcurrent.left;}}}}}4. 线索二叉树的遍历/** * 中序线索二叉树的遍历 * 不需要栈也不需要递归 * 时间复杂度 O(n)空间复杂度 O(1) * * 比普通中序遍历省掉了栈的空间 * 非常适合嵌入式等内存受限的环境 */五、森林的遍历与对应关系树的遍历对应二叉树的遍历先根遍历前序遍历后根遍历中序遍历层序遍历按层遍历不等价重要结论408 常考树的后根遍历序列 对应二叉树的中序遍历序列 树的先根遍历序列 对应二叉树的前序遍历序列 由树的先根和后根遍历序列可唯一确定一棵树六、408 考研常见考题题1树转二叉树题目将一棵有 5 个节点的树转换为二叉树 树的形态 A /|\ B C D | E 左孩子右兄弟转换 A / B \ C / D / E题2线索二叉树找前驱/后继在中序线索二叉树中找后继 如果 rtag 1 → right 就是后继 如果 rtag 0 → 右子树的最左节点 在中序线索二叉树中找前驱 如果 ltag 1 → left 就是前驱 如果 ltag 0 → 左子树的最右节点题3已知遍历序列构造二叉树已知某二叉树的先序序列为 ABDECFG 中序序列为 DBEAFCG 构造该二叉树并画出后序序列 解题步骤 1. 先序第一个 A 是根 2. 中序中 A 左边 DBE 是左子树右边 FCG 是右子树 3. 先序中 BDE 是左子树的先序从左到右 4. 递归继续...七、总结树的结构特点 每个节点可以有多个孩子没有限制 双亲表示法 → 找父节点快找孩子慢 孩子兄弟表示法 → 可以转换为二叉树 树与二叉树的转换 树的先根 → 二叉树的前序 树的后根 → 二叉树的中序408 重点树转二叉树左孩子右兄弟、线索二叉树的构造和遍历、森林与二叉树的互转。 觉得有用的话点赞 关注【张老师技术栈】吧每周更新 Java/Python/爬虫 实战干货不让你白来。