Рубрики

Бинарное дерево | Комплект 1 (Введение)

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

Древовидный словарь: самый верхний узел называется корнем дерева. Элементы, которые находятся непосредственно под элементом, называются его дочерними элементами. Элемент непосредственно над чем-то называется его родителем. Например, «a» является потомком «f», а «f» является родителем «a». Наконец, элементы без дочерних элементов называются листьями.

      tree
      ----
       j    <-- root
     /   \
    f      k  
  /   \      \
 a     h      z    <-- leaves 

Почему деревья?
1. Одной из причин использования деревьев может быть то, что вы хотите хранить информацию, которая естественно образует иерархию. Например, файловая система на компьютере:

file system
-----------
     /    <-- root
  /      \
...       home
      /          \
   ugrad        course
    /       /      |     \
  ...      cs101  cs112  cs113  

2. Деревья (с некоторым порядком, например, BST) обеспечивают умеренный доступ / поиск (быстрее, чем связанный список, и медленнее, чем массивы).
3. Деревья обеспечивают умеренную вставку / удаление (быстрее, чем массивы и медленнее, чем неупорядоченные связанные списки).
4. Как и связанные списки и в отличие от массивов, деревья не имеют верхнего предела числа узлов, поскольку узлы связаны с помощью указателей.

Основные применения деревьев включают в себя:
1. Управляйте иерархическими данными.
2. Сделайте информацию легкой для поиска (см. Обход дерева).
3. Управление отсортированными списками данных.
4. В качестве рабочего процесса для создания цифровых изображений для визуальных эффектов.
5. Алгоритмы маршрутизатора
6. Форма многоэтапного принятия решения (см. Деловые шахматы).

Двоичное дерево: дерево, элементы которого имеют не более 2 дочерних элементов, называется бинарным деревом. Поскольку каждый элемент в двоичном дереве может иметь только 2 дочерних элемента, мы обычно называем их левый и правый дочерние элементы.

Представление двоичного дерева в C: Дерево представлено указателем на самый верхний узел дерева. Если дерево пусто, тогда значение root равно NULL.
Узел дерева содержит следующие части.
1. Данные
2. Указатель на левого ребенка
3. Указатель на правильного ребенка

В C мы можем представить узел дерева, используя структуры. Ниже приведен пример узла дерева с целочисленными данными.

С

struct node 

{

  int data;

  struct node *left;

  struct node *right;

};

питон

# Класс Python, представляющий отдельный узел
# в двоичном дереве

class Node:

    def __init__(self,key):

        self.left = None

        self.right = None

        self.val = key

Джава

/ * Класс, содержащий левого и правого потомка текущего

   значение узла и ключа * /

class Node

{

    int key;

    Node left, right;

  

    public Node(int item)

    {

        key = item;

        left = right = null;

    }

}

C #

/ * Класс, содержащий левого и правого ребенка
текущего узла и значения ключа * /

class Node

{

    int key;

    Node left, right;

  

    public Node(int item)

    {

        key = item;

        left = right = null;

    }

}

Первое простое дерево в C
Давайте создадим простое дерево с 4 узлами в C. Созданное дерево будет выглядеть следующим образом.

      tree
      ----
       1    <-- root
     /   \
    2     3  
   /   
  4

С

struct node 

{

    int data;

    struct node *left;

    struct node *right;

};

  
/ * newNode () выделяет новый узел с данными данными и NULL слева и

   правильные указатели. * /

struct node* newNode(int data)

{

  // Выделим память для нового узла

  struct node* node = (struct node*)malloc(sizeof(struct node));

  

  // Назначаем данные этому узлу

  node->data = data;

  

  // Инициализируем левого и правого потомков как NULL

  node->left = NULL;

  node->right = NULL;

  return(node);

}

  

  

int main()

