Рубрики

Диаметр бинарного дерева

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

Диаметр дерева Т является наибольшим из следующих величин:

* диаметр левого поддерева Т
* диаметр правого поддерева Т
* самый длинный путь между листьями, который проходит через корень T (это может быть вычислено из высот поддеревьев T)

Реализация:

С

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

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

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

struct node

{

    int data;

    struct node* left, *right;

};

  
/ * функция для создания нового узла дерева и возврата указателя * /

struct node* newNode(int data);

  
/ * возвращает максимум двух целых чисел * /

int max(int a, int b);

  
/ * функция для вычисления высоты дерева. * /

int height(struct node* node);

  
/ * Функция для получения диаметра бинарного дерева * /

int diameter(struct node * tree)

{

   / * базовый случай, когда дерево пусто * /

   if (tree == NULL)

     return 0;

  

  / * получить высоту левого и правого поддерева * /

  int lheight = height(tree->left);

  int rheight = height(tree->right);

  

  / * получить диаметр левого и правого поддерева * /

  int ldiameter = diameter(tree->left);

  int rdiameter = diameter(tree->right);

  

  / * Вернуть максимум следующих трех

   1) диаметр левого поддерева

   2) диаметр правого поддерева

   3) Высота левого поддерева + высота правого поддерева + 1 * /

  return max(lheight + rheight + 1, max(ldiameter, rdiameter));

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ ДЛЯ ИСПЫТАНИЯ диаметр () ФУНКЦИЯ * /

  
/ * Функция вычисляет «высоту» дерева. Высота это

    число f узлов по самому длинному пути от корневого узла

    вплоть до самого дальнего листового узла. * /

int height(struct node* node)

{

   / * базовое дерево пусто * / 

   if(node == NULL)

       return 0;

  

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

      высота и правая высота * /    

   return 1 + max(height(node->left), height(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);

}

  
/ * возвращает максимум два целых числа * /

int max(int a, int b)

{

  return (a >= b)? a: b;

}    

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

int main()

{

  

  / * Построенное двоичное дерево

            1

          / /

        2 3

      / /

    4 5

  * /

  struct node *root = newNode(1);

  root->left        = newNode(2);

  root->right       = newNode(3);

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

  root->left->right = newNode(5);

  

  printf("Diameter of the given binary tree is %d\n", diameter(root));

  

  getchar();

  return 0;

}

Джава

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

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

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

class Node

{

    int data;

    Node left, right;

  

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  
/ * Класс для печати Диаметра * /

class BinaryTree

{

    Node root;

  

    / * Метод расчета диаметра и возврата его в основную * /

    int diameter(Node root)

    {

        / * базовый случай, если дерево пусто * /

        if (root == null)

            return 0;

  

        / * получить высоту левого и правого поддеревьев * /

        int lheight = height(root.left);

        int rheight = height(root.right);

  

        / * получаем диаметр левого и правого поддеревьев * /

        int ldiameter = diameter(root.left);

        int rdiameter = diameter(root.right);

  

        / * Вернуть максимум следующих трех

          1) диаметр левого поддерева

         2) диаметр правого поддерева

         3) Высота левого поддерева + высота правого поддерева + 1 * /

        return Math.max(lheight + rheight + 1,

                        Math.max(ldiameter, rdiameter));

  

    }

  

    / * Оболочка по диаметру (корень узла) * /

    int diameter()

    {

        return diameter(root);

    }

  

    / * Функция вычисляет «высоту» дерева. Высота это

      число f узлов по самому длинному пути от корневого узла

      вплоть до самого дальнего листового узла. * /

    static int height(Node node)

    {

        / * базовое дерево пусто * /

        if (node == null)

            return 0;

  

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

           высота и правая высота * /

        return (1 + Math.max(height(node.left), height(node.right)));

    }

  

    public static void main(String args[])

    {

        / * создание бинарного дерева и ввод узлов * /

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(1);

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

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

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

        tree.root.left.right = new Node(5);

  

        System.out.println("The diameter of given binary tree is : "

                           + tree.diameter());

    }

}

питон

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

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

class Node:

  

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

    def __init__(self, data):

        self.data = data

        self.left = None

        self.right = None

  

  
«»»
Функция вычисляет «высоту» дерева. Высота это
число f узлов по самому длинному пути от корневого узла
до самого дальнего листового узла.
«»»

def height(node):

      

    # Базовый случай: дерево пусто

    if node is None:

        return 0 ;

      

    # Если дерево не пустое, то высота = 1 + максимум слева

    # высота и правая высота

    return 1 + max(height(node.left) ,height(node.right))

  
# Функция для получения диаметра двоичного дерева

