Рубрики

Найти узел с минимальным значением в бинарном дереве поиска

Это довольно просто. Просто рекурсивно проходите узел от корня до левого, пока левый не станет NULL. Узел, левый которого равен NULL, является узлом с минимальным значением.

Для вышеприведенного дерева мы начинаем с 20, затем двигаемся влево 8, мы продолжаем двигаться влево, пока не увидим NULL. Поскольку слева от 4 — NULL, 4 — это узел с минимальным значением.

C ++

// C ++ программа для поиска минимального значения узла в бинарном дереве поиска.
#include <bits/stdc++.h> 

using namespace std; 

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

struct node 

    int data; 

    struct node* left; 

    struct node* right; 

}; 

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

struct node* newNode(int data) 

struct node* node = (struct node*) 

                    malloc(sizeof(struct node)); 

node->data = data; 
node->left = NULL; 
node->right = NULL; 

  

return(node); 

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

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


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

    один узел * /

if (node == NULL) 

    return(newNode(data)); 

else

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

    if (data <= node->data) 

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

    else

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

  

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

    return node; 


  
/ * Учитывая непустое двоичное дерево поиска,
вернуть минимальное значение данных, найденное в этом
дерево. Обратите внимание, что все дерево не нужно
быть обысканным. * /

int minValue(struct node* node) 

struct node* current = node; 

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

while (current->left != NULL) 

    current = current->left; 

return(current->data); 

  
/ * Код водителя * /

int main() 

struct node* root = NULL; 

root = insert(root, 4); 
insert(root, 2); 
insert(root, 1); 
insert(root, 3); 
insert(root, 6); 
insert(root, 5); 

  

cout << "\n Minimum value in BST is " << minValue(root); 

getchar(); 

return 0; 

  
// Этот код предоставлен Мукулом Сингхом.

С

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

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

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

struct node 

{

    int data;

    struct node* left;

    struct node* right;

};

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

struct node* newNode(int data) 

{

  struct node* node = (struct node*)

                       malloc(sizeof(struct node));

  node->data  = data;

  node->left  = NULL;

  node->right = NULL;

    

  return(node);

}

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

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

{

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

      один узел * /

  if (node == NULL) 

    return(newNode(data));  

  else 

  {

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

    if (data <= node->data) 

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

    else 

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

    

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

    return node; 

  }

}

  
/ * Учитывая непустое двоичное дерево поиска,
вернуть минимальное значение данных, найденное в этом
дерево. Обратите внимание, что все дерево не нужно
быть обысканным. * /

int minValue(struct node* node) {

  struct node* current = node;

  

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

  while (current->left != NULL) {

    current = current->left;

  }

  return(current->data);

}

  

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

int main()

{

  struct node* root = NULL;

  root = insert(root, 4);

  insert(root, 2);

  insert(root, 1);

  insert(root, 3);

  insert(root, 6);

  insert(root, 5);  

  

  printf("\n Minimum value in BST is %d", minValue(root));

  getchar();

  return 0;    

}

Джава

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

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

class Node {

  

    int data;

    Node left, right;

  

    Node(int d) {

        data = d;

        left = right = null;

    }

}

  

class BinaryTree {

  

    static Node head;

      

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

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

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

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

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

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

    Node insert(Node node, int data) {

          

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

         один узел * /

        if (node == null) {

            return (new Node(data));

        } else {

              

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

            if (data <= node.data) {

                node.left = insert(node.left, data);

            } else {

                node.right = insert(node.right, data);

            }

  

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

            return node;

        }

    }

  

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

     вернуть минимальное значение данных, найденное в этом

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

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

    int minvalue(Node node) {

        Node current = node;

  

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

        while (current.left != null) {

            current = current.left;

        }

        return (current.data);

    }

      

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

    public static void main(String[] args) {

        BinaryTree tree = new BinaryTree();

        Node root = null;

        root = tree.insert(root, 4);

        tree.insert(root, 2);

        tree.insert(root, 1);

        tree.insert(root, 3);

        tree.insert(root, 6);

        tree.insert(root, 5);

  

        System.out.println("Minimum value of BST is " + tree.minvalue(root));

    }

}

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

