代码之家 › 专栏 › 技术社区 › InverseFalcon

遍历并插入到一个奇怪的二叉树中

traversal binary-tree algorithm

InverseFalcon · 技术社区 · 14 年前

好吧,我碰到了这个看起来很简单的树问题,但开始让我发疯。

给定的树类似于二进制搜索树,但有一个区别:

对于节点,leftnode.value<value<=rightnode.value。然而,(由于他们遗漏了任何进一步的信息,以及下面的例子),这只适用于直接子节点,而不是每个子节点下面的节点。因此,有可能在左子树的某个位置有一个值,>=当前节点的值。

这不是自平衡树;除了在新叶节点中添加新值外,插入时不会更改现有的树结构。不允许值或节点的切换或移位。

还给出了插入测试值后的树结构示例:

If we insert 8, 5, 9, 3, 3, 2, 12, 4, 10:


   8


   8
  5  


   8
  5 9


   8
  5 9
 3


   8
  5 9
 3
  3


   8
  5 9
 3   
2 3


   8
  5 9
 3   12
2 3


   8
  5 9
 3   12
2 3
   4


    8
  5   9
 3  10 12
2 3
   4

我假设10是5的右孩子,因为给定的约束条件阻止它成为9的左孩子。

我的要求,给出了上述节点规则和给定输入的预期树结构和行为示例:为此树编写遍历和插入算法。

因为这不是一个真正的BST,我们不允许更改树,所以除了使用另一个数据结构来按顺序进行遍历之外,我想不出任何聪明的方法来执行遍历。

我有一个插入算法,它可能会工作,但因为它必须允许备份到父节点和探索另一条路径(在这两种情况下,它都开始向左或右移动),这将是一个非常奇怪的算法。

这个问题和普通的基本编程问题放在一起,所以看起来有点不合适。那么……这里有什么见解吗?还是我忽略了一些明显的东西?

编辑: 问题解决了。这是测试者介绍的一个打字错误。这本来是一个BST,但示例中的“10”被放在错误的位置;它应该是“12”的左子代。

2 回复 | 直到 13 年前

Henk Holterman 14 年前

在10出现之前,示例是有意义的。基本假设:这是一个打字错误。但它不能(也不想)成为5岁的孩子。它是9岁的左孩子。

但这也是第一个需要重组这棵树(以适应9到12之间的情况)。在我看来,最后一幅图是这样一次重组的一半。我们看到故事的结局了吗?

编辑

好吧,我没有完全读完规则2。看起来10岁的孩子应该是12岁的左撇子。没有充分的理由让insert在根处采用左分支。

如果10是5或9的子级,它就不再是BST或其他任何东西,而是无序的二叉树。

John Kugelman Michael Hodel 14 年前

编辑

再想一想,我更倾向于相信你的例子中有一个错别字,而不是这不是一个BST。 10 没有道理。在此之前,它是一个完全有效的bst。如果10作为 12 而不是节点,则将保留BST ness。

如果 leftNode.value < value <= rightNode.value 只适用于直接子代,而不是所有子代,那么这是一个无用的数据结构。我的意思是,我想它是可用的,但是由于您最终会在插入和查找中遍历整个树,所以它似乎是毫无意义的。

我认为插入算法的大纲将类似于下面的伪Python。它的要点是尽可能将节点添加为叶子,或者将其插入到任意一个子树中。不管是左边还是右边,都没关系。

基本上,我们只是在整棵树上寻找任何可以作为叶节点添加新值的地方。正如您所说,排序标准只适用于直系子女。您必须对添加新的叶节点很挑剔。但是你会不加选择地尝试左、右两个子树。

class TreeNode:
    def insert(self, value):
        # Can we add it as the left leaf of this node?
        if self.left is None and value < self.value:
            self.left = TreeNode(value)
            return True

        # Can we add it as the right leaf of this node?
        if self.right is None and value >= self.value:
            self.right = TreeNode(value)
            return True

        # Can we add it somewhere down the left sub-tree?
        if self.left.insert(value):
            return True

        # Can we add it somewhere down the right sub-tree?
        if self.right.insert(value):
            return True

        # Didn't find anywhere to add the node.
        return False

我猜这变得棘手的地方是,如果你必须尝试平衡子树,而不是随意地在树的任意点插入新节点。如果这是一个问题,那么您可以修改上述算法,将其插入尽可能最浅的点。

假装有一个 insert_depth 返回节点插入深度的方法如果它被插入到特定的子树中,如果无法插入,则返回∞。同样,这只是伪代码:

left_depth  = self.left .insert_depth(value)
right_depth = self.right.insert_depth(value)

if left_depth < right_depth:
    return self.left .insert(value)
else:
    return self.right.insert(value)

在真正的代码中,我会写一个“如果你要插入一个节点,你会在哪里插入它?”辅助方法。在两个子树上运行该方法,比较插入点,然后选择一个(即最浅的)。代码可能有点笨拙,但它可以避免您两次遍历每个子树。