在 Python 中查找二叉树的路径

Question

假设我有一个矩阵，其中反向（重组）下三角是一个二叉树，初始节点的值为 4（左下角），分支到 3 和 5，其中 3 个分支到 2 和 4，还有 5 个分支到 4 和 6，依此类推。

m = ((0, 0, 6),
     (0, 5, 4),
     (4, 3, 2))

这是视觉表示：

我怎样才能找到这棵树中的所有唯一路径作为元组？自然地，对于具有 $n$ 个步骤的树（即 $n+1$ 个终端节点），将有 $2^n$ 条路径。

[(4,3,2), (4,3,4), (4,5,4), (4,5,6)]

Answer 1

您可以： - 对树进行一些遍历，例如 BFS 或 DFS。
最简单的方法是递归

procedure Walk(node, route)
  if node = nil then //leaf node is reached
     output(route)
  else   
    Walk(node.left, route + node.name)
    Walk(node.right, route + node.name)

Walk(root, empty)

- 映射 0..2ⁿ-1 范围内的数字和可能的路线：
如果数字的第 i 位（从左起）为 1，则在第 i 层使用右分支，否则使用左分支。例如，(4,5,4) 对应数字 2 = 二进制 10

在 Python 中查找二叉树的路径

Find paths of binomial tree in Python

python

algorithm

tree

data-structures

python-3.x