[已解决]一个后续遍历的问题

xqq1984 · 发表于 2020-2-4 18:05:51

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

class TreeNode():
def __init__(self,val,left = None,right = None):
self.val = val
self.left = left
self.right = right
F = TreeNode('F')
G = TreeNode('G')
C = TreeNode('C')
D = TreeNode('D',F,G)
E = TreeNode('E')
A = TreeNode('A',C,D)
B = TreeNode('B',right=E)
Root = TreeNode('Root',A,B)
def preoderTraversal(node):
if node == None:
return None
if node.left != None:
preoderTraversal(node.left)
if node.right != None:
preoderTraversal(node.right)
print (node.val)
a = preoderTraversal(Root)

复制代码

运行结果时对的,但是我不明白第一次函数打印到数,print在函数的最后一行,然后是怎么重复执行的,求大佬们指点

最佳答案

月排行榜 / 总排行榜

阴阳神万物主

2020-2-4 21:22:22

综合看了下，发现你的主要问题是：在打印完树的末梢节点之后是如何去到另一个末梢的
其实吧，用一个流行词就能解释：套娃
但是呢，并不是一个套一个的基础款，而是有一个套俩的可能存在。
在套娃的同一层有复数个存在的话，是一个一个去开的，如果开了一个，里面还有，就进入下一层，否则就继续开同一层的，当没有剩下可开的套娃时，就回到上一层，继续开上一层的其他套娃。

跳转到最佳答案楼层

ll104567 · 发表于 2020-2-4 18:37:48

本帖最后由 ll104567 于 2020-2-4 18:39 编辑

首先函数用的是递归的方式，要先明白递归是什么意思。
也就是函数自己调用自己这种情况。
这里我用目录结构来展示你给的那个层级

root@lp:~/lp/python/data# tree root
root
├── A
│ ├── C
│ └── D
│ ├── F
│ └── G
└── B
└── E

复制代码

Root就是根啦，
因为函数里先判断的是left
所以我们就先看A那一个目录结构，也就是一路向左，找到的就是C，这个时候到头了
因为C没有下一个节点了，所以Return None，调用结束。
这里还有一个递归的时候函数栈的东西
我们先说后边的，
因为右边D还有下一个路径，所以D下一个是F（先左后右）
F也到头了，所以这里第二个打印F
同理下一个是G
到此为止
A这个所有节点都记经ok
所以类似于从历史记录里往出调，就是刚才所谓的函数栈。
所以从FG这里返回上一个节点，
所以接下来打印
D
接下来继续往上打印A
这里所有左侧遍历结束，开始用同样道理考虑右侧
所以会打印
E
B
最后所有都结束打印根Root

整体解释了一遍，为什么会这样。1.递归遍历 2.先判断左侧，后判断右侧
你大可以把那个判断顺序改一下，再去思考

xqq1984 · 发表于 2020-2-4 18:48:40

因为C没有下一个节点了，所以Return None，调用结束。

C没有节点了,不是应该先打印C的值吗,其实我就想问打印完C是怎么再去判断其他的,因为并没有循环指令

Stubborn · 发表于 2020-2-4 18:53:59

xqq1984 发表于 2020-2-4 18:48
C没有节点了,不是应该先打印C的值吗,其实我就想问打印完C是怎么再去判断其他的,因为并没有循环指令

有递归调用呀~

上个问题不就回答过了吗~需要理解下递归的过程，自己画一个函数的运行步骤出来，就会理解

xqq1984 · 发表于 2020-2-4 19:26:29

Stubborn 发表于 2020-2-4 18:53
有递归调用呀~上个问题不就回答过了吗~需要理解下递归的过程，自己画一个函数的运行步骤出来 ...

大神解释下啊,我画图了,打印出最下面的怎么返会上一个节点还是没搞明白

Stubborn · 发表于 2020-2-4 19:34:00

xqq1984 发表于 2020-2-4 19:26
大神解释下啊,我画图了,打印出最下面的怎么返会上一个节点还是没搞明白

