时间戳

首页 > 解决方案 > 二叉树节点位置和帮助字典

python - 二叉树节点位置和帮助字典

问题描述

谢谢你的帮助

背景

我有一个关于在树中定位节点的问题。

我有一个简单的二叉树。每个节点中都有一条数据。假设它看起来像这样：

  a
 / \
b   c

哪里a=root, b=root.left,c=root.right

树不是手动创建的。假设我收到添加new_data到节点 c 的请求。

我很困惑如何知道 c 在哪里而不显式编写root.right.data=new_data.

我的第一个想法是创建某种类型的辅助字典，并引用节点位置，例如：

helper = {
    'a'= root,
    'b'= root.left,
    'c'= root.right
}

这样当我收到请求时，我可以去找助手并说一些大意的东西：

helper.get('c').data=new_data

问题

我在正确的球场吗？递归地反复搜索整棵树似乎有点多 - 当树改变其节点结构时，这个助手可能会偶尔更新。

当我递归爬取树时，我对如何实际返回每个节点的位置感到困惑。我怎样才能创建这个助手？

标签： pythonrecursionbinary-treebinary-search-tree

解决方案

回答

答案是递归搜索。我对助手 dict 的想法源于我对 BST 的不熟悉。我将以下内容添加到我的节点以搜索树的预排序：

def find_node(self, start, id):
    if start:
        if start.id == id:
            return start
        else:
            node = self.find_node(start.left, id)
            if node:
                return node
            else:
                node = self.find_node(start.right, id)
                if node:
                    return node
    else:
        return None

该视频对帮助我了解 BST 非常有帮助。我意识到，当我找到正确的id.

推荐阅读