打印二叉搜索树直径对应节点组成的路径

Question

我知道如何找到二叉搜索树的直径。

int diameter(struct node * tree)
{

if (tree == 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));
}




int height(struct node* node)
{

if(node == NULL)
   return 0;


return 1 + max(height(node->left), height(node->right));
}

我需要在代码中做出哪些改变，才能按照从一片叶子节点到另一片叶子节点的顺序，打印路径即树的直径对应的节点。

例如：

                     8
                   /  \
                  1    12
                  \     /
                   5   9
                 /   \
                4     7
                     /
                    6

输出应该是6 7 5 1 8 12 9。

- Sumit Kumar Saha

---

出于好奇，如何定义二叉树的“直径”？（它们是否有“直径”？） - Thomas Matthews

请访问@Thomas Matthews (http://www.geeksforgeeks.org/archives/5687) 了解更多关于BST直径的信息。 - Sumit Kumar Saha

Answer 1

这里有一种寻找二叉树最大深度的算法：

1. 定义一个名为max_height的变量。
2. 将其初始化为0。
3. 定义一个名为depth的变量。
4. 将depth初始化为0。
5. 遍历子树时，将depth递增。
6. 如果depth大于max_height，则将max_height设置为depth。
7. 从子树返回时，将depth递减。

这假设读者知道如何遍历二叉树。这是另一篇文章的主题。

- Thomas Matthews

---

我知道如何找到二叉树的最大深度，现在需要做的是打印由BST直径对应节点组成的路径。 - Sumit Kumar Saha

我知道如何找到二叉树的最大深度，我想打印由BST直径对应节点组成的路径。这条路径包括最大深度，其中一些节点在这个最大深度路径上将成为树的直径的一部分。从树的直径中，我可以找到直径的中心，它将位于距离根节点最大深度路径上的(D-floor(M/2))距离处，其中D-最大深度路径上的节点数，M-树的直径。 - Sumit Kumar Saha

当您确定直径时，您能否打印节点：geeksforgeeks.org/archives/5687 - Thomas Matthews

Answer 2

struct node
{    
node* left,right;
int data;
};
struct path
{
node *nodepointer;
int length;
};
int flag=0;

node *x,*y,*lca;

path *printpath(node *leaf,int d)
{
if(flag==0)
{
    path *dia= new path;
    dia->length=0;
    dia->nodepointer=NULL;

    if(leaf==NULL)
    return dia;

    path *a=new path;
    path *b=new path;
    a=printpath(leaf->left,d);
    b=printpath(leaf->right,d);


    if(a->length + b->length + 1 == d )
    {
        lca=leaf;
        x=a->nodepointer;
        y=b->nodepointer;
        flag=1;
    }

    dia->length=max(a->length,b->length)+1;

    if(a->length > b->length && a->nodepointer!=NULL)
    {
        dia->nodepointer=a->nodepointer;
    }
    if(b->length >= a->length && b->nodepointer!=NULL)
    {
        dia->nodepointer=b->nodepointer;
    }
    if(a->nodepointer==NULL && b->nodepointer==NULL)
    {
            dia->nodepointer=leaf;
    }

    return dia;

}

}

- Sumit Kumar Saha

---

当你最初调用函数时，“d”是什么？ - Fox

d是树的直径。这是查找BST直径叶节点的公共祖先的代码。 - Sumit Kumar Saha