遍历二叉搜索树的元素

Question

我有一个二进制搜索树，它的节点存储在python字典中。下面是一个例子：

BST = {'node1': ['Fail', 'node3'], 'node3': ['Fail', 'Pass'], 'node2': ['Fail', 'node1'], 'node4': ['Fail', 'node2']}

在字典中，每个键都是来自BST的父项，而列表（key的值）是该父项的子项，而对应的键来自dictionary。在

例如：

^{pr2}$

在本例中，'node1'是子项{}的父项。列表的第一个元素，'Fail'是'node1'的左子元素，'node3'是{}的右子元素。在

左子项与其父项之间的边的值为“是”，右子项与其父项之间的边的值为“否”。在

Fail和Pass值是BST的叶子

一个观察，为了能够找到根；只需选择一个节点并检查它是否有父节点。如果不是，那就是树根。否则，请检查该节点的父节点。在

下面是字典对应的树：

我认为这棵树的构造是清楚的。现在关于我的问题，我需要以FAIL节点作为其最终节点并从yes边开始的格式来查找路径。如果第一个节点没有“是”边，只需消除它并查找下一个节点，直到找到“是”边是该路径的起点。在

示例：

在此BST中，有效路径应为：

[[node4,yes], [node1, yes], [node3, yes], FAIL]
[[node4,yes], [node1, no], FAIL]]
[[node2,yes], FAIL]
[[node1,yes], FAIL]
[[node3,yes], FAIL]

注意：如果找到了路径，则无需查看其子路径。例如，这是无效的，因为有较长的路径覆盖此路径：

[[node4,yes], [node3, yes], FAIL].

即：

[[node4,yes], [node1, yes], [node3, yes], FAIL]

Answer 1

用Dictionaries实现树是很难看的， 而是使用下面提到的自引用结构class Node

class Node:
    """Referential Structure used to create new nodes"""
    def __init__(self, data):
        """Constructor."""
        self.data = data
        self.left = None
        self.right = None

这将使你的穿越更容易

请参考：https://github.com/SivaCn/Small-Codes/blob/master/Python/BinarySearchTree.py