питон

# Программа Python для поиска узла с минимальным значением в bst

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

class Node:

  

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

    def __init__(self, key):

        self.data = key

        self.left = None

        self.right = None

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

def insert(node, data):

  

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

    # один узел

    if node is None:

        return (Node(data))

  

    else:

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

        if data <= node.data:

            node.left = insert(node.left, data)

        else:

            node.right = insert(node.right, data)

  

        # Вернуть (неизмененный) указатель узла

        return node

  
"" "Учитывая непустое двоичное дерево поиска,
вернуть минимальное значение данных, найденное в этом
дерево. Обратите внимание, что все дерево не нужно
быть обысканным. «»»

def minValue(node):

    current = node

  

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

    while(current.left is not None):

        current = current.left

  

    return current.data

  
# Драйверная программа

root = None

root = insert(root,4)

insert(root,2)

insert(root,1)

insert(root,3)

insert(root,6)

insert(root,5)

  

print "\nMinimum value in BST is %d"  %(minValue(root))

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

C #

using System;

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

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

public class Node

{

  

    public int data;

    public Node left, right;

  

    public Node(int d)

    {

        data = d;

        left = right = null;

    }

}

  

public class BinaryTree

{

  

    public static Node head;

  

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

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

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

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

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

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

    public virtual Node insert(Node node, int data)

    {

  

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

         один узел * /

        if (node == null)

        {

            return (new Node(data));

        }

        else

        {

  

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

            if (data <= node.data)

            {

                node.left = insert(node.left, data);

            }

            else

            {

                node.right = insert(node.right, data);

            }

  

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

            return node;

        }

    }

  

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

     вернуть минимальное значение данных, найденное в этом

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

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

    public virtual int minvalue(Node node)

    {

        Node current = node;

  

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

        while (current.left != null)

        {

            current = current.left;

        }

        return (current.data);

    }

  

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

    public static void Main(string[] args)

    {

        BinaryTree tree = new BinaryTree();

        Node root = null;

        root = tree.insert(root, 4);

        tree.insert(root, 2);

        tree.insert(root, 1);

        tree.insert(root, 3);

        tree.insert(root, 6);

        tree.insert(root, 5);

  

        Console.WriteLine("Minimum value of BST is " + tree.minvalue(root));

    }

}

  

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

PHP

<?php
// PHP-программа для поиска узла с
// минимальное значение в bst

  
// создаем двоичное дерево

class node 

{

    private $node, $left, $right;

    function __construct($node

    {

        $this->node = $node;

        $left = $right = NULL;

    }

  

    // установить левый узел в дереве

    function set_left($left

    {

        $this->left = $left;

    }

  

    // установить правильный узел в дереве

    function set_right($right

    {

        $this->right = $right;

    }

  

    // получаем левый узел

    function get_left()

    {

        return $this->left;

    }

  

    // получить правильный узел

    function get_right()

    {

        return $this->right;

    }

  

    // получить значение текущего узла

    function get_node()

    {

        return $this->node;

    }

      
}

  
// Найти узел с минимальным значением
// в бинарном дереве поиска

function get_minimum_value($node

{

    / * до последнего левого узла

      получить минимальное значение * /

    while ($node->get_left() != NULL) 

    {

        $node = $node->get_left();

    }

    return $node->get_node();

}

  
// код для создания дерева

$node = new node(4);

$lnode = new node(2); 

$lnode->set_left(new node(1));

$lnode->set_right(new node(3));

$rnode = new node(6);

$rnode->set_left(new node(5));

$node->set_left($lnode);

$node->set_right($rnode);

  

$minimum_value = get_minimum_value($node);

echo 'Minimum value of BST is '

                 $minimum_value;

  
// Этот код добавлен
// Дипика Патхак
?>


Выход:

Minimum value in BST is 1


Сложность времени:
O (n) Наихудший случай случается для наклонных деревьев слева.

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

Ссылки:
http://cslibrary.stanford.edu/110/BinaryTrees.html

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

Найти узел с минимальным значением в бинарном дереве поиска

0.00 (0%) 0 votes