{

  / * создать root * /

  struct node *root = newNode(1);  

  / * следующее дерево после вышеприведенного утверждения

  

        1

      / /

     НОЛЬ НОЛЬ

  * /

    

  

  root->left        = newNode(2);

  root->right       = newNode(3);

  / * 2 и 3 становятся левыми и правыми детьми 1

           1

         / /

        2 3

     / / / /

    NULL NULL NULL NULL

  * /

  

  

  root->left->left  = newNode(4);

  / * 4 становится левым ребенком от 2

           1

       / /

      2 3

    / / / /

   4 NULL NULL NULL

  / /

НОЛЬ НОЛЬ
* /

  

  getchar();

  return 0;

}

питон

# Программа Python для представления двоичного дерева

  
# Класс, который представляет отдельный узел в
# Двоичное дерево

class Node:

    def __init__(self,key):

        self.left = None

        self.right = None

        self.val = key

  

  
# создать рут

root = Node(1)

'' 'следующее дерево после вышеприведенного утверждения

        1

      / /

     Нет Нет

  

root.left      = Node(2);

root.right     = Node(3);

    
'' '2 и 3 становятся левыми и правыми детьми 1

           1

         / /

        2 3

     / / / /

   Нет Нет Нет Нет '' '

  

  

root.left.left  = Node(4);

'' '4 становится левым ребенком от 2

           1

       / /

      2 3

    / / / /

   4 Нет Нет Нет

  / /

Нет Нет

Джава

/ * Класс, содержащий левого и правого потомка текущего

   значение узла и ключа * /

class Node

{

    int key;

    Node left, right;

  

    public Node(int item)

    {

        key = item;

        left = right = null;

    }

}

  
// Java-программа для представления двоичного дерева

class BinaryTree

{

    // Корень бинарного дерева

    Node root;

  

    // Конструкторы

    BinaryTree(int key)

    {

        root = new Node(key);

    }

  

    BinaryTree()

    {

        root = null;

    }

  

    public static void main(String[] args)

    {

        BinaryTree tree = new BinaryTree();

  

        / * создать root * /

        tree.root = new Node(1);

  

        / * следующее дерево после вышеприведенного утверждения

  

              1

            / /

          ноль ноль */

  

        tree.root.left = new Node(2);

        tree.root.right = new Node(3);

  

        / * 2 и 3 становятся левыми и правыми детьми 1

               1

             / /

            2 3

          / / / /

        null null null null * /

  

  

        tree.root.left.left = new Node(4);

        / * 4 становится левым ребенком от 2

                    1

                / /

               2 3

             / / / /

            4 null null null

           / /

          ноль ноль

         * /

    }

}

C #

// AC # программа для представления бинарного дерева

using System;

  
/ * Класс, содержащий левого и правого ребенка
текущего узла и значения ключа * /

public class Node

{

    public int key;

    public Node left, right;

  

    public Node(int item)

    {

        key = item;

        left = right = null;

    }

}

  

public class BinaryTree

{

    // Корень бинарного дерева

    Node root;

  

    // Конструкторы

    BinaryTree(int key)

    {

        root = new Node(key);

    }

  

    BinaryTree()

    {

        root = null;

    }

  

    // Код драйвера

    public static void Main(String[] args)

    {

        BinaryTree tree = new BinaryTree();

  

        / * создать root * /

        tree.root = new Node(1);

  

        / * следующее дерево после вышеприведенного утверждения

  

            1

            / /

        ноль ноль */

        tree.root.left = new Node(2);

        tree.root.right = new Node(3);

  

        / * 2 и 3 становятся левыми и правыми детьми 1

            1

            / /

            2 3

        / / / /

        null null null null * /

        tree.root.left.left = new Node(4);

          

        / * 4 становится левым ребенком от 2

                    1

                / /

            2 3

            / / / /

            4 null null null

        / /

        ноль ноль

        * /

    }

}

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

Сводка: Дерево представляет собой иерархическую структуру данных. Основное использование деревьев включает поддержание иерархических данных, обеспечение умеренного доступа и операций вставки / удаления. Бинарные деревья — это особые случаи дерева, где каждый узел имеет не более двух дочерних элементов.

Ниже приведены набор 2 и набор 3 этого поста.
Свойства бинарного дерева
Типы бинарного дерева

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

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

Бинарное дерево | Комплект 1 (Введение)

0.00 (0%) 0 votes