如何根据节点的深度优先顺序索引计算完美二叉树中节点的级别？ [英] How can I calculate the level of a node in a perfect binary tree from its depth-first order index?

问题描述

我有一棵完美的二叉树，即树中的每个节点要么是一个叶节点，要么有两个子节点，而所有叶节点处于同一级别。每个节点都有一个深度优先的索引。

I have a perfect binary tree, i.e. each node in the tree is either a leaf node, or has two children, and all leaf nodes are on the same level. Each node has an index in depth-first order.

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

(E.g. in a tree with 3 levels the root node has index 0, the first child has 1, the first child of the first child has 2, the second child of the first child has 3, the second child has 4, the first child of the second child has 5, the second child of the second child has index 6.

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

）

我知道树（节点数/最大级别），但仅是特定节点的索引，我需要计算其级别（即，其与根节点的距离）。如何最有效地做到这一点？

I know the size of tree (number of nodes/maximum level), but only the index of a particular node, and I need to calculate its level (i.e. its distance to the rootnode). How do I do this most efficiently?

推荐答案

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

let i be the index you are looking for and n be the total number of nodes.

此算法可以完成您想要的操作：

This algorithm do what you want:

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 仅选择好子树。

0 is the index of the root, if i = 0 then you are at the good level, else you can remove the root and you obtain two subtrees n = (n-1)/2 updates the number of nodes is the new tree (which is a subtree of the old one) and i = i%n selects only the good subtree.

这篇关于如何根据节点的深度优先顺序索引计算完美二叉树中节点的级别？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！