7

我有一棵完美的二叉树，即树中的每个节点要么是叶节点，要么有两个孩子，并且所有叶节点都在同一级别。每个节点都有一个深度优先顺序的索引。

（例如，在具有 3 层的树中，根节点的索引为 0，第一个孩子有 1，第一个孩子的第一个孩子有 2，第一个孩子的第二个孩子有 3，第二个孩子有 4，第一个孩子第二个孩子的有 5，第二个孩子的第二个孩子有索引 6。

      0
    /   \
  1      4
 / \    / \
2   3  5   6

)

我知道树的大小（节点数/最大级别），但只知道特定节点的索引，我需要计算它的级别（即它到根节点的距离）。我怎样才能最有效地做到这一点？

4

7 回答 7

10

这是另一个建议，可以更轻松地解决这个问题：

如果以广度优先顺序使用索引标记节点，则无需在 O(1) 时间内进行任何遍历即可计算级别。因此，如果您正在执行多个查询，则可以执行 O(N) BFT 并在 O(1) 时间内回答每个查询。

等级公式为：

level = floor(log(index + 1))

日志以 2 为底

在这棵树上试一试：

       0
     /    \
    /      \
   1        2
  / \      / \
 /   \    /   \
3     4  5     6

干杯。

于 2015-06-30T20:04:35.083 回答
6

让i成为您要查找的索引并n成为节点总数。

这个算法做你想做的事：

level = 0
while i != 0 do
    i--
    n = (n-1)/2
    i = i%n
    level++
done

0 是根的索引，如果i = 0那么你处于良好的水平，否则你可以删除根并获得两个子树n = (n-1)/2更新节点的数量是新树（它是旧树的子树）并且i = i%n只选择好的子树。

于 2012-05-23T14:19:38.443 回答
3

似乎直接在树上行走应该足够高效。

在算法的每一步，请记住您所在节点的子树上的索引范围。范围的第一个值是根节点，之后的前半部分是左侧子树的范围，后半部分应该是右子树的范围。然后，您可以递归地向下移动，直到找到您的节点。

例如，让我们在具有 15 个元素的 4 级树中搜索

                 (root node)(left elements)(right elements)
Starting range:  (0)(1 2 3 4 5 6 7)(8 9 10 11 12 13 14)
Go left       :  (1)(2 3 4)(5 6 7)
Go right      :  (5)(6)(7)
Found node, total depth 2

您应该能够通过一个简单的循环来做到这一点，只使用几个变量来存储范围的开始和结束。如果您进行一些小的更改，例如使用 post/pre/in-order 遍历或从 1 而不是 0 开始索引，您也应该能够轻松地适应这一点。

于 2012-05-23T14:13:10.420 回答
2

未经测试：

int LevelFromIndex( int index, int count)
{
    if (index == 0)
        return 0;
    if (index > (count - 1)/ 2)
        index -= (count - 1) / 2;
    return 1 + LevelFromIndex( index - 1, (count - 1) / 2);
}

这count是树中的节点总数。

于 2012-05-23T14:17:20.340 回答
0

如果你只有索引，你就找不到深度。

假设你有一棵这样的树：

    1
   / \
  2   5
 / \
3   4

索引为 3 的节点的深度为 2。

假设你有一棵这样的树：

  1
 / \
2   3
   / \
  4   5

索引为 3 的节点的深度为 1。

你不能仅仅通过知道它们的索引来区分这两种树。仅通过知道索引就无法找到与根的距离。

编辑：如果你的意思是一个完美的二叉树，所有的叶子都在相同的深度，并且每个父母都有两个孩子，那么你仍然找不到深度。

比较这两棵树：

  1
 / \
2   3


      1
   /     \
  2       5
 / \     / \
3   4   6   7

节点 3 的深度根据树的高度而变化。

编辑2：如果你知道总树的高度，你可以使用这个递归算法：

def distanceFromRoot(index, rootIndex, treeHeight):
    if index == rootIndex:
        return 0
    leftIndex = rootIndex+1
    rightIndex = rootIndex + 2**treeHeight
    if index >= rightIndex:
        return 1 + distanceFromRoot(index, rightIndex, treeHeight-1)
    else:
        return 1 + distanceFromRoot(index, leftIndex, treeHeight-1)
于 2012-05-23T14:15:53.287 回答
0

编辑：尝试号 1... 仅适用于 BFS。

如果完美二叉树是指具有堆状结构的二叉树，则可以使用以下公式计算节点的父索引：

parentIndex = (index-1)/2

因此，您可以重复该公式，直到达到 <=0，每次循环时，您基本上都会在树中上升一个级别。

编辑：尝试编号 2..

我能想到的最好方法是采用 O(index + log n)，即 O(n)。执行 DFS 直到达到所需的索引，然后使用父指针继续向上树，直到到达根，跟踪你向上的次数。这假设每个节点上都存在一个父指针。

于 2012-05-23T14:09:47.640 回答
0

所以，我们有这样的树，有 4 个级别：

          0             - 0th level
      /       \         
     1          8       - 1th level
   /  \       /  \      
  2    5     9    12    - 2th level
 / \   /\   / \   / \
3   4 6  7 10 11 13 14  - 3th level

如您所见，每个左子节点的根索引都增加了一个（left = root + 1），因为在 DFS 中，左子节点总是首先访问。第二个节点的左节点索引增加了左子树的大小（右=左+左大小）。如果我们知道树的深度，我们可以计算它的大小（大小 = 2^depth - 1）。只要左子树的深度等于父级的深度减一，其大小 = 2^(parentDepth - 1) - 1。

所以现在我们有一个算法——计算左节点的索引，计算右节点的索引。如果节点索引位于它之间，则转到左侧节点，否则 - 转到右侧节点。

代码：

static int level(int index, int root, int treeDepth) {
        if (index == root)
            return 0;

        if (treeDepth <= 0 /* no tree */ || treeDepth == 1 /* tree contains only root */)
            throw new Exception("Unable to find node");

        int left = root + 1;
        int right = left + (int)Math.Pow(2, treeDepth - 1) - 1;

        if (index == left || index == right)
            return 1;

        if (left < index && index < right)
            return 1 + level(index, left, treeDepth - 1);
        else
            return 1 + level(index, right, treeDepth - 1);
    }
于 2012-05-23T14:41:45.423 回答