0

問題: プレオーダー配列が与えられた場合、それを二分探索木に変換します

                 7
           5          9
       3      6    8     10

解決：

ステップ 1: 配列を Stack に変換する

スタックからポップされた最初の要素はルートです。

次の要素と比較し、ルート値より小さい場合は左サブツリーにし、そうでない場合は右サブツリーにします

ここにコードがあります

public class reconstruct{
  public static void main(String[] args){

            Stack s = new Stack();
            Integer[] arr = {7,5,3,6,9,8,10};
            List<Integer> l = Arrays.asList(arr);


            for (int i=arr.length-1; i>=0;i--){
                s.push(arr[i]);
            }

            System.out.println(s);
            Node newone = CreateFromPreOrder(s);
            printInorder(newone);





public static Node CreateFromPreOrder(Stack preOrder) {

            if (!preOrder.isEmpty()) {
                //System.out.println("hel");

            int value = (int) preOrder.pop();




            Node root = new Node(value);
            if (!preOrder.isEmpty()){

            if((int)preOrder.peek()<value){
                root.left=CreateFromPreOrder(preOrder);
            }
            else 
                  root.right = CreateFromPreOrder(preOrder);

        }
            return root;
            }
            else return null;

            } 

public static void printInorder(Node root) {

            if (root!=null){
                printInorder(root.left);
                System.out.print(" " + root.data);
                printInorder(root.right);
            }
        }
    }

Output: [10, 8, 9, 6, 3, 5, 7] 3 6 8 10 9 5 7

出力は、予期される順序配列ではありません。上記のロジックの何が問題なのかわかりません。

4

2 に答える 2

2

コードを詳しく読んでいませんが、あなたの説明から、次のステートメントは間違っています。

スタックからポップされた最初の要素はルートです。

次の要素と比較し、ルート値より小さい場合は左サブツリーにし、そうでない場合は右サブツリーにします

次の状況を考慮してください。

     7
   5
 3

ここで、6 を挿入します。あなたによると、ツリーは次のようになります。

     7
   5
 3
  6

入力配列を逆にすると、この時点で同じ状況に直面します。

     10
8
   9
  6

これは有効な二分探索木ではありません。これを機能させるには、ツリーを遡ってトラバースし、BST 不変条件を検証する必要があります。

ツリーを元のツリーに 1:1 で再構築する場合は、ノードを配列内と同じ順序でツリーに追加するだけです。それができるのは、予約注文構造だからです。

于 2013-11-09T00:17:51.407 に答える