C语言 如何在二叉搜索树中找到第N个元素?

uubf1zoe  于 2022-12-03  发布在  其他
关注(0)|答案(4)|浏览(140)

我在C中有一个二叉搜索树,目前的目标是找到树中的第N个元素。我试图递归地做这件事,但这不是最重要的。我可以访问任何给定节点下的节点数量(包括)。
我试了这段代码:

TreeNode* findNthElement(int N, TreeNode* tree) {
  static int count = 0;
  printf("nodeCount: %d\nN: %d\nCount: %d\n", tree->nodeCount, N, count);//debug
  //null case
  if (tree == NULL) {
    return NULL;
  }
  //recursion
  if (count <= N) {
    findNthElement(N, tree->left);
    count++;
    if (count == N) {
      count = 0;
      return tree;
    }
    findNthElement(N, tree->right);
  }
}

这应该是一个递归函数来完成我的任务,但是count的值总是0,即使它是静态的。我也尝试过在函数外初始化count,并在成功或失败时将其重置为0,但也没有成功。

gcuhipw9

gcuhipw91#

您的代码忽略了递归调用返回的节点,因此,如果递归调用找到了目标节点,调用方并不知道它。此外,在findNthElement(N, tree->right)调用之后,不会返回任何内容。
同样,你不应该使用静态计数。计数逻辑可以通过 * reduce * 作为N参数传递给递归调用的值来满足。
下面是一个实现:

TreeNode* findNthElement(int n, TreeNode* tree) {
    if (tree == NULL) {
        return NULL;
    }
    int currentNum = tree->left == NULL ? 1 : tree->left->nodeCount + 1;
    return n == currentNum ? tree // Found it!
         : n <  currentNum ? findNthElement(n, tree->left) 
                           : findNthElement(n - currentNum, tree->right);
}
dauxcl2d

dauxcl2d2#

这段代码超出了我的知识范围,但是也许count++需要在之前递归?因为你在调用递归时没有增加代码中的计数。例如:

if (count <= N) {
    count++;
    findNthElement(N, tree->left);
pzfprimi

pzfprimi3#

你根本不需要将count定义为静态的,你可以直接递增参数并递归调用,直到N == count。无论何时调用函数,即使是递归调用,都会在内存堆栈中创建一个新的count变量。

TreeNode* findNthElement(int N, TreeNode* tree, int count) {
    TreeNode * nthTree = NULL;
    if(tree == NULL) 
        return NULL;

    //Found the Nth element
    if (count == N){
       return tree;
    }
    
    //Not using ++count just for clarity
    //First it will check left subtree, if its Nth then return it else go right
    nthTree = findNthElement(N, tree->left, count+1); //Recursive call for left node

    //Recursive call for right node
    return (nthTree == NULL) ? findNthElement(N, tree->right, count+1) : nthTree; 
     
}
qlzsbp2j

qlzsbp2j4#

为了找到BST中的第n个最小元素,可以应用如下逻辑:

using System.Collections.Generic;
public int smallElement(int k)
{
    Node<T> node = Root;
    int count = k;
    int sizeOfSubTree =0;
    
    while (node != null)
    {
        sizeOfSubTree = node.SizeOfLeftSubTree();
        if(sizeOfSubTree +1 == count)
        {
            return node.Value;
        }
        else if(sizeOfSubTree +1 < count)
        {
            node=node.Right;
            count -= sizeOfSubTree +1 ;
            
        }
        else
        {
            
            node = node.Right;
        }
        
    }
    return -1;
    
    
}

您还可以查看以下资源以获取帮助:
in-order traversal to find nth node
Find k’th smallest node in a Binary Search Tree (BST)
希望这对你有帮助。

相关问题