0

BSTの直径を見つけるプログラムを作成しました...見つけた最大直径のノード（root.data）を印刷する方法について誰かにアイデアを教えてもらえますか？

private int maxDia(Node root) {
    if(root==null) {
        return 0;
    }
    else{

        int llen = maxDepth(root.left);
        int rlen = maxDepth(root.right);
        int ldia = maxDia(root.left);
        int rdia = maxDia(root.right);
        return Math.max(llen+rlen+1,Math.max(ldia,rdia));
    }
}

PS：最大深度は木の高さを調べます。

ありがとう

4

2 に答える 2

0 
 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;

}

}
于 2013-02-17T20:42:04.277 に答える
0

擬似コード:

printDia(root):
    if diameter goes through root:
        printFromDeepest(root.left)
        print(root)
        printToDeepest(root.right)
    else if diameter is in root.left:
        printDia(root.left)
    else:
        printDia(root.right)
于 2013-02-16T19:48:49.480 に答える