N-й по величине элемент в бинарном дереве поиска

Question

Как найти N-й по величине узел в BST?

Сохраняю ли я переменную count при выполнении обхода по порядку BST? Вернуть элемент, когда count = N ???

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);

Answer 2

Подсказка: используйте обход по порядку дерева. Он может распечатывать элементы в отсортированном порядке, так что вы наверняка найдете N-й по величине элемент. Держите счетчик, когда вы «ходите», увеличивая каждый раз, когда вы «посещаете» узел.

Редактировать : хотя ответ IVlad действительно быстрее, он требует от вас хранения дополнительной информации в узлах. Этот ответ не, но это O(n). Просто отметив, что это компромисс, о котором вы должны знать.

Answer 3

Смотрите мой ответ здесь . Вы можете сделать это в среднем за O(log n), где n = количество узлов. В худшем случае все равно O(n) ЕСЛИ дерево не сбалансировано (всегда O(log n), если оно сбалансировано, однако). В порядке обхода всегда O(n) однако.

Answer 4

// 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;
}

Answer 5

Я бы сделал это, перейдя по дереву от самого большого к наименьшему элементу и возвращая значение при достижении заданной позиции. Я реализовал аналогичную задачу для второго по величине значения. Значение 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;
}

Answer 6

K'th крупнейший элемент в BST. Научитесь думать о такой проблеме и решать с помощью рекурсии. Kth Larget Объяснение Рекурсия

Answer 7

• Сохранение размера поддерева в каждом узле (root.size что-то подобное). например, {2,3,1} - это двоичное дерево с корнем 2, тогда размер узла (2) равен 3, размер узла (1) равен 1, а размер узла (2) равен 1

• , если вы хотите найти 4-й элемент в классе с размером корневого узла 23, подумайте о его ранге

• максимальный ранг элемента равен 23, поскольку размер корневого узла равен 23. Таким образом, 4-й по величине ранг элемента равен 23-4 + 1 = 20

• поэтому нам нужно найти элемент 20-го ранга в данном дереве

• первоначально объявить rank = 0 флаг равным нулю

• начиная с корневого узла, найдите его ранг (ранг + размер левого потомка + 1), например, размер левого потомка равен 16, тогда ранг корневого элемента равен 17 (ранг + размер левого потомка +1)

• поэтому мы должны искать элемент с рангом 20. так что, очевидно, мы должны перейти к его правому потомку

• Перейдите к правому ребенку и на основе приведенной выше формулы найдите правый дочерний ранг (на основе приведенной выше формулы обратите внимание: теперь значение флага ранга равно 17), решите, идти ли вправо или влево на основе ранга

• повторяйте этот процесс рекурсивно, пока мы не найдем ранг == 20

Answer 8

Вот как вы можете сделать это, слегка изменив порядок обхода дерева двоичного поиска - мы находим k-й по величине элемент;

    void kthLargest(Node node, int k, int count) {

      if(node != null) {

         nthLargest(node.left,k,count); //traversing the left node

         //while visit the node we do the following
         count++; // increment the count and check if that is equal to k
         if ( count == k ) {
           System.out.println("Node found "+node.value);
         } 

         nthLargest(node.right,k,count); //traversing the right node
      }

    }

Но проблема в том, что вы собираетесь достичь k-го наименьшего элемента и, следовательно, ваш вызов метода должен быть следующим: как k-й наибольший элемент = (n-k) -ый наименьший элемент.

    nthLargest(root,n-k,0);

Answer 9

Этот кусок кода от моего назначения, и одно из условий было не использовать массивы. Чтобы сделать код более компактным и читабельным, вы можете использовать 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);
}
}
    `

Answer 10

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);
}