如何获取元素在bst递归中的位置?在O(h)运行时 [英] How get the position of an element in a bst recursive ?? in O(h) runtime

问题描述

我需要获取bst元素的位置.这是我正在使用的结构numSubtree(用于跟踪子树中有多少个节点).

I need to get the position of an element of a bst. This is the struct that I am using, numSubtree (is to get track of how many nodes are in the subtree).

struct bst_node {
      int      val;
      int    numSubtree;
      bst_node *left;
      bst_node *right;

};

例如，如果调用position_of(number)，它应该返回索引1,2,3..etc 到目前为止，我已经尝试过了

for example, if a call position_of(number) it should return me the index 1,2,3..etc so far i have tried this

 int _position_of(bst_node *t, T x, int count){

          if (t->left != nullptr) {
               count = t->left->numNodesSub + 1;
          }else {
                count = 1;  
          }

          if (t->val == x) {
            return count;
          }
            
          if (x < t->val ) {
            return _position_of(t->left, x, count);
          }

          //otherwise 
          return _position_of(t->right, x, count + 1);

      }

推荐答案

给出一个bst_node *node和一个元素x，我们要查找元素<= x的数量.有四种情况需要考虑:

Given a bst_node *node and an element x we want to find the number of elements <= x. There are four cases to consider:

• 如果节点为空，则没有元素<= x，因此返回0.

如果node->val < x，node和node->right子树是> x，请在root->left上找到位置.

If node->val < x, node and the node->right subtree are > x, so find the position on the root->left.

如果node->val > x，node和node->left子树为<= x，则在找到右侧位置的结果中加1 +左子树大小.

If node->val > x, node and the node->left subtree are <= x, so add 1 + left subtree size to the result of finding the position on the right side.

否则，如果node->val == x，只有node和node->left子树是<= x，那么只需返回1 +左子树大小即可.

Otherwise, if node->val == x, only node and the node->left subtree are <= x, so simply return 1 + left subtree size.

// Returns the number of elements <= `x` in the binary search tree rooted at `node`.
int position(bst_node *node, T x) {
    if (!node) {
        return 0;
    }

    if (node->val < x) {
        return position(node->left, x);
    } 

    bst_node* left_node = node->left;
    int left_subtree_size = 0;
    if (node->left) {
        left_subtree_size = node->left->numSubtree;
    }

    if (node->val > x) {
        return 1 + left_subtree_size + position(node->right, x);
    } else {
        return 1 + left_subtree_size;
    }
}

这篇关于如何获取元素在bst递归中的位置?在O(h)运行时的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！