Центр бинарного дерева

Если знаешь диаметр :D

и вы знаете максимальную глубину дерева: M

тогда ваш центр будет в (M-(D/2)) узле (от корня) на самом глубоком пути (это может быть M - (D-1)/2 в зависимости от четности, вам нужно проверить себя )

Если у вас есть более одного пути от корня к листу с M узлами, то центр является корнем. (верно только тогда, когда самый длинный путь проходит через корень)

ИЗМЕНИТЬ:

Чтобы ответить на ваше замечание.

если не через корень. Давайте возьмем D/2-й узел на диаметре, он все еще будет на самой длинной стороне пути диаметра (что во всех случаях является самым длинным путем от корня к листу). и поэтому M-D/2 по-прежнему представляют эту точку от корня.

Взять M-D/2nth из корня — это то же самое, что произнести D/2nth из листа самого длинного пути.

Я достаточно ясен? Вы могли бы просто хотеть нарисовать это, чтобы проверить это.

Вы можете вычислить это за линейное время O(N), сохранив список узлов, которые вы прошли, если вы используете рекурсивный метод, в котором вы вычисляете диаметр, используя высоту дерева (см. этот сайт здесь).

Например, адаптируйте функцию diameter с линейным временем по ссылке, которую я разместил выше, чтобы вы также собирали список посещенных вами узлов, а не только информацию о расстоянии. При каждом рекурсивном вызове вы будете выбирать список, соответствующий более длинному пройденному расстоянию. Середина списка, представляющая диаметр дерева, будет «центром» дерева.

Ваша установка будет выглядеть следующим образом:

typedef struct linked_list
{
    tree_node* node;
    linked_list* next;
} linked_list;

typedef struct list_pair
{
    linked_list* tree_height;
    linked_list* full_path;
} list_pair;

//some standard functions for working with the structure data-types
//they're not defined here for the sake of brevity
void back_insert_node(linked_list** tree, tree_node* add_node);
void front_insert_node(linked_list** tree, tree_node* add_node);
int list_length(linked_list* list);
void destroy_list(linked_list* list);
linked_list* copy_list(linked_list* list);
linked_list* append_list(linked_list* first, linked_list* second);

//main function for finding the diameter of the tree
list_pair diameter_path(tree_node* tree)
{
    if (tree == NULL)
    {
        list_pair return_list_pair = {NULL, NULL};
        return return_list_pair;
    }

    list_pair rhs = diameter_path(tree->right);
    list_pair lhs = diameter_path(tree->left);

    linked_list* highest_tree = 
           list_length(rhs.tree_height) > list_length(lhs.tree_height) ? 
                                      rhs.tree_height : lhs.tree_height;

    linked_list* longest_path =
           list_length(rhs.full_path) > list_length(lhs.full_path) ?
                                      rhs.full_path : lhs.full_path;

    //insert the current node onto the sub-branch with the highest height
    //we need to make sure that the full-path, when appending the 
    //rhs and lhs trees, will read from left-to-right
    if (highest_tree == rhs.tree_height)
        front_insert_node(highest_tree, tree);
    else
        back_insert_node(highest_tree, tree);

    //make temporary copies of the subtrees lists and append them to 
    //create a full path that represents a potential diameter of the tree
    linked_list* temp_rhs = copy_list(rhs.tree_height);
    linked_list* temp_lhs = copy_list(lhs.tree_height);
    linked_list* appended_list = append_list(temp_lhs, temp_rhs);

    longest_path =
           list_length(appended_list) > list_length(longest_path) ?
                                      appended_list : longest_path;

    list_pair return_list_pair;
    return_list_pair.tree_height = copy_list(highest_tree);
    return_list_pair.full_path = copy_list(longest_path);

    destroy_list(rhs.tree_height);
    destroy_list(rhs.full_path);
    destroy_list(lhs.tree_height);
    destroy_list(lhs.full_path);

    return return_list_pair;
}

Теперь функция возвращает ряд указателей в элементе структуры full_path, которые можно использовать для циклического поиска среднего узла, который будет «центром» дерева.

P.S. Я понимаю, что использование функций копирования — не самый быстрый подход, но я хотел быть более ясным, а не делать что-то более быстрое, но слишком много манипулирования указателем.