首页 > 二叉树遍历的超简单方法-

二叉树遍历的超简单方法-

发布时间：来源：文档文库

小中大

字号：

手机查看

二叉树的定义什么就不多废话了，但是有些定义还是得写出来的：
1．先序遍历的递归算法定义（简称根左右）若二叉树非空，则依次执行如下操作： (1遍历左子树； (2访问根结点； (3遍历右子树。
2．中序遍历的递归算法定义（简称左根右）若二叉树非空，则依次执行如下操作： (1 访问根结点； (2 遍历左子树； (3 遍历右子树。
3．后序遍历得递归算法定义（简称左右根）若二叉树非空，则依次执行如下操作： (1遍历左子树； (2遍历右子树； (3访问根结点。

现在以上面的二叉树为例子，说下三种遍历的方法先序遍历（简称根左右）：
1）从最上的第一层根结点F开始，按照根左右的原则，写出先序遍历顺序：FCE 2）继续对第二层进行分析，第二层有结点C和E。可以看见C、A、D和E、G可以组成两组小二叉树，那么现在对这两组小二叉树进行先序遍历，得出答案分别是CAD和EG。好了，现在把我们刚做出的答案CAD和EG代进去第一步做出的答案FCE里面，就得出答案：FC（AD）E（G）了
3）同理对第三层进行分析，D、B和G、H、P可以组成两组小二叉树，我们就对他们进行先序遍历，结果就是DB和GHP了。同样地，把这两个答案代进上一步的结果里面，答案就是FC（AD（B））E（G（HP））
4）把第三步答案里面的括号全部去掉，得出最终答案FCADBEGHP 中序遍历（简称左根右）：
1）从最上的第一层根结点F开始，按照左根右的原则，写出先序遍历顺序：CFE 2）继续对第二层进行分析，写出答案（A）C（D）FE（G）
3）对第三层进行分析，写出答案（A）C（（B）D）FE（（H）G（P）） 4）去掉括号，得出：ACBDFEHGP 后序遍历（简称左右根）：
1）从最上的第一层根结点F开始，按照左右根的原则，写出先序遍历顺序：CEF 2）继续对第二层进行分析，写出答案（AD）C（G）EF 3）对第三层进行分析，写出答案（A（B）D）C（（HP）G）EF 4）去掉括号，得出：ABDCHPGEF

本文来源：https://www.2haoxitong.net/k/doc/e5463e4203d8ce2f0166230a.html