0

各ノードに単語がある二分木があります。

別のクラスでは、ノードに1つずつアクセスしてから、単語を操作する必要があります。別のクラスからノードに1つずつアクセスするための最良の方法は何ですか？

私のBinaryTreeクラスでは、各ノードに左子、右子、およびvalue（String）があります。printinorder、insert、findnodeの3つのメソッドがあります。検索ノードは文字列を受け取り、その文字列がノード値のいずれかに格納されているかどうかを確認します。

public void printInOrder(Node node) {
    if (node != null) {
        printInOrder(node.left);
        System.out.println(node.value);
        printInOrder(node.right);
    }

別のクラスがあり、ノードを1つずつ取得する必要がありますが、別のクラスからそれを行うための最良の方法がわかりません。クラス内からツリーをトラバースすることはできますが、別のクラスからはトラバースできません。

4

4 に答える 4

1

バイナリツリー内のすべてのノードをウォークオーバーする1つの方法は、次の手順を実行することです。これにより、左端のノードが開始され、現在のノードの順序どおりの後続ノードに繰り返し移行されます。

  1. 木から落ちずにできるだけ左に歩くことから始めます。これが最初のノードです。

  2. あるノードから訪問する必要のある次のノードに移動するには、次のようにします。

    1. ノードに右の子がある場合は、右の子に降りてから、可能な限り左の子に続けて降ります。次に訪問するノードで終了します。
    2. それ以外の場合は、左の子からその親までエッジを上るまで、ノードからその親まで上向きに繰り返し歩きます。最終的には新しいノードになります。

これは、すべてのノード間でO（n）時間しかかからないため、ノード間を移行するための非常に高速な方法です。

これが機能するためには、各ノードに親ポインターを格納させるか、開始ノードから現在のノードまでのノードのパスのスタックを維持する必要があります。ただし、適度にバランスの取れたツリーの場合、これは、ツリー内のノードのリスト全体を入力して返すよりもはるかにスペース効率が高くなります。

お役に立てれば！

于 2013-01-11T00:31:43.413 に答える
0

ツリークラスがあると仮定して、最初にツリーをトラバースするメソッドを最初に記述します（幅/深さ検索）。トラバーサルのすべてのノードで、ノードがその変数の1つに単語を保持するある種のオブジェクトであると想定して、ノードにアクセスし、保存されている単語を変更します。基本的に、これを可能にする関数をBinary Treeクラスに記述し、それらを他のクラスで呼び出します。

于 2013-01-10T23:51:10.920 に答える
0

検索用：

ツリーを二分探索木に並べ替えることができます。または、ツリーを構築するときに、バイナリ検索ツリーを構築します。検索するのに最適な方法です。O(logn)。

検索はfindNode(String value)メソッドに実装する必要があります

または、検索の実装に問題がありますか？

于 2013-01-11T00:20:09.457 に答える
0

より効率的なアプローチであるtemplatetypedefの答えを読んでください。私が提示するアプローチの利点は、既存のNodeクラスに変更を加える必要がなく、PrintInOrderにすでに使用したのと同じパターンを使用することです。Nodeクラスのパブリックプロパティのみに依存しているため、別のクラスから使用できる必要があります。

public List<Node> nodes GetAllNodes(Node root) {
    List<Node> nodes = new ArrayList<Node>();
    if (root != null) {
        nodes.addAll(GetAllNodes(root.left));
        nodes.add(root);
        nodes.addAll(GetAllNodes(root.right));
    }
    return nodes;
}

これをコンパイルまたはテストしなかったため、エラーが発生する可能性があります。

于 2013-01-11T00:30:35.310 に答える