二叉搜索树中第N大的元素

Question

如何在二叉搜索树中查找第N大的节点？

我在进行二叉搜索树的中序遍历时应该保留一个计数变量吗？当计数等于N时返回该节点的值吗？

- Jony

Answer 1

这个想法非常简单：按每个节点的值降序遍历树。当你到达第N个节点时，打印该节点的值。以下是递归代码。

void printNthNode(Node* root, int N)
{
   if(root == NULL)
       return;

   static int index = 0; //These will initialize to zero only once as its static

   //For every Node go to the right of that node first.
   printNthNode(root->right, N);


   //Right has returned and now current node will be greatest
   if(++index == N)
   {
    printf("%d\n", root->data);
    return;
   }

   //And at last go to the left
   printNthNode(root->left, N);
}

编辑 - 根据下面的评论，由于静态局部变量，这似乎是一次性调用函数。可以通过传递index的包装器对象来解决此问题，如下所示：

    class WrapIndex {
         public: int index;
    };

方法签名将更改为：

void printNthNode(Node* root, int N, WrapIndex wrapInd)

现在，我们不需要一个本地静态变量；而是使用包装对象的 index。调用将如下所示：

WrapIndex wrapInd = new WrapIndex();
wrapInd.index=0;
printNthNode(root,7,wrapInd);

wrapInd.index=0;
printNthNode(root,2,wrapInd);

- Vallabh Patade

---

这是一个严格的“一次性”使用函数。例如，如果b是BSTree，则printNthNode(b.head, 7); //打印第7个最大的数字 printNthNode(b.head, 2); //无法打印任何内容 - lifebalance

@lifebalance 我怀疑这是由于static局部变量引起的。我们可以使用一个包装对象来存储index并将其传递给每个调用。对于每个新的调用，我们将把这个包装对象的index设置为0。 - Vallabh Patade

请在您的解决方案中提供包装器的一些示例代码。谢谢。 - lifebalance

@lifebalance 编辑了答案！ - Vallabh Patade

你可能需要传递一个对 wrapInd 的引用，否则它可能无法正常工作。或者，只需将第三个参数作为整数引用变量 printNthNode(Node*, int, int&) 即可。调用将是 int counter = 0; printNthNode (root, 7, counter); counter = 0; printNthNode(root, 2, counter); - lifebalance

Answer 2

提示: 使用树的 中序遍历。它可以按排序顺序打印出项目，因此您可以确定第 N 个最大项目。在“遍历”每个节点时，将计数器增加一次。

编辑: IVlad 的回答确实更快，但需要在节点中保留额外信息。此答案不需要，但是它的复杂度为O(n)。只是指出这是您必须注意的权衡。

- Eli Bendersky

---

@IVlad：你的方法需要在BST节点中额外存储吗？ - Eli Bendersky

不比你的多。你打算如何在没有额外存储空间的情况下遍历树？递归堆栈也算是额外的内存。 - IVlad

@IVlad：这不是关键点。关键是修改BST节点以保存遍历所需的额外信息。 - Eli Bendersky

@IVlad：因为这是一道作业题，而不是设计生产算法。这就是为什么有规则存在的原因。我试图撤销我的负评，但已经太晚了，你需要编辑答案以使其可行。 - Eli Bendersky

IVlad：你的解决方案需要额外的O(n)存储空间：每个节点都需要一个计数器。而这个解决方案只需要额外的O(log n)存储空间，用于递归过程中堆栈的最大深度。 - jemfinch

Answer 3

请看我这里的回答。当节点数为n时，平均情况下可以在O(log n)时间内完成，但如果树不平衡，则最坏情况下仍然需要O(n)时间（如果树是平衡的，则始终为O(log n)）。然而，中序遍历始终需要O(n)时间。

- IVlad

---

当然，这仅适用于您可以修改二叉树节点的情况。如果您正在使用库二叉树，则您的解决方案不是一个选项。 - jemfinch

我认为用所需的额外信息填充树的成本是O(n)，不是吗？因此，如果给定的树没有附加信息，我不认为它可以在O(log n)中解决。 - duduamar

