python之遍历BST的元素_编程设计

我有一个二叉搜索树，其节点存储在 Python 字典中。这是一个例子:

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

在字典中，每个键都是来自 BST 的父项，列表(键的值)是该父项与字典中相应键的子项。

例如:

BST['node1'] =  ['Fail', 'node3']

在这种情况下，'node1' 是子级 ['Fail', node3] 的父级。列表的第一个元素 'Fail' 是 'node1' 和该列表的另一个元素 'node3' 的左子元素是 'node1' 的右 child 。

左 child 与其 parent 之间的边值为"is"，右 child 与其 parent 之间的边值为“否”。

Fail 和 Pass 值是 BST 的叶子。

一次观察，才能找到根源；只需选择一个节点并检查它是否有父节点。如果不是，它就是树的根。否则检查与该节点的父节点相同的事情。

这是字典对应的树:

我认为树的构造很清楚。现在关于我的问题，我需要以 FAIL 节点作为其最终节点并以是边缘开始的格式找到路径。如果第一个节点不具有是边，则将其消除并寻找下一个节点，直到发现是边是该路径的起点。

示例:

在此 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]

请您参考如下方法:

用 Dictionaries 实现 Tree 很丑陋，而是使用下面提到的自引用结构 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