В порядке наследника в бинарном дереве поиска

Question

Учитывая узел в BST, как найти следующий более высокий ключ?

Answer 1

Общий способ зависит от того, есть ли у вас родительская ссылка в ваших узлах или нет.

Если вы храните родительскую ссылку

, тогда вы выбираете:

1. Самый левый дочерний элемент правого дочернего элемента, если ваш текущий узел имеет правого дочернего элемента.Если у правого потомка нет левого потомка, правый потомок является вашим преемником inorder.
2. Перейдите вверх по родительским узлам-предкам, и когда вы найдете родителя, у которого левый потомок является узлом, в котором вы находитесь в данный момент, родительявляется преемником inorder вашего исходного узла.

Если у вас есть правильный ребенок, используйте этот подход (случай 1 выше):

Если выу вас нет подходящего ребенка, используйте этот подход (случай 2 выше):

Если вы не сохраняете родительскую ссылку

Тогда вам нужновыполнить полное сканирование дерева, отслеживая узлы, обычно со стеком, чтобы у вас была информация, необходимая для того, чтобы в основном сделать то же самое, что и первый метод, который полагался на родительскую ссылку.

Answer 2

код Python для ответа Лассе :

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

Answer 3

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

Answer 4

В двоичном дереве поиска алгоритм поиска следующего наивысшего узла данного узла в основном находит наименьший узел правого поддерева этого узла.

Алгоритм может быть просто:

1. Начать с правого потомка данного узла (сделать его временным текущим узлом)
2. Если текущий узел не имеет левого потомка, это следующий по значению узел.
3. Если у текущего узла есть левый потомок, сделайте его текущим узлом.

Повторяйте 2 и 3, пока мы не найдем следующий наивысший узел.

Answer 5

Вот реализация без необходимости родительских ссылок или промежуточных структур (например, стека).Эта преемственная функция по порядку немного отличается от того, что большинство может искать, поскольку она работает с ключом, а не с узлом.Кроме того, он найдет преемника ключа, даже если его нет в дереве.Не слишком трудно изменить, если вам нужно, однако.

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

Answer 6

Проверьте здесь: Преемник InOrder в бинарном дереве поиска

В двоичном дереве преемник Inorder узла является следующим узлом в обходе Inorder двоичного дерева.Inorder Successor равен NULL для последнего узла в обходе Inoorder.В дереве двоичного поиска преемник преемника входного узла также может быть определен как узел с наименьшим ключом, который больше ключа входного узла.

Answer 7

Мы можем найти преемника в O (log n) без использования родительских указателей (для сбалансированного дерева).

Идея очень похожа на то, когда у вас есть родительские указатели.

Мы можем определить рекурсивную функцию, которая достигает этого следующим образом:

• Если текущий узел является целью, вернуть самый левый / наименьший узел его правого поддерева, если он существует.
• Рекурсировать влево, если цель меньше текущего узла, и вправо, если он больше.
• Если цель находится слева и мы еще не нашли преемника, вернуть текущий узел.

Псевдо-код:

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

Демоверсия Live Java .

Answer 8

Если мы выполняем обход в порядке, то мы посещаем левое поддерево, затем корневой узел и, наконец, правое поддерево для каждого узла в дереве.Выполнение обхода по порядку даст нам ключи двоичного дерева поиска в порядке возрастания, поэтому, когда мы ссылаемся на получение преемника по порядку узла, принадлежащего к бинарному дереву поиска, мы имеем в виду, каким будет следующий узел в последовательности изданный узел.

Допустим, у нас есть узел R, и мы хотим, чтобы он был преемником по порядку. У нас будут следующие случаи.

[1] Корень R имеетправый узел, поэтому все, что нам нужно сделать, это пройти к самому левому узлу R-> right.

[2] Корень R не имеет правого узла, в этом случаемы перемещаемся вверх по дереву, следуя родительским ссылкам, пока узел R не станет левым потомком своего родителя, когда это происходит, мы имеем родительский узел P в качестве преемника в порядке.

[3] Мы находимся в крайнем правом узле дерева, в этом случае преемника по порядку нет.

Реализация основана на следующем определении узла

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

Answer 9

C ++ решение, предполагая, что узлы имеют левый, правый и родительский указатели:

Это иллюстрирует функцию 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

Answer 10

Реализация C # (не рекурсивная!) Для поиска «следующего» узла данного узла в двоичном дереве поиска, где каждый узел имеет ссылку на своего родителя.

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