t**g
发帖数: 1164 | 1 前面某位仁兄给出的
给定一棵树, 每个节点有任意个子节点, 怎样得到深度, 给出递归和非递归两种解
我知道递归算法
可是不知道如何写非递归？ |
f*******e
发帖数: 1161 | 2 非递归不就是堆栈么？
【在 t**g 的大作中提到】
: 前面某位仁兄给出的
: 给定一棵树, 每个节点有任意个子节点, 怎样得到深度, 给出递归和非递归两种解
: 我知道递归算法
: 可是不知道如何写非递归？
|
d*******d
发帖数: 2050 | 3 bfs
【在 t**g 的大作中提到】
: 前面某位仁兄给出的
: 给定一棵树, 每个节点有任意个子节点, 怎样得到深度, 给出递归和非递归两种解
: 我知道递归算法
: 可是不知道如何写非递归？
|
x******3
发帖数: 245 | 4 同意，类似于逐层打印， 用一个FIFO queue
【在 d*******d 的大作中提到】
: bfs
|
m*****g
发帖数: 226 | 5 non recursive
未必一定bfs
也可以用stack 作遍历 |
t**g
发帖数: 1164 | 6 能给具体代码么
我觉得DFS可行
可是“每个节点可以有任意子节点”
感觉写遍历代码的时候有点麻烦
如何知道某个节点已经没有更多字接点了呢？
【在 f*******e 的大作中提到】
: 非递归不就是堆栈么？
|
s*********t
发帖数: 1663 | 7 每访问一个节点就标记，并且把他的子节点全部加入队列
然后对队列里每个元素做同样的事情
【在 t**g 的大作中提到】
: 能给具体代码么
: 我觉得DFS可行
: 可是“每个节点可以有任意子节点”
: 感觉写遍历代码的时候有点麻烦
: 如何知道某个节点已经没有更多字接点了呢？
|
f*******e
发帖数: 1161 | 8 dfs每次入栈所有子节点吧？
是否有子节点取决于你如何定义数据结构？
【在 t**g 的大作中提到】
: 能给具体代码么
: 我觉得DFS可行
: 可是“每个节点可以有任意子节点”
: 感觉写遍历代码的时候有点麻烦
: 如何知道某个节点已经没有更多字接点了呢？
|
t**g
发帖数: 1164 | 9 BFS才是每次入栈所有子节点吧？
【在 f*******e 的大作中提到】
: dfs每次入栈所有子节点吧？
: 是否有子节点取决于你如何定义数据结构？
|
f*******e
发帖数: 1161 | 10 bfs是队列，dfs是栈；FIFO, LIFO
就这么个区别
【在 t**g 的大作中提到】
: BFS才是每次入栈所有子节点吧？
|
K******g
发帖数: 1870 | 11 请问谁能给个详细点的步骤，非递归的求一棵树的深度？多谢 |
