W kolejności w drzewie wyszukiwania binarnego

Kod Pythona do odpowiedzi Lasse ' a :

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

Sprawdź tutaj: Inorder następca w binarnym drzewie wyszukiwania

W drzewie binarnym, w kolejności następcy a node jest następnym węzłem w Inorder Trawers drzewa binarnego. Inorder Następca jest NULL dla ostatniego węzła w / Align = "left" / W Poszukiwaniu Binarnym Drzewo, w kolejności następcy wejścia węzeł może być również zdefiniowany jako węzeł z najmniejszym klawiszem większym niż klucz węzła wejściowego.

Oto implementacja bez potrzeby tworzenia linków nadrzędnych lub struktur pośrednich (np. stosu). Ta funkcja następcy w kolejności jest nieco inna niż to, czego większość może szukać, ponieważ działa na kluczu, a nie na węźle. Ponadto znajdzie następcę klucza, nawet jeśli nie jest on obecny w drzewie. Nie jest to jednak zbyt trudne do zmiany, jeśli trzeba.

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

W binarnym drzewie wyszukiwania, algorytm znajdowania następnego najwyższego węzła danego węzła jest w zasadzie znajdowaniem najniższego węzła z prawego pod-drzewa tego węzła.

Algorytm może być po prostu:

1. zacznij od prawego potomka danego węzła (uczyń go tymczasowym węzłem bieżącym)
2. jeśli obecny węzeł nie ma lewego potomka, jest to następny najwyższy węzeł.
3. Jeśli bieżący węzeł ma lewy węzeł potomny, zrób z niego bieżący węzeł.

Powtórz 2 i 3 do znajdujemy następny najwyższy węzeł.

Rozwiązanie C++ zakładając, że węzły mają lewy, prawy i nadrzędny Wskaźnik:

Ilustruje to funkcję Node* getNextNodeInOrder(Node), która zwraca następny klucz binarnego drzewa wyszukiwania w kolejności.

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

Który drukuje:

1 2 3 4 5 6 7 8 9 10 11

unit tests: 
passed01
passed02
passed03
passed04
passed05
passed06
passed07
passed08
passed09

Jeśli wykonamy przejście w kolejności, to odwiedzamy lewy podzbiór, następnie węzeł korzeniowy i wreszcie prawy podzbiór dla każdego węzła w drzewie. Wykonanie przejścia w kolejności da nam klucze binarnego drzewa wyszukiwania w kolejności rosnącej, więc kiedy odnosimy się do pobierania następcy w kolejności węzła należącego do binarnego drzewa wyszukiwania, mamy na myśli, jaki byłby następny węzeł w sekwencji z danego węzła.

Powiedzmy, że mamy węzeł R i chcemy jego następcę w kolejności mieć następujące przypadki.

[1] root R ma prawy węzeł, więc wszystko, co musimy zrobić, to przejść do lewego węzła R - > prawego.

[2] root R nie ma prawego węzła, w tym przypadku przemierzamy z powrotem drzewo po łączach nadrzędnych, dopóki węzeł R nie będzie lewym potomkiem swojego rodzica, gdy to nastąpi, mamy węzeł nadrzędny P jako następcę w kolejności.

[3] jesteśmy w skrajnym prawym węźle drzewa, w tym przypadku nie ma w kolejności następca.

Implementacja opiera się na następującej definicji węzła

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

Nie potrzebujemy łącza nadrzędnego lub stosu, aby znaleźć następcę w kolejności w o (log n) (zakładając zrównoważone drzewo). Zachowaj zmienną tymczasową o najnowszej wartości napotkanej w przejściu zlecenia, która jest większa niż klucz. jeśli inorder traversal stwierdzi, że węzeł nie ma odpowiedniego potomka, to będzie to następca inordera. w przeciwnym razie, najbardziej lewy potomek prawego dziecka.

Możesz przeczytać dodatkowe informacje tutaj (Rus)

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

