2

我有一个二叉搜索树，其节点存储在 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'。

左孩子与其父母之间的边值为“是”，右孩子与其父母之间的边缘值为“否”。

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]
4

1 回答 1

1

很难看，用 实现 Tree ，而不是使用下面提到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

于 2013-11-07T17:08:03.393 回答