Рубрики

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

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

На вышеприведенной диаграмме преемник 810 , преемник 1012, а 1420 .

Метод 1 (использует родительский указатель)
В этом методе мы предполагаем, что у каждого узла есть родительский указатель.

Алгоритм делится на два случая на основе того, что правое поддерево входного узла пустое или нет.

Вход: узел, корень // узел — это узел, чей преемник Inorder необходим.
output: succ // succ является преемником Inorder узла .

1) Если правое поддерево узла не NULL , то succ лежит в правом поддереве. Делай следующее.
Перейти к правому поддереву и вернуть узел с минимальным значением ключа в правом поддереве.
2) Если правое дерево узла имеет значение NULL, то succ является одним из предков. Делай следующее.
Перемещайтесь вверх, используя указатель родителя, пока не увидите узел, который остается дочерним от его родителя. Родителем такого узла является succ .

Реализация
Обратите внимание, что функция для поиска преемника InOrder выделена (с серым фоном) в коде ниже.

С

#include <stdio.h>
#include <stdlib.h>

   
/ * Узел двоичного дерева содержит данные, указатель на левого потомка

   и указатель на правого ребенка * /

struct node

{

    int data;

    struct node* left;

    struct node* right;

    struct node* parent;

};

  

struct node * minValue(struct node* node); 

  

struct node * inOrderSuccessor(struct node *root, struct node *n)

{

  // шаг 1 приведенного выше алгоритма

  if( n->right != NULL )

    return minValue(n->right);

  

  // шаг 2 вышеуказанного алгоритма

  struct node *p = n->parent;

  while(p != NULL && n == p->right)

  {

     n = p;

     p = p->parent;

  }

  return p;

}

  
/ * Если дано непустое двоичное дерево поиска, вернуть минимальные данные

    значение найдено в этом дереве. Обратите внимание, что все дерево не нужно

    быть обысканным. * /

struct node * minValue(struct node* node) {

  struct node* current = node;

   

  / * зациклиться, чтобы найти самый левый лист * /

  while (current->left != NULL) {

    current = current->left;

  }

  return current;

}

  
/ * Вспомогательная функция, которая выделяет новый узел с заданными данными и

    NULL левый и правый указатели. * /

struct node* newNode(int data)

{

  struct node* node = (struct node*)

                       malloc(sizeof(struct node));

  node->data   = data;

  node->left   = NULL;

  node->right  = NULL;

  node->parent = NULL;

    

  return(node);

}

  
/ * Даем двоичное дерево поиска и число, вставляем новый узел с

    данный номер в правильном месте в дереве. Возвращает новый

    корневой указатель, который затем должен использовать вызывающий объект (стандартный трюк для

    избегать использования эталонных параметров). * /

struct node* insert(struct node* node, int data)

{

  / * 1. Если дерево пустое, вернуть новое,

      один узел * /

  if (node == NULL)

    return(newNode(data));

  else

  {

    struct node *temp;  

  

    / * 2. В противном случае вернемся вниз по дереву * /

    if (data <= node->data)

    {    

         temp = insert(node->left, data);

         node->left  = temp;

         temp->parent= node;

    }

    else

    {

        temp = insert(node->right, data);

        node->right = temp;

        temp->parent = node;

    }    

   

    / * вернуть (неизмененный) указатель узла * /

    return node;

  }

   
/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

  struct node* root = NULL, *temp, *succ, *min;

  

  // создаем дерево, указанное на диаграмме выше

  root = insert(root, 20);

  root = insert(root, 8);

  root = insert(root, 22);

  root = insert(root, 4);

  root = insert(root, 12);

  root = insert(root, 10);  

  root = insert(root, 14);    

  temp = root->left->right->right;

  

  succ =  inOrderSuccessor(root, temp);

  if(succ !=  NULL)

    printf("\n Inorder Successor of %d is %d ", temp->data, succ->data);    

  else

    printf("\n Inorder Successor doesn't exit");

  

  getchar();

  return 0;

}

Джава

// Java-программа для поиска узла минимального значения в дереве двоичного поиска

  
// Узел двоичного дерева

class Node {

  

    int data;

    Node left, right, parent;

  

    Node(int d) {

        data = d;

        left = right = parent = null;

    }

}

  

class BinaryTree {

  

    static Node head;

  

    / * Учитывая бинарное дерево поиска и число,

     вставляет новый узел с указанным номером в

     правильное место в дереве. Возвращает новый

     корневой указатель, который затем должен использовать вызывающий

     (стандартный трюк, чтобы избежать использования ссылки

     параметры). * /

    Node insert(Node node, int data) {

  

        / * 1. Если дерево пустое, вернуть новое,

         один узел * /

        if (node == null) {

            return (new Node(data));

        } else {

  

            Node temp = null;

              

            / * 2. В противном случае вернемся вниз по дереву * /

            if (data <= node.data) {

                temp = insert(node.left, data);

                node.left = temp;

                temp.parent = node;

  

            } else {

                temp = insert(node.right, data);

                node.right = temp;

                temp.parent = node;

            }

  

            / * вернуть (неизмененный) указатель узла * /

            return node;

        }

    }

  

