获取一个值在 BST 的有序列表中的位置（无需创建列表）

Question

我完全被这个问题困住了。我需要输出一个值在有序列表中的位置（第一个索引 0）。需要注意的是，我无法创建列表并在其中进行搜索。对于每个节点，我都有一个变量，其中包含有关任何给定树（包括根）中有多少节点的信息。我让它在大约 50% 的情况下工作，但其余的以难以理解的方式失败......如果该值不存在，我需要 return 它本来应该存在的索引。

在 class 树中

public int position(int val) {
    if (this.isEmpty()){
        return 0;
    }

    if (val == root.key){
        return (root.subNodes - root.rightchild.subNodes) - 1;
    }

    if (val < root.key){
        return root.position(0,root.subNodes - 1,val,root);
    } else {
        return (root.subNodes - root.rightchild.subNodes) +root.position(0,root.subNodes - 1,val,root.rightchild);
    }

}

在class节点

int position(int min, int max, int k, Node n){
    if (k == n.key){
        if (n.rightchild != null){
            return n.subNodes - (n.rightchild.subNodes);
        }
        return max;
    }
    if (n.rightchild == null && n.leftchild == null){
        return 1;
    }
    if (k < n.key){
        return position(min ,n.leftchild.subNodes - 1, k, n.leftchild);
    }

    if (k > n.key && n.rightchild != null){
        return position(n.subNodes - (n.rightchild.subNodes + 1), n.subNodes - 1, k, n.rightchild);
    }

    return max;
}

Answer 1

想法：

您可以按顺序遍历树并跟踪您访问过的节点数。这需要某种计数器，可能还需要一个辅助方法。

当我们找到一个值大于或等于期望值的节点时，我们停止搜索。这是因为我们要么找到了所需值的索引，要么找到了所需值所在位置的索引（所需值不会出现在任何更早或更晚的索引中）。如果我们永远找不到等于或大于期望值的节点，那么期望值将位于树的末尾，其位置等于节点数。

实施：

假设你有这个节点

public class Node {
   int value;
   Node leftChild;
   Node rightChild;

   // Getters and Setters
}

还有这棵树

public class Tree {
    Node root;

   // Getters and Setters
}

树的内部

public int position(int val) {
   positionHelper(val, root, 0);
}

public int positionHelper(int val, Node currentNode, int steps) {
   // In-order search checks left node, then current node, then right node
   if(currentNode.getLeftChild() != null) {
       steps = positionHelper(val, currentNode.getLeftChild(), steps++);
   }

   // We found the node or have already moved over the node, return current steps
   if(currentNode.getValue() >= val) {
       return steps;
   }

   // Next Node Index  
   steps++;

   if(currentNode.getRightChild() != null) {
       steps = positionHelper(val, currentNode.getRightChild(), steps++);
   }

   return steps;
}

如果有任何问题或有任何疑问，请告诉我

获取一个值在 BST 的有序列表中的位置（无需创建列表）

Get position of a value in a BST's inorder list(without creating the list)

java

binary-search-tree