Проверка сбалансированности B-дерева: Решение

Опубликовано Jan 17, 2012 в Деревья и графы | 1 коммент.

, ,

Реализовать функцию, которая проверяет, является ли бинарное дерево сбалансированным.

//Структура узла
//    C++                                           C#
struct tree_node                              public class Node
{                                             {
    tree_node* left;                             public Node Left;
    tree_node* right;                            public Node Right;
    int data;                                    public int Data;
}                                              }
//Сигнатура функции на C++
bool isBalanced(tree_node* root) { //...

Посмотрите пост, связанный с этой задачей

Подсказка идеи алгоритма

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

   //ТЕСТОВЫЕ ДАННЫЕ
   //Несбалансированное  дерево
   //                5
   //        3               7
   //    1      4       6        8
   //             10
   //           12  13
   //Сбалансированное  дерево
   //                5
   //        3               7
   //    1      4       6       8
   //             10

Код решения задачи на C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <algorithm>
//----------------------------------------------------------------
 int maxDepth(tree_node* root){
   if (!root) {
    return 0;
   }
   return 1 + max(maxDepth(root->left), maxDepth(root->right));
 }
 
 int minDepth(tree_node* root) {
   if (!root) {
     return 0;
   }
   return 1 + min(minDepth(root->left), minDepth(root->right));
 }
 
 bool isBalanced(tree_node* root){
   return (maxDepth(root) - minDepth(root) <= 1);
 }


Автор публикации: