Учитывая node в BST, как найти следующий более высокий ключ?
В порядке правопреемника в двоичном дереве поиска
Ответ 1
Общий способ зависит от того, есть ли у вас родительская ссылка в ваших узлах или нет.
Если вы сохраняете родительскую ссылку
Затем вы выбираете:
- Самый левый дочерний элемент правильного дочернего элемента, если ваш текущий node имеет правильный ребенок. Если у правого ребенка нет левого ребенка, правильным ребенком является ваш преемник inorder.
- Перейдите к родительским родителям-предкам, и когда вы найдете родителя, у которого левый ребенок - это node, на котором вы сейчас находитесь, родителем является преемник inorder вашего исходного node.
Если у вас есть правильный ребенок, сделайте этот подход (пример 1 выше):
Если у вас нет правильного ребенка, сделайте этот подход (пример 2 выше):
Если вы не храните родительскую ссылку
Затем вам нужно выполнить полное сканирование дерева, отслеживая узлы, обычно со стеком, чтобы у вас была информация, необходимая для того, чтобы в основном сделать то же самое, что и первый метод, основанный на родительской ссылке.
Ответ 2
Код Python для Lasse answer:
def findNext(node):
if node.rightChild != None:
return findMostLeft(node.rightChild)
else:
parent = node.parent
while parent != None:
if parent.leftChild == node:
break
node = parent
parent = node.parent
return parent
Ответ 3
Отъезд здесь: Преемник InOrder в двоичном дереве поиска
В двоичном дереве преемник Inorder node - следующий node в Inorder обход двоичного дерева. В порядке Преемник равен NULL для последнего node в Обход обхода. В двоичном поиске Дерево, Inorder Преемник ввода node также можно определить как nodeс наименьшим ключом, большим, чем ключ ввода node.
Ответ 4
Здесь реализована реализация без необходимости в родительских ссылках или промежуточных структурах (например, в стеке). Эта функция преемника в порядке немного отличается от того, что может потребоваться, поскольку она работает с ключом, а не с node. Кроме того, он найдет преемника ключа, даже если его нет в дереве. Однако не так сложно изменить, если вам нужно.
public class Node<T extends Comparable<T>> {
private T data;
private Node<T> left;
private Node<T> right;
public Node(T data, Node<T> left, Node<T> right) {
this.data = data;
this.left = left;
this.right = right;
}
/*
* Returns the left-most node of the current node. If there is no left child, the current node is the left-most.
*/
private Node<T> getLeftMost() {
Node<T> curr = this;
while(curr.left != null) curr = curr.left;
return curr;
}
/*
* Returns the right-most node of the current node. If there is no right child, the current node is the right-most.
*/
private Node<T> getRightMost() {
Node<T> curr = this;
while(curr.right != null) curr = curr.right;
return curr;
}
/**
* Returns the in-order successor of the specified key.
* @param key The key.
* @return
*/
public T getSuccessor(T key) {
Node<T> curr = this;
T successor = null;
while(curr != null) {
// If this.data < key, search to the right.
if(curr.data.compareTo(key) < 0 && curr.right != null) {
curr = curr.right;
}
// If this.data > key, search to the left.
else if(curr.data.compareTo(key) > 0) {
// If the right-most on the left side has bigger than the key, search left.
if(curr.left != null && curr.left.getRightMost().data.compareTo(key) > 0) {
curr = curr.left;
}
// If there no left, or the right-most on the left branch is smaller than the key, we're at the successor.
else {
successor = curr.data;
curr = null;
}
}
// this.data == key...
else {
// so get the right-most data.
if(curr.right != null) {
successor = curr.right.getLeftMost().data;
}
// there is no successor.
else {
successor = null;
}
curr = null;
}
}
return successor;
}
public static void main(String[] args) {
Node<Integer> one, three, five, seven, two, six, four;
one = new Node<Integer>(Integer.valueOf(1), null, null);
three = new Node<Integer>(Integer.valueOf(3), null, null);
five = new Node<Integer>(Integer.valueOf(5), null, null);
seven = new Node<Integer>(Integer.valueOf(7), null, null);
two = new Node<Integer>(Integer.valueOf(2), one, three);
six = new Node<Integer>(Integer.valueOf(6), five, seven);
four = new Node<Integer>(Integer.valueOf(4), two, six);
Node<Integer> head = four;
for(int i = 0; i <= 7; i++) {
System.out.println(head.getSuccessor(i));
}
}
}
Ответ 5
С деревом двоичного поиска алгоритм, чтобы найти следующий самый высокий node данного node, в основном находит наименьшее node правого поддерева этого node.
Алгоритм может просто быть просто:
- Начните с правого дочернего элемента данного node (сделайте его временным током node)
- Если текущий node не имеет левого дочернего элемента, он является следующим самым высоким node.
- Если текущий node имеет левый дочерний элемент, сделайте его текущим node.
Повторите 2 и 3, пока мы не найдем следующий самый высокий node.
Ответ 6
Решение С++, предполагающее, что узлы имеют левый, правый и родительский указатели:
Это иллюстрирует функцию Node* getNextNodeInOrder(Node), которая возвращает следующий ключ двоичного дерева поиска в порядке.
#include <cstdlib>
#include <iostream>
using namespace std;
struct Node{
int data;
Node *parent;
Node *left, *right;
};
Node *createNode(int data){
Node *node = new Node();
node->data = data;
node->left = node->right = NULL;
return node;
}
Node* getFirstRightParent(Node *node){
if (node->parent == NULL)
return NULL;
while (node->parent != NULL && node->parent->left != node){
node = node->parent;
}
return node->parent;
}
Node* getLeftMostRightChild(Node *node){
node = node->right;
while (node->left != NULL){
node = node->left;
}
return node;
}
Node *getNextNodeInOrder(Node *node){
//if you pass in the last Node this will return NULL
if (node->right != NULL)
return getLeftMostRightChild(node);
else
return getFirstRightParent(node);
}
void inOrderPrint(Node *root)
{
if (root->left != NULL) inOrderPrint(root->left);
cout << root->data << " ";
if (root->right != NULL) inOrderPrint(root->right);
}
int main(int argc, char** argv) {
//Purpose of this program is to demonstrate the function getNextNodeInOrder
//of a binary tree in-order. Below the tree is listed with the order
//of the items in-order. 1 is the beginning, 11 is the end. If you
//pass in the node 4, getNextNode returns the node for 5, the next in the
//sequence.
//test tree:
//
// 4
// / \
// 2 11
// / \ /
// 1 3 10
// /
// 5
// \
// 6
// \
// 8
// / \
// 7 9
Node *root = createNode(4);
root->parent = NULL;
root->left = createNode(2);
root->left->parent = root;
root->right = createNode(11);
root->right->parent = root;
root->left->left = createNode(1);
root->left->left->parent = root->left;
root->right->left = createNode(10);
root->right->left->parent = root->right;
root->left->right = createNode(3);
root->left->right->parent = root->left;
root->right->left->left = createNode(5);
root->right->left->left->parent = root->right->left;
root->right->left->left->right = createNode(6);
root->right->left->left->right->parent = root->right->left->left;
root->right->left->left->right->right = createNode(8);
root->right->left->left->right->right->parent =
root->right->left->left->right;
root->right->left->left->right->right->left = createNode(7);
root->right->left->left->right->right->left->parent =
root->right->left->left->right->right;
root->right->left->left->right->right->right = createNode(9);
root->right->left->left->right->right->right->parent =
root->right->left->left->right->right;
inOrderPrint(root);
//UNIT TESTING FOLLOWS
cout << endl << "unit tests: " << endl;
if (getNextNodeInOrder(root)->data != 5)
cout << "failed01" << endl;
else
cout << "passed01" << endl;
if (getNextNodeInOrder(root->right) != NULL)
cout << "failed02" << endl;
else
cout << "passed02" << endl;
if (getNextNodeInOrder(root->right->left)->data != 11)
cout << "failed03" << endl;
else
cout << "passed03" << endl;
if (getNextNodeInOrder(root->left)->data != 3)
cout << "failed04" << endl;
else
cout << "passed04" << endl;
if (getNextNodeInOrder(root->left->left)->data != 2)
cout << "failed05" << endl;
else
cout << "passed05" << endl;
if (getNextNodeInOrder(root->left->right)->data != 4)
cout << "failed06" << endl;
else
cout << "passed06" << endl;
if (getNextNodeInOrder(root->right->left->left)->data != 6)
cout << "failed07" << endl;
else
cout << "passed07" << endl;
if (getNextNodeInOrder(root->right->left->left->right)->data != 7)
cout << "failed08 it came up with: " <<
getNextNodeInOrder(root->right->left->left->right)->data << endl;
else
cout << "passed08" << endl;
if (getNextNodeInOrder(root->right->left->left->right->right)->data != 9)
cout << "failed09 it came up with: "
<< getNextNodeInOrder(root->right->left->left->right->right)->data
<< endl;
else
cout << "passed09" << endl;
return 0;
}
Какие принты:
1 2 3 4 5 6 7 8 9 10 11
unit tests:
passed01
passed02
passed03
passed04
passed05
passed06
passed07
passed08
passed09
Ответ 7
Если мы выполним обход в порядке, то мы посетим левое поддерево, затем root node и, наконец, правое поддерево для каждого node в дереве. Выполнение a в порядке прохождения даст нам ключи двоичного дерева поиска в порядке возрастания, поэтому, когда мы ссылаемся на получение преемника в node, принадлежащего двоичному дереву поиска, мы подразумеваем, что будет следующим node в последовательности из заданного node.
Допустим, что у нас есть node R, и мы хотим, чтобы в порядке преемника у нас были бы следующие случаи.
[1] Корень R имеет право node, поэтому все, что нам нужно сделать, - это переместить влево наиболее node R- > вправо.
[2] Корень R не имеет права node, в этом случае мы возвращаемся назад к дереву, следуя за родительскими ссылками, пока node R не будет левым дочерним элементом его родителя, когда это происходит, мы имеем родительский node P как преемник.
[3] Мы находимся в крайнем правом значении node дерева, в этом случае его преемника нет.
Реализация основана на следующем определении node
class node
{
private:
node* left;
node* right;
node* parent
int data;
public:
//public interface not shown, these are just setters and getters
.......
};
//go up the tree until we have our root node a left child of its parent
node* getParent(node* root)
{
if(root->parent == NULL)
return NULL;
if(root->parent->left == root)
return root->parent;
else
return getParent(root->parent);
}
node* getLeftMostNode(node* root)
{
if(root == NULL)
return NULL;
node* left = getLeftMostNode(root->left);
if(left)
return left;
return root;
}
//return the in order successor if there is one.
//parameters - root, the node whose in order successor we are 'searching' for
node* getInOrderSucc(node* root)
{
//no tree, therefore no successor
if(root == NULL)
return NULL;
//if we have a right tree, get its left most node
if(root->right)
return getLeftMostNode(root->right);
else
//bubble up so the root node becomes the left child of its
//parent, the parent will be the inorder successor.
return getParent(root);
}
Ответ 8
Вы можете прочитать дополнительную информацию здесь (Rus lung)
Node next(Node x)
if x.right != null
return minimum(x.right)
y = x.parent
while y != null and x == y.right
x = y
y = y.parent
return y
Node prev(Node x)
if x.left != null
return maximum(x.left)
y = x.parent
while y != null and x == y.left
x = y
y = y.parent
return y
Ответ 9
Эти ответы кажутся мне слишком сложными. Нам действительно не нужны родительские указатели или любые вспомогательные структуры данных, такие как стек. Все, что нам нужно сделать, - это пересечь дерево из корня в порядке, установить флаг, как только мы найдем цель node, а следующая node в дереве, которое мы посетим, будет в следующем порядке node. Вот быстрая и грязная рутина, которую я написал.
Node* FindNextInorderSuccessor(Node* root, int target, bool& done)
{
if (!root)
return NULL;
// go left
Node* result = FindNextInorderSuccessor(root->left, target, done);
if (result)
return result;
// visit
if (done)
{
// flag is set, this must be our in-order successor node
return root;
}
else
{
if (root->value == target)
{
// found target node, set flag so that we stop at next node
done = true;
}
}
// go right
return FindNextInorderSuccessor(root->right, target, done);
}
Ответ 10
JavaScript-решение - Если данный node имеет право node, тогда верните наименьший node в правом поддереве - Если нет, то есть две возможности: - Данный node является левым дочерним элементом родительского node. Если да, верните родительский node. В противном случае данный node является правильным потомком родительского node. Если это так, верните правый дочерний элемент родительского node
function nextNode(node) {
var nextLargest = null;
if (node.right != null) {
// Return the smallest item in the right subtree
nextLargest = node.right;
while (nextLargest.left !== null) {
nextLargest = nextLargest.left;
}
return nextLargest;
} else {
// Node is the left child of the parent
if (node === node.parent.left) return node.parent;
// Node is the right child of the parent
nextLargest = node.parent;
while (nextLargest.parent !== null && nextLargest !== nextLargest.parent.left) {
nextLargest = nextLargest.parent
}
return nextLargest.parent;
}
}
Ответ 11
Выполнение этого в Java
TreeNode getSuccessor(TreeNode treeNode) {
if (treeNode.right != null) {
return getLeftMostChild(treeNode.right);
} else {
TreeNode p = treeNode.parent;
while (p != null && treeNode == p.right) { // traverse upwards until there is no parent (at the last node of BST and when current treeNode is still the parent right child
treeNode = p;
p = p.parent; // traverse upwards
}
return p; // returns the parent node
}
}
TreeNode getLeftMostChild(TreeNode treeNode) {
if (treeNode.left == null) {
return treeNode;
} else {
return getLeftMostChild(treeNode.left);
}
}
Ответ 12
Мы можем разделить это на 3 случая:
-
Если node является родительским: в этом случае мы обнаруживаем, что он имеет право node и проходит к самому левому дочернему элементу справа node. В случае, если в правом node нет детей, то правый node является его преемником последовательности. Если нет права node, нам нужно перемещаться по дереву, чтобы найти преемника inorder.
-
Если node является левым дочерним: в этом случае родитель является преемником inorder.
-
Если node (назовите его x) является правильным потомком (из его непосредственного родителя): мы пересекаем дерево, пока не найдем node, у которого левое поддерево имеет x.
Экстремальный случай: если node - самый правый угол node, преемник inorder отсутствует.
Ответ 13
Каждый "учебник", который я проверил в google и все ответы в этом потоке, использует следующую логику: "Если node не имеет правильного дочернего элемента, то его последователем в порядке будет один из его предков. link продолжайте движение до тех пор, пока вы не получите node, который является левым дочерним элементом его родителя. Тогда этот родительский node будет потомком в порядке."
Это то же самое, что думать, "если мой родитель больше меня, тогда я левый ребенок" (свойство двоичного дерева поиска). Это означает, что вы можете просто подойти к родительской цепочке, пока указанное свойство не будет истинным. Что, на мой взгляд, приводит к более элегантному коду.
Я думаю, причина, по которой каждый проверяет "я левый ребенок", рассматривая ветки вместо значений в пути кода, который использует родительские ссылки, исходит из логики "заимствования" из алгоритма no-link-to-parent.
Также из приведенного ниже кода мы видим, что не требуется структура данных стека, как это было предложено другими ответами.
Ниже приведена простая функция С++, которая работает для обоих прецедентов (с использованием и без использования ссылки на родителя).
Node* nextInOrder(const Node *node, bool useParentLink) const
{
if (!node)
return nullptr;
// when has a right sub-tree
if (node->right) {
// get left-most node from the right sub-tree
node = node->right;
while (node->left)
node = node->left;
return node;
}
// when does not have a right sub-tree
if (useParentLink) {
Node *parent = node->parent;
while (parent) {
if (parent->value > node->value)
return parent;
parent = parent->parent;
}
return nullptr;
} else {
Node *nextInOrder = nullptr;
// 'root' is a class member pointing to the root of the tree
Node *current = root;
while (current != node) {
if (node->value < current->value) {
nextInOrder = current;
current = current->left;
} else {
current = current->right;
}
}
return nextInOrder;
}
}
Node* previousInOrder(const Node *node, bool useParentLink) const
{
if (!node)
return nullptr;
// when has a left sub-tree
if (node->left) {
// get right-most node from the left sub-tree
node = node->left;
while (node->right)
node = node->right;
return node;
}
// when does not have a left sub-tree
if (useParentLink) {
Node *parent = node->parent;
while (parent) {
if (parent->value < node->value)
return parent;
parent = parent->parent;
}
return nullptr;
} else {
Node *prevInOrder = nullptr;
// 'root' is a class member pointing to the root of the tree
Node *current = root;
while (current != node) {
if (node->value < current->value) {
current = current->left;
} else {
prevInOrder = current;
current = current->right;
}
}
return prevInOrder;
}
}
Ответ 14
Реализация С# (не рекурсивная!), чтобы найти "следующий node данного node в двоичном дереве поиска, где каждый node имеет ссылку на своего родителя.
public static Node WhoIsNextInOrder(Node root, Node node)
{
if (node.Right != null)
{
return GetLeftMost(node.Right);
}
else
{
Node p = new Node(null,null,-1);
Node Next = new Node(null, null, -1);
bool found = false;
p = FindParent(root, node);
while (found == false)
{
if (p.Left == node) { Next = p; return Next; }
node = p;
p = FindParent(root, node);
}
return Next;
}
}
public static Node FindParent(Node root, Node node)
{
if (root == null || node == null)
{
return null;
}
else if ( (root.Right != null && root.Right.Value == node.Value) || (root.Left != null && root.Left.Value == node.Value))
{
return root;
}
else
{
Node found = FindParent(root.Right, node);
if (found == null)
{
found = FindParent(root.Left, node);
}
return found;
}
}
public static Node GetLeftMost (Node node)
{
if (node.Left == null)
{
return node;
}
return GetLeftMost(node.Left);
}
Ответ 15
Мы можем найти преемника в O (log n) без использования родительских указателей (для сбалансированного дерева).
Идея очень похожа на то, когда у вас есть родительские указатели.
Мы можем определить рекурсивную функцию, которая достигает этого следующим образом:
- Если текущий node является целью, верните самый левый/самый маленький node его правого поддерева, если он существует.
- Зарезервируйте левую, если цель меньше текущего node, и вправо, если она больше.
- Если цель находится слева и мы еще не нашли преемника, верните текущий node.
Псевдо-код:
Key successor(Node current, Key target):
if current == null
return null
if target == current.key
if current.right != null
return leftMost(current.right).key
else
return specialKey
else
if target < current.key
s = successor(current.left, target)
if s == specialKey
return current.key
else
return s
else
return successor(current.right, target)
Node leftMost(Node current):
while current.left != null
current = current.left
return current
Ответ 16
вы можете найти все преемника inorder, используя эту функцию
пс. next - это глобальная переменная, которая сначала указывает на нуль
void find(Node root)
{
if(root==null)
return;
find(root.right);
root.next=next;
next=root;
find(root.left);
}
root.next будет указывать на преемника inorder (следующий более высокий ключ)