Как найти N-й самый большой node в BST?
Должен ли я хранить переменную count во время выполнения в порядке прохождения BST? Верните элемент, когда count = N???
Наибольший элемент N в двоичном дереве поиска
Ответ 1
Смотрите мой ответ здесь. Вы можете сделать это в O(log n) в среднем, где n = количество узлов. Худший случай по-прежнему O(n) Если дерево не сбалансировано (всегда O(log n), если оно сбалансировано). Однако для обхода всегда O(n).
Ответ 2
Идея очень проста: пересечь дерево в порядке убывания значений каждого node. Когда вы достигнете Nth node, напечатайте это значение node. Вот рекурсивный код.
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);
Ответ 3
Совет: используйте обход дерева по порядку. Он может распечатывать элементы в отсортированном порядке, поэтому вы можете найти N-й по величине элемент. Держите счетчик, когда вы "ходите", увеличивая каждый раз, когда вы "посещаете" node.
Изменить: в то время как ответ IVlad действительно быстрее, он требует, чтобы вы сохраняли дополнительную информацию в узлах. Этот ответ не только O(n). Просто указывая, что это компромисс, о котором вы должны знать.
Ответ 4
Используйте инвертированное преобразование порядка. Это означает, что вместо первого левого дочернего элемента сначала нужно перейти к правильному потомку. рекурсивно это можно получить следующим образом: Важнейшей проблемой является то, что глобальный счет должен использоваться при рассмотрении рекурсивного решения.
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);
}
}
Ответ 5
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);
}
Ответ 6
Этот фрагмент кода относится к моему назначению, и одно из условий не должно использоваться массивы. Чтобы сделать код более компактным и читаемым, вы можете использовать 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);
}
}
`
Ответ 7
-
Поддерживать размер поддерева на каждом уровне (root.size - это нечто подобное). например, {2,3,1} - двоичное дерево с корнем 2, тогда размер node (2) равен 3, node (1) размер равен 1, а размер node (2) равен 1
-
если u хочет найти 4-й крупный элемент в дереве с корнем node размером 23, подумайте о его ранге
-
максимальный ранг элемента равен 23, так как размер корня node равен 23. Таким образом, 4-й по величине ранг элемента равен 23-4 + 1 = 20
-
поэтому мы должны найти элемент 20-го ранга в данном дереве
-
сначала объявить флаг rank = 0 равным нулю
-
начиная с root node найти свой ранг (rank + размер левого ребенка + 1), например, левый размер файла равен 16, тогда ранний ранний элемент равен 17 (ранний + размер левого ребенка +1)
-
поэтому нам нужно искать элемент с рангом 20. так что, очевидно, нам нужно пересечь его правый дочерний элемент
-
Перейдите к правильному ребенку и на основе вышеприведенной формулы найдите правильный дочерний ранг (на основе приведенной выше формулы, обратите внимание: теперь значение флага ранга составляет 17), решите, нужно ли идти вправо или влево на основе ранга
- повторите этот процесс до тех пор, пока мы не найдем ранг == 20
Ответ 8
Я бы сделал это, пройдя хотя бы дерево от самого большого до самого маленького элемента и возвращающее значение, когда спрошено положение достигнуто. Я выполнил аналогичную задачу для второй по величине ценности. Значение 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;
}
Ответ 9
// 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;
}
Ответ 10
Вот как вы можете это сделать, слегка изменив обход последовательности в двоичном дереве поиска - мы находим 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);
Ответ 11
Kth Largest Element в BST. Узнайте, как думать о такой проблеме и решать с рекурсией. Kth Larget Explanation Recursion