Найти диаметр дерева, если для каждого узла указан родительский указатель

Question

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

How do we find diameter of a binary tree if parent pointer to each node is given. 

Definition of tree diameter is : Longest distance between two nodes of tree. 

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

структура узел выглядит следующим образом класс Node {Node влево; Узел справа; Узел parentPointer; данные int;

}

Answer 1

Просьба уточнить, какой родительский указатель должен иметь диаметр. Если вы определяете диаметр как максимальное расстояние между любыми двумя узлами, чем не имеет значения, какой узел является назначенным родителем. Если, с другой стороны, существует различие, например, родительский узел является источником, а другие узлы - стоками, то вы, вероятно, ищете максимальные расстояния от любого узла до источника, а не от диаметра дерева.

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

Если, с другой стороны, вы ищете двойной диаметр дерева BFS дважды: 1-й старт от любого узла, который вам нравится, и найдите самый дальний; затем начните с самого дальнего узла и найдите самого дальнего от него. Так получилось, что расстояние от «самого дальнего узла от любого данного узла» до «самого дальнего узла от самого дальнего, которое вы только что нашли» дает вам диаметр дерева.

Answer 2

Этот код из geeksforgeeks показывает, как можно вычислить диаметр двоичного времени в O (N).

Однако, нет необходимости в указателе родителя, поэтому, возможно, я неправильно понял ваш вопрос?

/*The second parameter is to store the height of tree. 
    Initially, we need to pass a pointer to a location with value 
    as 0. So, function should be used as follows: 

    int height = 0; 
    struct node *root = SomeFunctionToMakeTree(); 
    int diameter = diameterOpt(root, &height); */ 
int diameterOpt(struct node *root, int* height) 
{ 
    /* lh --> Height of left subtree 
     rh --> Height of right subtree */ 
    int lh = 0, rh = 0; 

    /* ldiameter --> diameter of left subtree 
     rdiameter --> Diameter of right subtree */ 
    int ldiameter = 0, rdiameter = 0; 

    if(root == NULL) 
    { 
    *height = 0; 
    return 0; /* diameter is also 0 */ 
    } 

    /* Get the heights of left and right subtrees in lh and rh 
    And store the returned values in ldiameter and ldiameter */ 
    ldiameter = diameterOpt(root->left, &lh); 
    rdiameter = diameterOpt(root->right, &rh); 

    /* Height of current node is max of heights of left and 
    right subtrees plus 1*/ 
    *height = max(lh, rh) + 1; 

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

Answer 3

http://leisurehours.wordpress.com/2009/07/18/find-the-diameter-of-a-tree/

Предполагая, что задано указатель на любом узле дерева.

Сделайте BFS (поиск по ширине первого) на данном узле и найдите узел, имеющий максимальное расстояние от данного узла. Узел, имеющий максимальное расстояние от данного узла, будет листовым узлом. Давайте назовем его node1 Теперь снова примените BFS на узле1 и найдите максимальное расстояние любого узла от узла1. Это расстояние - диаметр дерева. Поскольку node1 является листом дерева, а BFS находит кратчайшее расстояние от node1 (лист) до всех других узлов в дереве. Очевидно, что узел, наиболее удаленный от node1, будет листом, и, следовательно, мы получим диаметр дерева.