4

私は次の木を与えられました：

元の木

そして、3つの実装を変更するためにlast-child /previous-siblingメソッドを使用するように指示されました。その結果、次のようになりました。

最後の子/前の兄弟メソッドの後のツリー

私は現在、このツリーでさまざまな機能を実行するためのJava実装に取り​​組んでいます。TreeインターフェースとTreeNodeインターフェースがあります。それらは両方とも、私たちが記入する多くの機能を持っています。

ノードは次のように作成されます。

MyTreeNode a = new MyTreeNode ("a");

ツリーは次のように（ルートを使用して）作成されます。

MyTree     tree = new MyTree (a);

そして最後に、ノードには兄弟の子が与えられます。

e.setChild(j);
e.setSibling(d);

setChild、setSibling、getNextSibling、getFirstChild、およびgetChildrenのメソッドはすでに作成しました。たとえば、これはgetChildrenのコードです。

public List getChildren ()
{
    List <MyTreeNode> children = new ArrayList <MyTreeNode> ();

    MyTreeNode x = this.child;

    children.add(x);

    while (x != null && x.sibling != null) {
        x = x.sibling;
        children.add(x);
    }

    return children;
}

高さ、深さ、ノードのサブツリーのサイズ、getPreOrder、getPostOrder、およびツリーサイズのメソッドを作成する方法が完全にわかりません。

ツリーがこの異なる表現になっているため、ノードの高さまたは深さをチェックする再帰メソッドを作成する方法がわかりません。通常、私が理解しているように、左/右のサブツリーを再帰的にチェックしますが、現在は何もありません（私が見る限り）。私が考えることができる唯一の方法は、多くのifステートメントとwhileループを使用して、すべてのノードをループすることです。しかし、それが最善の方法ではありません。

このツリーの実装を使用して、これらのメソッドを再帰的に作成するにはどうすればよいですか？

また、ノードはまったく一緒に保存されていないため、ツリー全体の詳細を取得する方法がわかりません。これらは上記の方法で実装されているため、すべてのノードに関するデータをまとめて収集する方法がわかりません。

ツリー全体として、すべてのノードでツリーサイズ、isEmpty、makeEmptyなどのメソッドを作成するにはどうすればよいですか？

過度に冗長な説明でごめんなさい。

4

1 に答える 1

2

ツリーに次のようなノード構造があると仮定します。

public class Node{
   String nodeName;

   Node left;
   Node right;

   public Node(String nodeName, Node left, Node right){
     this.nodeName = nodeName;
     this.left     = left;
     this.right= right;
   }
}

新しいツリーを構築する方法について、私は次のように考えています。ツリーに新しいノードを追加する場合でも、ツリー構造は維持されます。ノードをツリーに追加する方法に応じて、引き続き親の左側または右側に追加します。

新しいツリーを視覚化する 1 つの可能な方法は、次のようなものです。

                A
               /
              E
            /   \
           D     J
         /   \   / \
        C    H  I   K
       /
      B
     /
    G
   /    
  F

注: ここでは、子が 1 人の場合、親の左側に追加されると想定しています。しかし、これは理想的にはあなたの要件に依存します

このツリーをこのように視覚化できる場合、高さ、前順、後順トラバーサルを取得するための再帰関数は同じままです。

さらにいくつかのヒント:

  • 兄弟の追加は、ノードの親の左または右にノードを追加するようなものです。つまり、現在のノードがその親の左にある場合、新しいノードを右に追加します。

  • 子の追加は同じままです。ロジックに応じて、新しいノードを現在のノードの左の子または右の子として追加します。

于 2012-09-18T00:59:49.810 に答える