0

我已经rankOfElement(x)用伪代码实现了一个方法，它返回给定节点 x 的排名：

function rankofElement(x) {
    rank = 0; 
    Node temp = root;

    while (temp.key != x) {
       if (x < temp.key) {
          temp = temp.leftson
       } else if (x > temp.key) {
          rank += temp.leftson.size + 1;
          temp = temp.rightson;
       } else if (temp.key == x) {
          return rank + temp.leftson.size
       } else return "key not found"
   }

现在我应该elementbyRank(k)用伪代码实现一个方法 ( )，它在二叉树的上下文中返回一个具有特定秩 k 的节点。我正在为此苦苦挣扎，希望你能给我一个答案。

4

1 回答 1

1

因此，如果给定等级 k 并且我们需要找到具有给定等级的节点，我们首先需要一个遍历算法来搜索树。预购遍历应该可以正常工作。这是一个递归的。

function preOrderTraversal(node){
    if(node !== null){
        print(node.data);
        preOrderTraversal(node.left);
        preOrderTraversal(node.right);
    }
}

现在我们有了一种方法来遍历我们的树，我们需要实现该elementbyRank方法并修改遍历算法。我们将检查每个节点的排名，而不是打印数据。我们需要通过我们需要找到的排名，我们需要在遍历中添加一个返回。

elementbyRank 方法非常简单：

function elementbyRank(k){
   return preOrderTraversal(root, k);    
}

现在我们需要对 prePrderTraveral 进行更改，并将名称也更改为 elementbyRankTraversal。

function elementbyRankTraversal(node, key){
    if(node !== null){
        if(key == rankofElement(node.key))
            return node;    

        return elementbyRankTraversal(node.left);
        return elementbyRankTraversal(node.right);
    }
    return null;
}

因此，现在如果我们找到一个具有传入等级的节点，我们将取回该节点。但如果一个不存在，我们将得到一个空值。

我知道你说给定node x，rankofElement(x)将返回元素的等级。但是您正在将node's key直接与xwhich 告诉我这不是xanode而是. 如果我错了，那么只需从.xkey of node xelementbyRankTraversal()

这应该有效。

于 2018-06-14T14:39:54.823 回答