1

以下は私のコードです：

class Node{
    int value;
    Node left;
    Node right;
    Node parent;
       //getters, setters
}

ツリーを作成する

    private static void createTree() throws FileNotFoundException{
    Map<String,Node> nodeMap = new HashMap<String,Node>();
    Scanner sc = new Scanner(new File("<location>"));
    int row =0;
    while(sc.hasNextLine()){
        String line = sc.nextLine();
        Scanner scanLine = new Scanner(line);
        System.out.println(line);
        int col =0;

        while(scanLine.hasNextInt()){
            int value = scanLine.nextInt();
            System.out.println(row+","+col+"="+value);
            Node node = new Node(value);
            nodeMap.put(row+","+col,node);
            if(row >0){
                if(col %2 ==0){
                    //left node
                    Node parent = nodeMap.get(row-1+","+col/2);
                    if(parent !=null){
                        node.setParent(parent);
                        parent.setLeft(node);
                    }
                }else{
                    //right node
                    Node parent = nodeMap.get(row-1+","+(col-1)/2);
                    if(parent !=null){
                        node.setParent(parent);
                        parent.setRight(node);
                    }
                }
            }
            col++;
        }
        row++;
    }
    System.out.println(nodeMap);
    Node root = nodeMap.get("0,0");
    traverseTree(root);
    System.out.println("sum="+sum);


}

実際のトラバーサル 

    static int sum =0;
private static void traverseTree(Node n){
    if(n != null){
        sum+=n.value;
        traverseTree(n.left);
        traverseTree(n.right);
    }
}

2 つの質問があります。

  1. 入力を読み取り、ツリーを作成します。ファイルから読み取り、ルート ノードをハッシュマップに格納します。代替手段は何ですか？

  2. 再帰検索では、合計を関数の外に置いているので、合計を順次計算することができます。合計変数を内部に保持し、最後に合計値を返すことは可能ですか?

4

1 に答える 1

0

ファイルから読み取り、ルート ノードをハッシュマップに格納します。代替手段は何ですか？

明らかな入力形式を考えると、あなたのやり方はかなり合理的だと思わList<List<Node>>れますが、文字列が非常に似ているため、パフォーマンスがかなり急速に低下する可能性があるため、文字列と一緒に保存するのではなく、を使用することをお勧めします。入力が大きい場合、マップのパフォーマンスが大幅に向上します。

再帰検索では、合計を関数の外に置いているので、合計を順次計算することができます。合計変数を内部に保持し、最後に合計値を返すことは可能ですか?

private static int traverseTree(Node n) {
    if (n != null) {
        return n.value + traverseTree(n.left) + traverseTree(n.right);
    } else {
        return 0;
    }
}
于 2013-01-11T03:26:36.763 に答える