二叉树的遍历到底是怎么遍历的啊？

比如中序遍历什么先遍历左子树，在遍历根节点，在遍历右子树。。。。可是有的节点又可以是根又可以是别人的子树吧。。。。那我遍历那个节点的时候是把它当子树看还是根节点看呢。。。

happy_chllsg · 2018-4-30 01:55:57

遍历的目的就是按照某种顺序把非线性序列转换成线性序列。
中序遍历：左根右，是指二叉树非空时，第一步先中序遍历左子树，第二步访问根，第三步中序遍历右子树；如果二叉树为空，则返回。这是一个递归的思想，在中序遍历某棵二叉树过程中又用到中序遍历（遍历该二叉树根的左子树和右子树）。假设有一个包含A、B、C三个结点的二叉树，其中A是根结点，B是A的左孩子，C是A的右孩子。那么中序遍历过程为：第1次调用中序遍历，第一步中序遍历（根A的）左子树（只有一个根结点B）--即要调用中序遍历，此时第2次调用中序遍历，第一步中序遍历（根B的）左子树（空树）--由于是空树，所以返回，继续第2次调用终须遍历的第二步，也就是访问根结点B，然后是第三步，中序遍历（根B的）右子树（空树）--由于是空树，所以返回，此时要返回到第一次调用中序遍历的第二步，即访问根结点A，然后是第一次调用的第三步，中序遍历（根A的）右子树（只有一个根结点C）--即要调用中序遍历，此时第3次调用中序遍历，同理分析下去就可以了。呵呵

hl_zh · 2018-4-30 01:55:56

关键是要有递归的思想。
只要拥有左子树，就要先处理左子树，直到左子树为空。因此如果出现在根节点和子树间徘徊的情况，就是没有遍历到底。

leo003 · 2018-4-30 01:55:55

这个可以参考下我以前回答的
看完相信你会发现二叉树遍历很简单~
http://zhidao.baidu.com/question/89674628.html

二叉树的遍历到底是怎么遍历的啊？

3 个回复