5

配列インデックスごとにツリーをトラバースすることなく Binary をソート済み配列に変換する方法はありますか?

Node root;
Node runner;
int current_smallest;

void findsmallest(Node root){
    //Pre-order traversal
    if(root == null){
        return;
    }else{
        runner = root;
        if(current_smallest == null){
            current_smallest = runner.element;
        }else{
            if(current_smallest > runner.element){
            current_smallest = runner.element;
            }
        }
        findsmallest(runner.left);
        findsmallest(runner.right);
    }   
}

void fill_array( int [] array ){

    for(int i =0; i < array.length(); i++){
        findsmallest(root);
        array[i] = current_smallest;
    }
}

ご覧のとおり、ツリーに多数のノードがある場合、これには長い時間がかかることがあります。ところで、配列の長さを取得するには、最初にツリー全体を走査する必要があることを示すのを忘れていました。

4

4 に答える 4

17

はい、それを行うことができます:ツリーの順序どおりのトラバーサルを実行し、配列の現在の位置を保持し、ノードの値を配列の現在の位置に格納します。

順序通りのトラバーサルを再帰的に行うことも、スタック データ構造を使用して行うこともできます。再帰的に実行したい場合は、次のようにします。

int fill_array(Node root, int [] array, int pos) {
    if (root.left != null) {
        pos = fill_array(root.left, array, pos);
    }
    array[pos++] = root.element;
    if (root.right != null) {
        pos = fill_array(root.right, array, pos);
    }
    return pos; // return the last position filled in by this invocation
}

上記の再帰的な手順が機能するためには、呼び出し元arrayが関数に渡される十分なスペースを割り当てる必要があることに注意してください。

于 2013-04-23T23:04:42.790 に答える
4

必要なのは、通常は次のように再帰的に実装される順序通りのトラバーサルです。

  • 左のサブツリーをトラバースします。
  • このノードを処理します (つまり、配列の次の要素として挿入します)
  • 右部分木をトラバースします。
于 2013-04-23T23:04:35.090 に答える
4

二分木は配列で表すことができます。この場合、配列をソートするだけで済みます。

配列内のツリーの表現に関する詳細情報は次のとおりです: ウィキペディア

これは必ずしも最もスペース効率の良い表現ではありません。「参照のあるノード」表現は、より少ないスペースを浪費する可能性があります。

于 2013-04-23T23:02:55.857 に答える