二叉树的中心

Question

我们如何找到二叉树的中心？ 什么是最有效的算法。虽然二叉树的中心将是与树的直径相对应的路径的中点。我们可以在不知道路径的情况下找到树的直径，是否有类似的技术可以找到二叉树的中心？

Answer 1

如果您知道直径：D

并且知道树的最大深度：M

那么您的中心将位于最深路径上的第 (M-(D/2)) 个节点（从根开始）。（可能是M - (D-1)/2 取决于奇偶校验，您需要自行检查）

如果从根到叶有超过 1 条具有 M 个节点的路径，则中心是根。 （仅当最长路径穿过根时才正确）

编辑：

回答您的评论。

如果没有贯穿根部。让我们取直径上的第 D/2 个节点，它仍然位于直径路径的最长一侧（在所有情况下都是从根到叶的最长路径）。因此MD/2仍然从根本上代表了这一点。

从根开始取 MD/2n 与从最长路径的叶子开始取 D/2n 是一样的。

我说得够清楚吗？您可能只想绘制它来检查它。

Answer 2

如果您使用递归方法，通过使用树的高度计算直径 (在此处查看此网站）。

例如，调整我上面发布的链接中的线性时间直径函数，以便您还可以收集您访问过的节点的列表，而不仅仅是距离信息。在每次递归调用中，您将选择与较长遍历距离相关的列表。代表树直径的列表的中间将是树的“中心”。

您的设置如下所示：

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 结构成员中返回一系列指针，可用于循环并查找将成为该路径“中心”的中间节点。树。

PS 我知道利用复制函数并不是最快的方法，但我想更清楚，而不是制作更快但有太多指针旋转的东西。

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)