    Node inOrderSuccessor(Node root, Node n) {

  

        // шаг 1 приведенного выше алгоритма

        if (n.right != null) {

            return minValue(n.right);

        }

  

        // шаг 2 вышеуказанного алгоритма

        Node p = n.parent;

        while (p != null && n == p.right) {

            n = p;

            p = p.parent;

        }

        return p;

    }

  

    / * Если дано непустое двоичное дерево поиска, вернуть минимальные данные

     значение найдено в этом дереве. Обратите внимание, что все дерево не нужно

     быть обысканным. * /

    Node minValue(Node node) {

        Node current = node;

  

        / * зациклиться, чтобы найти самый левый лист * /

        while (current.left != null) {

            current = current.left;

        }

        return current;

    }

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String[] args) {

        BinaryTree tree = new BinaryTree();

        Node root = null, temp = null, suc = null, min = null;

        root = tree.insert(root, 20);

        root = tree.insert(root, 8);

        root = tree.insert(root, 22);

        root = tree.insert(root, 4);

        root = tree.insert(root, 12);

        root = tree.insert(root, 10);

        root = tree.insert(root, 14);

        temp = root.left.right.right;

        suc = tree.inOrderSuccessor(root, temp);

        if (suc != null) {

            System.out.println("Inorder successor of " + temp.data + 

                                                      " is " + suc.data);

        } else {

            System.out.println("Inorder successor does not exist");

        }

    }

}

  
// Этот код предоставлен Mayank Jaiswal

питон

# Программа Python для поиска преемника inroder в BST

  
# Узел двоичного дерева

class Node:

  

    # Конструктор для создания нового узла

    def __init__(self, key):

        self.data = key 

        self.left = None

        self.right = None

  

def inOrderSuccessor(root, n):

      

    # Шаг 1 приведенного выше алгоритма

    if n.right is not None:

        return minValue(n.right)

  

    # Шаг 2 приведенного выше алгоритма

    p = n.parent

    while( p is not None):

        if n != p.right :

            break 

        n =

        p = p.parent

    return p

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

def minValue(node):

    current = node

  

    # цикл, чтобы найти самый левый лист

    while(current is not None):

        if current.left is None:

            break

        current = current.left

  

    return current

  

  
# Учитывая двоичное дерево поиска и число, вставляет
# новый узел с указанным номером в правильном месте
# в дереве. Возвращает новый корневой указатель, который
# вызывающий должен использовать (стандартный прием, чтобы избежать
# с использованием опорных параметров)

def insert( node, data):

  

    # 1) Если дерево пусто, вернуть новый одиночный узел

    if node is None:

        return Node(data)

    else:

         

        # 2) В противном случае, вернуться вниз по дереву

        if data <= node.data:

            temp = insert(node.left, data)

            node.left = temp 

            temp.parent = node

        else:

            temp = insert(node.right, data)

            node.right = temp 

            temp.parent = node

          

        # вернуть неизмененный указатель узла

        return node

  

  
# Программа Progam для тестирования вышеуказанной функции

  

root  = None

  
# Создание дерева, приведенного на диаграмме выше

root = insert(root, 20)

root = insert(root, 8);

root = insert(root, 22);

root = insert(root, 4);

root = insert(root, 12);

root = insert(root, 10);  

root = insert(root, 14);    

temp = root.left.right.right 

  

succ = inOrderSuccessor( root, temp)

if succ is not None:

    print "\nInorder Successor of %d is %d " \

            %(temp.data , succ.data)

else:

    print "\nInorder Successor doesn't exist"

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)


Вывод вышеуказанной программы:
Inorder Наследник 14 — 20

Сложность времени: O (h) где h — высота дерева.

Способ 2 (поиск из корня)
Родительский указатель НЕ нужен в этом алгоритме. Алгоритм делится на два случая на основе того, что правое поддерево входного узла пустое или нет.

Вход: узел, корень // узел — это узел, чей преемник Inorder необходим.
output: succ // succ является преемником Inorder узла .

1) Если правое поддерево узла не NULL , то succ лежит в правом поддереве. Делай следующее.
Перейти к правому поддереву и вернуть узел с минимальным значением ключа в правом поддереве.
2) Если правое sbtree узла имеет значение NULL, тогда начните с корня и используйте метод поиска. Делай следующее.
Пройдите вниз по дереву, если данные узла больше, чем данные корня, то идите направо, в противном случае — налево.

struct node * inOrderSuccessor(struct node *root, struct node *n)

{

    // шаг 1 приведенного выше алгоритма

    if( n->right != NULL )

        return minValue(n->right);

  

    struct node *succ = NULL;

  

    // Начинаем с корня и ищем преемника по дереву

    while (root != NULL)

    {

        if (n->data < root->data)

        {

            succ = root;

            root = root->left;

        }

        else if (n->data > root->data)

            root = root->right;

        else

           break;

    }

  

    return succ;

}

Спасибо за предложение этого метода.

Сложность времени: O (h) где h — высота дерева.

Ссылки:
http://net.pku.edu.cn/~course/cs101/2007/resource/Intro2Algorithm/book6/chap13.htm

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

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

0.00 (0%) 0 votes