二叉树遍历实验报告，二叉树实验的心得体会

这篇文章给大家聊聊关于二叉树遍历实验报告，以及二叉树实验的心得体会对应的知识点，希望对各位有所帮助，不要忘了收藏本站哦。

二叉树遍历例题

假设某二叉树的先序遍历序列是abdgcefh，中序遍历序列是dgbaechf，画出二叉树，并给出其后序遍历序列。分析过程：

以下面的例题为例进行讲解：

已知一棵二叉树的先序遍历序列和中序遍历序列分别是abdgcefh、dgbaechf，求二叉树及后序遍历序列。

分析：先序遍历序列的第一个字符为根结点。对于中序遍历，根结点在中序遍历序列的中间，左边部分是根结点的左子树的中序遍历序列，右边部分是根结点的右子树的中序遍历序列。先序：abdgcefh-->abdgcefh

中序：dgbaechf-->dgbaechf

得出结论：a是树根，a有左子树和右子树，左子树有bdg结点，右子树有cefh结点。先序：bdg-->bdg

中序：dgb-->dgb

得出结论：b是左子树的根结点，b无右子树，有左子树。先序：dg-->dg

中序：dg-->dg

得出结论：d是b的左子树的根结点，d无左子树，有右子树。先序：cefh-->cefh

中序：echf-->echf

得出结论：c是右子树的根结点，c有左子树(只有e结点)，有右子树(有fh结点)。先序：fh-->fh

中序：hf-->hf

得出结论：f是c的左子树的根结点，f有左子树(只有h结点)，无右子树。还原二叉树为：

a

bc

def

gh后序遍历序列：gdbehfca

前序遍历是什么

这个是二叉树里面的一种遍历情况，前序遍历也叫做先根遍历，可记做根左右。

前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。

一棵二叉树的中序遍历序列为：DGBAECHF，后序遍历序列为：GDBEHFCA，则前序列遍历序列是

不知道你理解前，中，后序遍历的概念没？

前序遍历又叫先根遍历，就是先访问根再访问左子树再访问右子树。

中序就是先访问左子树再访问根再是右子树。

后根就是先访问左子树然后是右子树最后是根。

简单的讲就是，你看后序遍历序列为：GDBEHFCA，最后一个是A，说明A是根。然后再去看中序遍历序列为：DGBAECHF，看到A在中间，把DGBAECHF分成DGB和ECHF两部分，好，现在单独看这两个子树，左子树DGB和右子树ECHF。

同样后序遍历序列GDBEHFCA中，找到DGB这三个字母，发现它是这样排列的，GDB，因为它是后跟遍历，所以子树DGB的根是B，这时候，你通过观察中序的DGB和后序的GDB，发现中序的右边没有东西，所以得出：子树GDB没有右支。同样的道理，发现子树ECHF的根是C，左子树只有E，右子树是HF。

像这样一步步分析

那么结论就是前序遍历是ABDGCEFH。

你最好能画个图就好理解多了。

图给你画了，有点丑，凑合看吧，呵呵。

如果二叉树有1亿个节点，递归遍历算法会不会漏掉一两个图呢

谢谢邀请！

二叉树的递归遍历算法已经属于比较成熟的算法。1亿个节点的遍历，主要是涉及效率和时间的问题。一亿个节点的遍历，对计算机来说，并不是什么辛苦的事情。

正常来说，不会漏掉任何一个节点。除非是编程的bug。如果真的出现这种漏掉问题，基本都是编程的问题。

图的遍历？按你提问的逻辑，应该是多叉树吧？

多叉树的遍历也是一样的情况，算法没有问题，多半是编程的问题。但针对图的遍历算法，递归未必是最好的算法。根据多叉树节点的搜查要求和节点存储规则，可以优化遍历算法。

我曾经带过一个项目，处理2.3亿个节点，也是很轻松的事。关键是我们在测试时，用测试案例，把全部节点遍历一遍的统计个数和节点实际个数核算，经过一周的严格测试，项目的这个功能才能通过。

二叉树先序，中序，后序遍历顺序

任何一颗二叉树的叶子结点在先序、中序、后序遍历序列中的相对次序是不发生改变的，解释如下：因为根据三个遍历的次序和特点：前序是根左右、中序是左根右、后序是左右根,因此相对次序发生变化的都是子树的根,也就是分支结点。例如：对于一个满3层二叉树，按每层从左到右按除0自然数编号（第一层，1；第二层，2,3；第三层，4,5,6,7），然后先序遍历是1245367，对编号1的根节点来说245是左分支的，367是右分支；而对于2来说，4是左边，5是右边；对于3,6在左边，7在右边，所以先序遍历是根左右，同理中序是左根右，后序是左右根，先序，中序，后序，都是先左后右。

为什么树的后根遍历就是对应二叉树的中序遍历

一棵树的后根遍历与这棵树所对应的二叉树的中序遍历相同。

当对一棵数学表达式树进行中序，前序和后序遍历时，就分别得到表达式的中缀、前缀和后缀形式。中缀（infix）形式即平时所书写的数学表达式形式，在这种形式中，每个二元操作符（也就是有两个操作数的操作符）出现在左操作数之后，右操作数之前。

一棵二叉树的先序遍历

1、先序遍历第一个为树的根，先序遍历是先根再左子树最后右子树，第一个肯定是树的根，先画A，A再中序遍历中左右都有，说明A有左子树也有右子树。

2、然后看先序第一个值是B，在中序中为A的前面，所以B是A的左子树

3、继续看先序，接下来是C、D，C再中序中再B的前面，所以C是B的左子树，D在B后面，D是B的

4、接下来是E，E在中序是在D后面A前面，所以E是D的右子树

5、接着先序中是F，F在中序为A后面，是A的右子树

文章到此结束，如果本次分享的二叉树遍历实验报告和二叉树实验的心得体会的问题解决了您的问题，那么我们由衷的感到高兴！