0

2 つのバイナリ ツリーを交差させ、同じノードを持つ新しいバイナリ ツリーを作成しようとしていますが、次のコードでは stackOverflow エラーが発生します。誰でも私を助けることができますか？

private OrderedSet<E> resultIntersect = new OrderedSet<E>();

public OrderedSet<E> intersection(OrderedSet<E> other) {
    OrderedSet<E> result = new OrderedSet<E>();
    if (other.root == null || root == null)
        return result;
    else if (height() == 0 && other.height() == 0
            && other.root.data.equals(root.data)) {
        result.insert(root.data);
        return result;
    } else {
        intersection(other, root, other.root);
        result = resultIntersect;
    }
    return result;
}

private void intersection(OrderedSet<E> other, TreeNode root1,
        TreeNode root2) {
    if (root1 == root2) {
        resultIntersect.insert(root1.data);
    }
    if (root1 == null || root2 == null) {
        return;
    }
    intersection(other, root1.left, root2.left);
    intersection(other, root1.right, root2.right);
}

編集

これは私が必要とする方法に近いと思いますが、それでもエラーが発生します。

private OrderedSet<E> resultIntersect = new OrderedSet<E>();

public OrderedSet<E> intersection(OrderedSet<E> other) {
    OrderedSet<E> result = new OrderedSet<E>();
    result = resultIntersect;
    return result;
}

private void intersection(OrderedSet<E> other, TreeNode t) {
    if (other.contains(t.data)) {
        resultIntersect.insert(t.data);
    }
    if(t.left != null)
        intersection(other, t.left);
    if(t.right != null)
        intersection(other, t.right);
}
4

2 に答える 2

1

具体的な問題はわかりませんが、いくつかの問題があります。

  1. 「その他」が2番目の交差点に渡されるのはなぜですか(使用されません)?
  2. セットへの挿入を行った後、戻るべきではありませんか?
  3. resultグローバル変数ではなく 、ローカルの OrderedSet (と呼ばれる) を渡して挿入するべきではありませんか?
  4. ノード自体ではなく、root1 と root2 のデータを比較するべきではありませんか?
  5. 2回目のリターンは不要です
  6. null をテストする前にルートを逆参照する
  7. 初期テストは不要です

これらの欠陥をクリーンアップすると、次のようになります。

public OrderedSet<E> intersection(OrderedSet<E> other) {
    OrderedSet<E> result = new OrderedSet<E>();
    intersection(result, root, other.root);
    return result;
}

private void intersection(OrderedSet<E> result, TreeNode root1,
        TreeNode root2) {
    if (root1 == null || root2 == null) {
        return;
    }
    if (root1.data == root2.data) {
        result.insert(root1.data);
    }
    intersection(result, root1.left, root2.left);
    intersection(result, root1.right, root2.right);
}

これが機能するかどうかはわかりませんが、近いです

于 2012-06-30T03:59:01.633 に答える
0

スタック オーバーフロー エラーは、スタック制限に達する前に底を打たない再帰があることを示しています。主な容疑者はprivate void intersection方法です。入力が正しいバイナリ ツリーである場合、(root1 == null || root2 == null)ある時点で条件に到達する必要があります。ただし、非常に大きく、バランスの取れていないバイナリ ツリーの場合は長い時間がかかるか、「バイナリ ツリー」にバグがあり、どこかにサイクルがある場合は到達しない可能性があります。 . どちらの場合も、オーバーフローの原因になる可能性があります。

また、同じメソッドの条件が意図したとおりに実行されていない可能性があることも指摘しておきif (root1 == root2)ます。パラメーターroot1とroot2はおそらく同じオブジェクトではないため、その条件はほぼ確実に false になります。他のequals()ベースの比較がおそらくより適切です。

于 2012-06-30T04:00:11.620 に答える