Центр Бинарного Дерева

Question

Как мы можем найти центр бинарного дерева?Какой должен быть самый эффективный алгоритм.Хотя центр бинарного дерева будет средней точкой пути, соответствующей диаметру дерева.Мы можем найти диаметр дерева, фактически не зная пути, есть ли подобная техника для нахождения центра бинарного дерева?

Answer 1

Если вы знаете диаметр: D

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

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

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

РЕДАКТИРОВАТЬ:

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

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

Получение MD / 2nth от корня - это то же самое, что говорить D / 2nth с листа самого длинного пути.

Достаточно ли я ясен?Возможно, вы просто захотите нарисовать это, чтобы проверить.

Answer 2

Вы можете рассчитать это за линейное время 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. Я понимаю, что использование функций копирования не является самым быстрым подходом, но я хотел быть более понятным, чем делать что-то более быстрое, но с слишком большим поворотом указателя.

Answer 3

Optimized implementation: The above implementation can be optimized by calculating the    
height in the same recursion rather than calling a height() separately.
/*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));
}
Time Complexity: O(n)