深度优先遍历未知高度的二叉树

Question

我正在尝试实现一个算法（广度优先搜索或深度优先搜索），用来遍历一个二叉树，并从中提取数据。这个二叉树有两个方向：赢（WIN）或输（LOSE），而且它的深度是未知的（可能达到80-90层）。

我需要的是从根节点到叶子节点的所有路径，以及每个节点的内容。我想找到一种方法来追踪路径，不仅是当前的路径，还有所有可能的路径。而且因为每次到达叶子节点后，我们需要从根节点重新开始，所以我们需要一种方法来检查：

这条路径之前是否已经遍历过？（用队列或栈吗？？？）
它在哪里停止？这样我们就可以从那里继续（用标志来检查？？？）

树的结构：

所以我需要做的是找到从根节点A到叶子节点（V, Y, X, Q, Z, P, O, J, E, I, T, S, M）的所有可能路径。

所有可能的路径将是：

A -> C -> G -> L -> R -> V
A -> C -> G -> L -> R -> U -> Y
A -> C -> G -> L -> R -> U -> X
A -> C -> G -> L -> Q
A -> C -> G -> Z
A -> C -> F -> K -> P
A -> C -> F -> K -> O
A -> C -> F -> J
A -> B -> E
A -> B -> D -> I
A -> B -> D -> H -> N -> T
A -> B -> D -> H -> N -> S
A -> B -> D -> H -> M

每个节点都会有我需要提取的数据。

当我们到达叶子节点时，我们需要从头开始，但我们需要找到一种方法来跟踪我们已经遍历过的路径，这样就不必再走一遍，因为树的高度不仅仅是像这个例子中的7层，可能会达到80-100层。

#编辑 我想使用广度优先搜索而不是深度优先搜索的原因是，我想避免过早到达叶子节点，因为那样之后我需要从头开始。如果还没有到达叶子节点，那么获取尽可能多的数据来构建树会容易得多。

我仍在思考这个算法，但卡住了：

伪代码：

Create an empty tree
Create an empty queue to keep track of nodes that need to be processed.
Create an empty arrray of array (A) to save path. This array will be built up with each child     array is a possible path:
[ [WIN,WIN,WIN,WIN,WIN,LOSE,WIN,LOSE,LOSE,LOSE,LOSE],
  [WIN,WIN,WIN,WIN,WIN,LOSE,LOSE,LOSE,LOSE,LOSE,LOSE,LOSE,LOSE,LOSE,LOSE,LOSE,LOSE,],
.............................................................................................
  [LOSE,LOSE,LOSE,LOSE,WIN,LOSE]]
Create an empty arrray of array (B) to save flag. This array will have exact size with A but it will have 2 value 0 when we haven't visit that node, 1 when we visit it). So this array will change value from 0 to 1 when we visit node.
[ [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
  [1, 1, 1, 0, 0, 0, 0, 0, 0, 0,],
....................................................
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],

Add the starting point to the tree as the root node
Add the root node to a queue for processing

Repeat until the queue is empty (or finish):
  Remove a node from the queue 
  For child value WIN: 
    If the child hasn't already been processed: 
      Add it to the queue 
      Add it to array of array A
      Set 1 to array of array B
      Create an edge in the graph that connects the node and its neighbor

任何帮助都将不胜感激！非常感谢！

数据提取树结构算法设计深度优先搜索广度优先搜索二叉树节点遍历路径追踪

深度优先遍历未知高度的二叉树

1 个回答

撰写回答