它需要O(n)的内存，但不需要任何额外的时间，只需要构建内存中的树所需的时间。 - IVlad

Answer 4

• 维护每个节点的子树大小（例如，{2,3,1} 是一个根节点为 2 的二叉树，则节点 (2) 的大小为 3，节点 (1) 的大小为 1，节点 (2) 的大小为 1）

• 如果您想在根节点大小为 23 的树中查找第四大的元素，请考虑其排名

• 最大元素的排名是 23，因为根节点大小为 23。因此，第四大的元素排名是 23-4+1=20

• 因此，我们必须在给定的树中找到第 20 名元素

• 最初声明一个 rank=0 标志为零

• 从根节点开始，找到它的排名（rank+左子树大小+1），例如左子树大小为 16，则根元素的排名为 17（rank+左子树大小+1）

• 因此，我们必须查找排名为 20 的元素。所以显然我们必须遍历到它的右子树

• 遍历到右子树，并根据上述公式找到右子树的排名（根据上述公式，注意：现在 rank 标志值为 17），根据排名决定向左还是向右

• 重复此过程，直到找到 rank==20

- pashaplus

Answer 5

这段代码来自我的作业，其中一个条件是不使用数组。为了使代码更紧凑和易读，您可以使用stringName.split("|")。由于该方法是递归的，我使用了stringBuilder，其结构如下："counter|orderOfElementToFind|dataInrequiredNode"。

