k树的等级

Question

我需要制作一个函数来计算 k 树的等级。我是这样写的：

Rank (T)
if T.child=NIL
    return 0
else 
   return 1+ max{Rank(T.child), Rank(T.sibiling)}
end if

是否正确？ max函数计算树的左右节点数之间的最大值。

Answer 1

我对 K-trees 不熟悉，如果我说错了请指正。

如果我没理解错的话，秩是比你查找的根节点小的节点数。因此，您需要以这样一种方式平衡您的树，即子节点的所有后续树都小于本地根。

之后需要对树进行中序遍历。您访问的第一个节点应该是最小的节点，并且被赋予等级 0，下一个访问的节点应该被赋予等级 1 等等。

示例代码：

private int getRank(Node<E> n, E target, int rank) {
    if (n == null)
        return rank;
    rank = getRank(n.left, target, rank);   // smaller nodes
    if (n.e.equals(target))     // Solution to sought after node (target) 
        return rank;    
    System.out.println(n.e + " has rank " + rank);
    return getRank(n.right, target, rank + 1);  // larger nodes
}
public int getRank(E target) {
    if (root != null) {
        return getRank(root, target, 0);
    }
    return -1;
}



OUT:
3 has rank 0
4 has rank 1
5 has rank 2
7 has rank 3
9 has rank 4

如果树不平衡，另一种解决方案是访问所有节点并计算小于目标节点的节点。

示例：

private int getRank(Node<E> n, E target, int count) {
    if (n != null) {
        for (Node<E> c : getChildren(n)) {
            count += getRank(c, target, count);
        }
        if (n.e.compareTo(target) < 0) {
            count++;
        }
    }
    return count;
}

k树的等级

Rank of a k-tree

tree

pseudocode