нахождение два большинство удаленных элементов в двоичном дереве
Я ищу алгоритм, который мог найти два большинство удаленных элементов в двоичном дереве, не ища специального языка, только для алгоритма.
Спасибо.
3 ответа
Это называется диаметр дерева.
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));
}
То, что вы ищете, можно назвать диаметром графика . Чтобы получить его, вам нужно вычислить путь от одной вершины к любой другой, а затем пройти все их и найти самую большую.
Этого можно достичь, используя алгоритм Дейкстры или просто матрицу расстояний (что может быть достигнуто путем включения матрицы смежности ), хотя это займет больше времени, чем алгоритм Дейкстры.
Поскольку это дерево, существует только один путь между любой парой вершин. Это облегчает нам поиск диаметра графика.
Самый простой способ сделать это - выполнить два простых обхода дерева. Сначала возьмите любой произвольный узел в качестве корня и вычислите расстояния каждой вершины от него, используя простой DFS / BFS. Теперь возьмите узел, который находится дальше всего от корня (это первый узел самой удаленной пары), и, сделав его новым корнем, выполните еще один обход дерева, вычисляя расстояния оттуда. Самый удаленный от него узел - это другой узел пары.
Доказательство того, почему это работает, оставлено в качестве упражнения.
Существует также другой способ вычисления наиболее удаленной пары путем вычисления и сравнения наиболее удаленных пар для каждого поддерева дерева, начиная с произвольного узла в качестве корня (уже упомянутого в другом ответе).