protected StringBuilder t(StringBuilder s)
{
    if (lc != null) 
    {
        lc.t(s);
}


if((s.toString().charAt(s.toString().length() - 1)) == '|')
{
        String str = s.toString();
    s.delete(0, s.length());

        int counter = 0, k = 0;


        String strTemp = "", newStrBuilContent = "";

        for (int i = 0, c = 0 ; i < str.length(); ++i)
        {
            if (c == 0)
            {
            if (str.charAt(i) != '|')
    {
        strTemp += str.charAt(i); 
    }
    else
    {
        counter = Integer.parseInt(strTemp);
        ++c;

        strTemp = "";
    }
            }
    else
    {

            if (str.charAt(i) != '|')
        {
            strTemp += str.charAt(i); 
            }
        else
        {
                k = Integer.parseInt(strTemp);
        }

    }

    counter ++;

            newStrBuilContent = (counter + "|" + k + "|");
    s.append(newStrBuilContent);
    if (counter == k)
    {
        double ldata = this.getData();
        s.append(ldata);

    }

}

if (rc != null) 
{
    rc.t(s);
} 

    return s;

}

以及方法调用：

// the value of counter ad the beginning is 0 and data 
// segment is missing
String s = ("0|" + order +"|");
StringBuilder strBldr = new StringBuilder(s); 
String content = sTree.t(strBldr).toString();

s = "";

for (int i = 0, c = 0; i < content.length(); ++i)
{           
    if (c < 2)
{
    if (content.charAt(i) == '|')
    {  
        ++c;
        }
    }
else
{
    s += content.charAt(i);
}
}
    `

- Alex

Answer 6

// C++ program to find k'th largest element in BST
#include<iostream>
using namespace std;

struct Node
{
    int key;
    Node *left, *right;
};

// A utility function to create a new BST node
Node *newNode(int item)
{
    Node *temp = new Node;
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

// A function to find k'th largest element in a given tree.
void kthLargestUtil(Node *root, int k, int &c)
{
    // Base cases, the second condition is important to
    // avoid unnecessary recursive calls
    if (root == NULL || c >= k)
        return;

    // Follow reverse inorder traversal so that the
    // largest element is visited first
    kthLargestUtil(root->right, k, c);

    // Increment count of visited nodes
    c++;

    // If c becomes k now, then this is the k'th largest 
    if (c == k)
    {
        cout << "K'th largest element is "
             << root->key << endl;
        return;
    }

    // Recur for left subtree
    kthLargestUtil(root->left, k, c);
}

// Function to find k'th largest element
void kthLargest(Node *root, int k)
{
    // Initialize count of nodes visited as 0
    int c = 0;

    // Note that c is passed by reference
    kthLargestUtil(root, k, c);
}

/* A utility function to insert a new node with given key in BST */
Node* insert(Node* node, int key)
{
    /* If the tree is empty, return a new node */
    if (node == NULL) return newNode(key);

    /* Otherwise, recur down the tree */
    if (key < node->key)
        node->left  = insert(node->left, key);
    else if (key > node->key)
        node->right = insert(node->right, key);

    /* return the (unchanged) node pointer */
    return node;
}

// Driver Program to test above functions
int main()
{
    /* Let us create following BST
              50
           /     \
          30      70
         /  \    /  \
       20   40  60   80 */
    Node *root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

    int c = 0;
    for (int k=1; k<=7; k++)
        kthLargest(root, k);

    return 0;
}

- sankar

Answer 7

我会通过从最大到最小的元素遍历树来完成它，并在达到所需位置时返回值。我为第二大的值实现了类似的任务。值2是硬编码的，但可以通过添加额外参数轻松更改 :)

void BTree::findSecondLargestValueUtil(Node* r, int &c, int &v)
{
    if(r->right) {
        this->findSecondLargestValueUtil(r->right, c, v);
    }

    c++;

    if(c==2) {
        v = r->value;
        return;
    }

    if(r->left) {
        this->findSecondLargestValueUtil(r->left, c, v);
    }
}


int BTree::findSecondLargestValue()
{
    int c = 0;
    int v = -1;

    this->findSecondLargestValueUtil(this->root, c, v);

    return v;
}

- Oleksandr Knyga

Answer 8

使用反向中序遍历。即先访问右子节点而不是左子节点。 递归地，可以按以下方式获得： 考虑递归解决方案时，最重要的问题是必须使用全局计数。

reverseInorder(root){
 if(root!=null){
reverseInorder(root->rightChild);
self
reverseInorder(root->leftChild);
}
}

Java解决方案

    package datastructure.binaryTree;

import datastructure.nodes.BinaryTreeNode;


public class NthElementFromEnd {
    private BinaryTree tree=null;
    int currCount=0;
    public NthElementFromEnd(int[] dataArray) {
        this.tree=new BinaryTree(dataArray);

    }
    private void getElementFromEnd(int n){
        getElementFromEnd(this.tree.getRoot(),n);
    }
    private void getElementFromEnd(BinaryTreeNode node,int n){
        if(node!=null){
            if(currCount<n)
            getElementFromEnd(node.getRightChild(),n);
            currCount++;

            if(currCount==n)
            {
                System.out.print(" "+node.getData());
                return;
            }
            if(currCount<n)
            getElementFromEnd(node.getLeftChild(),n);
        }
    }

    public static void main(String args[]){
        int data[]={1,2,3,4,5,6,7,8,9};
        int n=2;
        new NthElementFromEnd(data).getElementFromEnd(n);
    }
}

- frictionlesspulley

Answer 9

int nLargeBST(node *root, int N) {
    if (!root || N < 0) {
        return -1;
    }
    nLargeBST(root->left, N);
    --N;
    if(N == 0) {
        return root->val;
    }
    nLargeBST(root->right, N);
}

- user1148976

Answer 10

Swift版本。这与Vallabh Patade所说的非常接近。当尝试通过没有子节点的节点时，计数器会增加1。与他略有不同。

class BinaryNode {
    var val: Int
    var left: BinaryNode?
    var right: BinaryNode?

    init(value: Int) {
        self.val = value
    }
}

func findMaxValue(_ n: Int, from root: BinaryNode?) {
    var counter = 0
    maxValue(counter: &counter, n: n, node: root)
}

private func maxValue(counter: inout Int, n: Int, node: BinaryNode?) {
    if node == nil {
        counter += 1
        return
    }
    maxValue(counter: &counter, n: n, node: node?.right)
    // If the counter has reached the nth node we're looking for.
    if counter == n {
        if let val = node?.val { print(val) }
    }
    maxValue(counter: &counter, n: n, node: node?.left)
}

- Hedylove