首页 文章

遍历BST的元素

提问于
浏览 次
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的叶子 .

一个观察，能够找到根;只需选择一个节点并检查是否有父节点 . 如果没有，它就是树的根 . 否则，请与该节点的父节点检查相同的内容 .

这是与字典对应的树：

tree with the dictionary

我认为树的结构很清楚 . 现在关于我的问题，我需要找到以 FAIL 节点作为其最终节点并以yes边缘开头的格式的路径 . 如果第一个节点没有“是”边缘，则将其消除并查找下一个节点，直到找到“是”边缘为该路径的起点 .

说明性示例：

example tree

在此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]
python python-2.7 binary-search-tree

1 回答

  • 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

    回复于

相关问题