Te odpowiedzi wydają mi się zbyt skomplikowane. Tak naprawdę nie potrzebujemy wskaźników nadrzędnych ani żadnych pomocniczych struktur danych, takich jak stos. Wszystko, co musimy zrobić, to przemierzyć drzewo od korzenia w kolejności, ustawić flagę, jak tylko znajdziemy węzeł docelowy, a następny węzeł w drzewie, które odwiedzamy, będzie kolejnym węzłem w kolejności. Oto szybka i brudna rutyna, którą napisałem.

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

JavaScript solution - Jeżeli dany węzeł ma prawy węzeł, to zwraca najmniejszy węzeł w prawym poddrzewie - Jeśli nie, to są 2 możliwości: - Dany węzeł jest lewym potomkiem węzła nadrzędnego. Jeśli tak, zwróć węzeł nadrzędny. W przeciwnym razie dany węzeł jest Prawym potomkiem węzła nadrzędnego. Jeśli tak, zwróć prawy potomek węzła nadrzędnego

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

Robienie tego w Javie

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

Możemy podzielić to na 3 przypadki:

1. Jeśli węzeł jest rodzicem: w tym przypadku znajdujemy, czy ma prawy węzeł i przesuwamy się do lewego dziecka prawego węzła. W przypadku, gdy prawy węzeł nie ma dzieci, wtedy prawy węzeł jest jego następcą inorder. Jeśli nie ma odpowiedniego węzła, musimy przesunąć się w górę drzewa, aby znaleźć następcę inordera.

2. Jeśli węzeł jest lewym potomkiem: w tym przypadku rodzic jest następcą podrzędnym.

3. If the node (call it x) jest Prawym dzieckiem (jego najbliższego rodzica): przemierzamy drzewo, aż znajdziemy węzeł, którego lewy podzbiór mA x.

Przypadek skrajny: jeśli węzeł jest węzłem narożnym po prawej stronie, nie ma następcy inorder.

Każdy "tutorial", który sprawdziłem w google i wszystkie odpowiedzi w tym wątku używają następującej logiki: "Jeśli node nie ma odpowiedniego dziecka, to jego następca w kolejności będzie jednym z jego przodków. Korzystanie z łącza rodzica Kontynuuj podróżowanie w górę, dopóki nie otrzymasz węzła, który jest lewym dzieckiem jego rodzica. Wtedy ten węzeł macierzysty będzie następcą w kolejności."

Jest to to samo, co myślenie " jeśli mój rodzic jest większy ode mnie, to ja jestem lewym dzieckiem "(własność binary search tree). Oznacza to, że możesz po prostu przejść do łańcucha nadrzędnego, aż powyższa właściwość będzie prawdziwa. Co moim zdaniem skutkuje bardziej eleganckim kodem.

Myślę, że powód, dla którego wszyscy sprawdzają" am I the left child ", patrząc na gałęzie zamiast wartości w ścieżce kodu, która wykorzystuje łącza rodzicielskie, pochodzi z" zapożyczenia " logiki z algorytmu no-link-to-parent.

Również z dołączonego poniżej kodu widzimy, że nie ma potrzeby stosowania danych stosu struktura sugerowana przez inne odpowiedzi.

Poniżej znajduje się prosta funkcja C++, która działa dla obu przypadków użycia (z lub bez użycia łącza do rodzica).

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

Implementacja C #(Non recursive!), aby znaleźć "następny" węzeł danego węzła w binarnym drzewie wyszukiwania, w którym każdy węzeł ma link do swojego rodzica.

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

Możemy znaleźć następcę w o (log n) bez użycia wskaźników nadrzędnych (dla zrównoważonego drzewa).

Pomysł jest bardzo podobny do tego, gdy masz wskaźniki rodzica.

Możemy zdefiniować funkcję rekurencyjną, która osiąga to w następujący sposób:

• Jeśli bieżący węzeł jest celem, zwróć najbardziej lewy / najmniejszy węzeł z jego prawego poddrzewa, jeśli istnieje.
• Rekursuj w lewo, jeśli cel jest mniejszy od bieżącego węzła, i w prawo, jeśli jest większy.
• Jeśli celem jest lewa i nie znaleźliśmy jeszcze następcy, zwróć bieżący węzeł.

Pseudo-kod:

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 demo .