你告诉我顶点的Root节点，丢到函数里面，什么时候才会运行到print(node.val)

ll104567 · 发表于 2020-2-4 19:52:03

xqq1984 发表于 2020-2-4 18:48
C没有节点了,不是应该先打印C的值吗,其实我就想问打印完C是怎么再去判断其他的,因为并没有循环指令

看你是怎么理解递归的吧。
我对于他的理解是这样的。

首先从头开始一直先找到结尾，因为会涉及很多分支，
所以最后一定是最后找到了所有的分支的末尾，然后继续从末尾一级一级的往回走
就比如找到C以后，在最左侧已经全部找完了，但是你要知道C和D是在同一个维度开始的，
在C那个分支找以后，D同时就开始分支，
C很快结束所以返回C

D又有子分支所以会继续向下找，直到到头，然后再依次向回一段段回溯。

xqq1984 · 发表于 2020-2-4 19:52:23

Stubborn 发表于 2020-2-4 19:34
你告诉我顶点的Root节点，丢到函数里面，什么时候才会运行到print(node.val)

参数Root存在,跳到Root.left(即A)存在,跳到A.left(即C)存在,再跳C.left和C.right都不存在,打印C的值.下面就不知道怎么执行了?求指点

Stubborn · 发表于 2020-2-4 20:01:27

xqq1984 发表于 2020-2-4 19:52
参数Root存在,跳到Root.left(即A)存在,跳到A.left(即C)存在,再跳C.left和C.right都不存在,打印C的值.下面 ...

打印完C，即这个函数生命结束，上一个跳转到C的函数呢？生命周期结束了吗？

ll104567 · 发表于 2020-2-4 20:05:39

9楼说的很对阿，
我先问个问题，先不考虑你这二叉树

这个能看懂么，能的话你自己先解释解释

In [43]: def fib(n):
...: if n <= 1 :
...: return 1
...: return fib(n-1) + fib(n-2)
...:
In [44]: fib(10)
Out[44]: 89

复制代码

ll104567 · 发表于 2020-2-4 20:11:09

我在求fib（10）的时候，是不知道fib（9）和fib（8）的，所以在内存里只能先存着。
一直计算到最后一步的时候，才会知道fib（1）和fib（0）是1 ，然后再一步一步回去，
也就是重新累加。

这不是一个正常的循环
所以你可以看看

In [53]: def fib(n):
...: if n <= 1 :
...: return 1
...: print(n)
...: return fib(n-1) + fib(n-2)
...:
In [54]: fib(5)
5
4
3
2
2
3
2
Out[54]: 8
In [55]: fib(6)
6
5
4
3
2
2
3
2
4
3
2
2
Out[55]: 13

复制代码

xqq1984 · 发表于 2020-2-4 20:22:53

ll104567 发表于 2020-2-4 20:05
9楼说的很对阿，
我先问个问题，先不考虑你这二叉树

实现什么功能说不上来,就是不停的fib(n-1)+fib(n-2),直到所有的n-1或n-2<=1时返回1,再把这些数相加

ll104567 · 发表于 2020-2-4 20:44:09

xqq1984 发表于 2020-2-4 20:22
实现什么功能说不上来,就是不停的fib(n-1)+fib(n-2),直到所有的n-1或n-2

那你找张纸一步一步画一画这个遍历的过程，结合我楼上的话好好想想那个例子，你在这一个劲问没有用。

阴阳神万物主 · 发表于 2020-2-4 21:22:22

综合看了下，发现你的主要问题是：在打印完树的末梢节点之后是如何去到另一个末梢的
其实吧，用一个流行词就能解释：套娃
但是呢，并不是一个套一个的基础款，而是有一个套俩的可能存在。
在套娃的同一层有复数个存在的话，是一个一个去开的，如果开了一个，里面还有，就进入下一层，否则就继续开同一层的，当没有剩下可开的套娃时，就回到上一层，继续开上一层的其他套娃。

账号		自动登录	找回密码
密码			立即注册