44周游二叉树 ■周游系统地访问数据结构中的结点。 每个结点都正好被访问到一次。 周游一棵二叉树的过程实际上就是把 叉树的结点放入一个线性序列的过程, 或者说把二叉树进行线性化 北京大学信息学院 版权所有,转载或翻印必究 Page 26
北京大学信息学院 ©版权所有，转载或翻印必究 Page 26 4.4 周游二叉树 ◼ 周游 系统地访问数据结构中的结点。 每个结点都正好被访问到一次。 ◼ 周游一棵二叉树的过程实际上就是把二 叉树的结点放入一个线性序列的过程， 或者说把二叉树进行线性化
44周游二叉树 二叉树周游 44.1深度优先周游二叉树 442非递归深度优先周游二叉树 443广度优先周游二叉树 北京大学信息学院 版权所有,转载或翻印必究 Page 27
北京大学信息学院 ©版权所有，转载或翻印必究 Page 27 4.4 周游二叉树 ◼ 二叉树周游 ◼ 4.4.1 深度优先周游二叉树 ◼ 4.4.2 非递归深度优先周游二叉树 ◼ 4.4.3 广度优先周游二叉树
深度优先周游二叉树 我们变换一下根结点的周游顺序,可以得到 以下三种方案: ①前序周游(tLR次序):访问根结点;前 序周游左子树;前序周游右子树。 ②中序周游(tR次序):中序周游左子 树;访问根结点;中序周游右子树 ③后序周游(LRt次序):后序周游左子 树;后序周游右子树;访问根结点。 北京大学信息学院 版权所有,转载或翻印必究 Page 28
北京大学信息学院 ©版权所有，转载或翻印必究 Page 28 深度优先周游二叉树 我们变换一下根结点的周游顺序，可以得到 以下三种方案： ① 前序周游(tLR次序)：访问根结点；前 序周游左子树；前序周游右子树。 ② 中序周游(LtR次序)：中序周游左子 树；访问根结点；中序周游右子树。 ③ 后序周游(LRt次序)：后序周游左子 树；后序周游右子树；访问根结点
深度优先周游二叉树 深度周游如下二叉树 B E F D GO OH IO 北京大学信息学院 版权所有,转载或翻印必究 Page 29
北京大学信息学院 ©版权所有，转载或翻印必究 Page 29 深度优先周游二叉树 ◼ 深度周游如下二叉树
深度优先周游二叉树 深度周游二叉树结果 ①前序周游: ABDCEGFHI ②中序周游: DBAEGCHFT ③后序周游: DBGEHIFCA 北京大学信息学院 版权所有,转载或翻印必究 Page 30
北京大学信息学院 ©版权所有，转载或翻印必究 Page 30 深度优先周游二叉树 ◼ 深度周游二叉树结果 ◼ ① 前序周游：ABDCEGFHI ◼ ② 中序周游：DBAEGCHFI ◼ ③ 后序周游：DBGEHIFCA