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

Question

Я ищу алгоритм, который мог бы найти два самых удаленных элемента в двоичном дереве, не ища никакого специального языка, только для алгоритма.

Спасибо.

Answer 1

Это называется диаметр дерева .

int diameter(Tree * t) // post: return diameter of t 
{ 
     if (t == 0) return 0; 
     int lheight = height(tree->left); 
     int rheight = height(tree->right);
     int ldiameter = diameter(tree->left); 
     int rdiameter = diameter(tree->right); 
     return max(lheight + rheight + 1, max(ldiameter,rdiameter));
 } 

скопированный код и изображения отсюда .

Answer 2

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

Answer 3

Поскольку это дерево, между любой парой вершин существует только один путь. Это облегчает нам поиск диаметра графика.

Самый простой способ сделать это - сделать два простых обхода дерева. Сначала возьмем любой произвольный узел в качестве корня и вычислим расстояния от него до каждой вершины, используя простую DFS / BFS. Теперь возьмем самый дальний от корня узел (это первый узел самой удаленной пары) и, сделав его новым корнем, выполните еще один обход дерева, вычисляя расстояния от него. Самый удаленный узел от этого - другой узел пары.

Доказательство того, почему это работает, оставлено в качестве упражнения.

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