“树的遍历”的版本间的差异

2022年9月19日 (一) 05:52的版本

前序/先序遍历：先遍历根结点，然后遍历左子树，最后遍历右子树。根、左、右

中序遍历：先遍历左子树，然后遍历根结点，最后遍历右子树。左、根、右

后序遍历：先遍历左子树，然后遍历右子树，最后遍历根结点。左、右、根

层序遍历：从上往下逐层遍历。上到下、左到右

图中前序遍历结果是？

1、2、4、5、7、8、3、6

图中中序遍历结果是？

4、2、7、8、5、1、3、6

图中后序遍历结果是？

4、8、7、5、2、6、3、1

图中层序遍历结果是？

1、2、3、4、5、6、7、8

由前序序列为ABHFDECG；中序序列为HBEDFAGC构造二叉树；

前序序列是根、左、右的顺序，已知“前序序列为A......”，得知这个二叉树的根结点是A；

中序序列是左、根、右的顺序，已知“中序序列为HBEDFAGC”，得知A前面的结点（HBEDF）都在以A为根节点的树的左子树中，A后面的结点（GC）都在以A为根节点的树的右子树中，则有：

@@ 第25行： / 第25行： @@
 、2、3、4、5、6、7、8
+=== 2）由前序、中序遍历序列构造二叉树 ===
+由前序序列为ABHFDECG；中序序列为HBEDFAGC构造二叉树；
+前序序列是根、左、右的顺序，已知“前序序列为A......”，得知这个二叉树的根结点是A；
+中序序列是左、根、右的顺序，已知“中序序列为HBEDFAGC”，得知A前面的结点（HBEDF）都在以A为根节点的树的左子树中，A后面的结点（GC）都在以A为根节点的树的右子树中，则有：
+[[文件:构造二叉树1.png|无|缩略图|300x300像素]]