c++ - BSTの直径に対応するノードで構成されるパスを印刷します

Question

BSTの直径を見つける方法を知っています。

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));
}

パスを印刷するには、コードにどのような変更を加える必要がありますか。つまり、ツリーの直径に対応するノードを、直径の1つのリーフノードから別のリーフノードに順番に出力します。

例えば：-

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

出力は675 1 8129である必要があります

Answer 1

二分木の最大深さを求めるアルゴリズムは次のとおりです。

1. という変数があるとしmax_heightます。
2. ゼロに初期化します。
3. という変数があるとしますdepth。
4. ゼロに初期化depthします。
5. サブツリーをトラバースするときは、 をインクリメントしますdepth。
6. depthより大きい場合はmax_height、 に設定max_heightし depthます。
7. サブツリーから戻るときは、デクリメントしますdepth。

これは、読者が二分木をトラバースする方法を知っていることを前提としています。これは別の投稿のトピックです。

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;

}

}