テスト（再帰的設計）からの質問 - ツリー - Java

Question

私は次の2つの質問に答えようとしました。それらはJavaコーステストからのものですが、再帰的なので、おそらく使用する必要がある。

最初は、バイナリツリーのルートを受け取り、treeの最大値を返すメソッドです。 （図Aの例）。

この質問（第二）が失われたラインで唯一の完全な言葉：

public static int maxInTree (Node root) 
{ 
    if (root == null) 
     return 0; 
    if ((root.getLeftSon() == null) && (root.getRightSon() == null)) 
     ______________________ // I think that here: *return 1*; 
    if (root.getLeftSon() == null) 
    return _________________ 
    if (___________ == null) // I think that here: *root.getRightSon()* 
    _______________________________- 
    return max______________________________ 
} 

2つ目の質問は述べています：最初の質問としてではなくソート、バイナリ検索ツリーについて同じことを行います。 はgetNumber（）：あなたが想定できる

public static int maxInSearchTree (Node r) 
{ 
    if (r == null) 
     return 0; 
    if (r.getRightSon() == null) 
     __________________________ 
    return _______________________________ 
} 

は父親を引き抜きにする方法があります。

thnx !!

Answer 1

私はgetNumber（）が（父ではなく）値を与えると仮定します。

public static int maxInTree (Node root) 
{ 
    if (root == null) 
     return 0; 
    if ((root.getLeftSon() == null) && (root.getRightSon() == null)) 
     return root.getNumber(); 
    if (root.getLeftSon() == null) 
     return max(root.getNumber(), maxInTree(root.getRightSon())); 
    if (root.getRightSon() == null) 
     return max(root.getNumber(), maxInTree(root.getLeftSon())); 
    return max(root.getNumber(), 
     max(maxInTree(root.getLeftSon()),maxInTree(root.getRightSon()))); 
} 

public static int maxInSearchTree (Node r) 
{ 
    if (r == null) 
     return 0; 
    if (r.getRightSon() == null) 
     return r.getNumber(); 
    return maxInSearchTree(r.getRightSon()); 
} 

Answer 2

ツリーのレイアウトと望ましい結果について考える必要があります。 いくつかのヒント：

• 何のルートが存在しない場合、子、再帰がある場合、現在のノードの（サブツリーのルート）値
• を返し、子がない場合
• 適切であるものは何でも返します
• そこに木がソートされている場合、右の子の値は常にツリーがソートされていない場合、あなたは、各ノードの値を比較し、最も高い1（max(...)を覚えておく必要があるノードのより大きく、左の子の
• する必要があります）

Answer 3

トーマスは私がすでに言っていたことの多くをカバーして以来、完全な答えではありません。ただし、いくつかの追加のヒント：

ルートノードの左と右の子ノードは、それ自身が左右のサブツリーのルートノードです。これを考慮して、左右のサブツリーの最大値を取得するには、左または右の子を引数として再帰的なmaxInTree(Node node)メソッドを呼び出す必要があります。

順序付けられていないツリーに左または右のサブツリーのみがある場合、最大値はルートノードの値と左または右のサブツリーの最大値のどちらか大きい方です。