二叉树遍历的超简单方法

《二叉树遍历的超简单方法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

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

3、历，结果就是DB和GHP了。同样地，把这两个答案代进上一步的结果里面，答案就是FC（AD（B））E（G（HP））4）把第三步答案里面的括号全部去掉，得出最终答案FCADBEGHP 中序遍历（简称左根右）：1）从最上的第一层根结点F开始，按照左根右的原则，写出先序遍历顺序：CFE2）继续对第二层进行分析，写出答案（A）C（D）FE（G）3）对第三层进行分析，写出答案（A）C（（B）D）FE（（H）G（P））4）去掉括号，得出：ACBDFEHGP 后序遍历（简称左右根）：1）从最上的第一层根结点F开

4、始，按照左右根的原则，写出先序遍历顺序：CEF2）继续对第二层进行分析，写出答案（AD）C（G）EF3）对第三层进行分析，写出答案（A（B）D）C（（HP）G）EF4）去掉括号，得出：ABDCHPGEF