关于二叉树的递归遍历还是不理解 那位高手能不能详细讲一下!!!

2024-11-27 11:05:16
推荐回答(2个)
回答(1):

主要有三种遍历方法,先序遍历,中序遍历,后序遍历。
先序遍历:就是先访问根节点,再访问其左子树。最后访问右子树。
A
/ \
B C
/ \ / \
D E F G
对于遍历来说无论是哪种遍历,采取的思路是遍历左子树和右子树的时候,把左子树和右子树当成一棵新的完整的二叉树来对待,按照指定的遍历方法进行遍历,就比较容易理解了。
例如:先序遍历
1、首先访问根节点A,然后接下来要去访问它的左子树
2、将它的左子树当成一棵完整的二叉树:
B
/ \

D E
这个你要采用先序来进行遍历的话,还是先遍历根节点,然后左子树,然后右子树。那么这个时候必定要先访问根节点B了。
3、再将B的左子树当成一棵新的二叉树:
D
由于其没有子树了,就只有一个根节点。所以这个时候就访问这个根节点D
4、同样的道理再去访问B的右子树E。
5、到这个地方,对于根节点A的左子树才完整遍历了。
6、同样的道理接着去访问A的右子树,还是将它的右子树当成一个新的二叉树,进行遍历。遍历结果是CFG。
7、最终的遍历结果就是ABDECFG。
/* 我的理解是递归A->B->D,然后就回到A了,怎么到了B就停了 去访问E,就是这点我不理解 ,请你帮我理一下思路,到底是怎么回事啊???*/
你的理解只是单纯的理解为访问左子树的时候,只是左边的是它的左子树,其实在访问的时候只要是处在A左边的全部都是它的左子树。。。
希望我的回答对你有所帮助。。。。。

回答(2):

主要有三种遍历方法,先序遍历,中序遍历,后序遍历。
先序遍历:就是先访问根节点,再访问其左子树。最后访问右子树。
A
/ \
B C
/ \ / \ B
D E F G / \
例如:先访问A,再访问其左子树 D E ,那么,对于这个树,先访问其根节点B,再访问其左子树D。D没有左右子树。于是访问B的右子树E。E没有子树。返回A,访问A的右子树。即:C 与其左子树F和右子树G。最后得出遍历序列是:ABDECFG。
中序遍历:就是先访问左子树,再访问其根节点。最后访问右子树。
遍历方法如上:最后遍历序列:DBEAFCG
后序遍历:先访问左子树,再访问其右子树。最后访问根节点。
同样方法:遍历序列:DEBFGCA