def diameter(root):

      

    # Базовый случай, когда дерево пусто

    if root is None:

        return 0;

  

    # Получить высоту левого и правого поддеревья

    lheight = height(root.left)

    rheight = height(root.right)

  

    # Получить диаметр левого и нижнего деревьев

    ldiameter = diameter(root.left)

    rdiameter = diameter(root.right)

  

    # Вернуть максимум следующего дерева:

    # 1) Диаметр левого поддерева

    # 2) Диаметр правого поддерева

    # 3) Высота левого поддерева + высота правого поддерева +1

    return max(lheight + rheight + 1, max(ldiameter, rdiameter))

      

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

  
«»»
Построенное двоичное дерево

            1

          / /

        2 3

      / /

    4 5

«»»

  

root = Node(1)

root.left = Node(2)

root.right = Node(3)

root.left.left = Node(4)

root.left.right = Node(5)

print "Diameter of given binary tree is %d" %(diameter(root))

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


Сложность времени: O (n ^ 2)

Выход:

Diameter of the given binary tree is 4

Оптимизированная реализация: вышеуказанную реализацию можно оптимизировать, вычисляя высоту в одной и той же рекурсии, а не вызывая height () по отдельности. Спасибо Амару за предложение этой оптимизированной версии. Эта оптимизация уменьшает сложность времени до O (n).

С

/ * Второй параметр - хранить высоту дерева.

   Изначально нам нужно передать указатель на местоположение со значением

   как 0. Итак, функцию следует использовать следующим образом:

  

   int height = 0;

   struct node * root = SomeFunctionToMakeTree ();

   int диаметр = диаметрOpt (корень, & высота); * /

int diameterOpt(struct node *root, int* height)

{

  / * lh -> Высота левого поддерева

     rh -> Высота правого поддерева * /

  int lh = 0, rh = 0;

   

  / * ldiameter -> диаметр левого поддерева

     rdiameter -> диаметр правого поддерева * /

  int ldiameter = 0, rdiameter = 0;

   

  if(root == NULL)

  {

    *height = 0;

     return 0; / * диаметр тоже 0 * /

  }

   

  / * Получить высоты левого и правого поддеревьев в lh и rh

    И сохраните возвращенные значения в ldiameter и ldiameter * /

  ldiameter = diameterOpt(root->left, &lh);

  rdiameter = diameterOpt(root->right, &rh);

   

  / * Высота текущего узла - максимум высот слева и

     правильные поддеревья плюс 1 * /

  *height = max(lh, rh) + 1;

   

  return max(lh + rh + 1, max(ldiameter, rdiameter));

}

Джава

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

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

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

class Node

{

    int data;

    Node left, right;

  

    public Node(int item)

    {

        data = item;

        left = right = null;

    }

}

  
// Сервисный класс для передачи объекта высоты

class Height

{

    int h;

}

  
/ * Класс для печати Диаметра * /

class BinaryTree

{

    Node root;

  

    / * определить height = 0 глобально и вызвать диаметрOpt (корень, высота)

       от основного * /

    int diameterOpt(Node root, Height height)

    {

        / * lh -> Высота левого поддерева

           rh -> Высота правого поддерева * /

        Height lh = new Height(), rh = new Height();

  

        if (root == null)

        {

            height.h = 0;

            return 0; / * диаметр тоже 0 * /

        }

          

        / * ldiameter -> диаметр левого поддерева

           rdiameter -> диаметр правого поддерева * /  

        / * Получить высоты левого и правого поддеревьев в lh и rh

         И сохраните возвращенные значения в ldiameter и ldiameter * /

        int ldiameter = diameterOpt(root.left, lh);

        int rdiameter = diameterOpt(root.right, rh);

  

        / * Высота текущего узла - максимум высот слева и

         правильные поддеревья плюс 1 * /

        height.h = Math.max(lh.h, rh.h) + 1;

  

        return Math.max(lh.h + rh.h + 1, Math.max(ldiameter, rdiameter));

    }

  

    / * Оболочка по диаметру (корень узла) * /

    int diameter()

    {

        Height height = new Height();

        return diameterOpt(root, height);

    }

  

    / * Функция вычисляет «высоту» дерева. Высота это

      число f узлов по самому длинному пути от корневого узла

      вплоть до самого дальнего листового узла. * /

    static int height(Node node)

    {

        / * базовое дерево пусто * /

        if (node == null)

            return 0;

  

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

           высота и правая высота * /

        return (1 + Math.max(height(node.left), height(node.right)));

    }

  

    public static void main(String args[])

    {

        / * создание бинарного дерева и ввод узлов * /

        BinaryTree tree = new BinaryTree();

        tree.root = new Node(1);

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

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

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

        tree.root.left.right = new Node(5);

  

        System.out.println("The diameter of given binary tree is : "

                           + tree.diameter());

    }

}


Сложность времени: O (n)
Выход:

 4 
  1. Диаметр двоичного дерева в O (n) [Новый метод]
  2. Диаметр н-арного дерева

Ссылки:
http://www.cs.duke.edu/courses/spring00/cps100/assign/trees/diameter.html

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

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

Диаметр бинарного дерева

0.00 (0%) 0 votes