0

特定のツリーが BST かどうかを調べるコードを作成しました。しかし、私はそれをリファクタリングする助けが必要です。私が探しているもののいくつかは次のとおりです。

  1. 一時変数を取り除く (Martin Fowler の提案による)
  2. leftTreeMax と RighTreeMin メソッドの組み合わせ
  3. より良いメソッド名

また、人々が持っている他のリファクタリングのアイデアをいただければ幸いです。

package com.cc.bst;

import com.cc.queue.Queue;
import com.cc.trees.BinaryTreeNode;

public class IsBinaryTreeBST {

public static boolean binaryTreeBST ( BinaryTreeNode root) {

    if (root == null) {
        return false;
    }
    int maxVal = leftTreeMax(root.getLeft());
    int minVal = rightTreeMin(root.getRight());
    int rootVal = root.getData();

    if (maxVal == 0 || minVal == 0 ) {
        return false;
    }

    if (rootVal > maxVal && rootVal < minVal) {
        return true;
    }

    return false;

}

private static int leftTreeMax (BinaryTreeNode node) {

    if (node == null) {
        return 0;
    }
    Queue nodeQueue = new Queue();
    nodeQueue.enqueue(node);
    int maxValue = node.getData();

    while (!nodeQueue.isEmpty()) {
        BinaryTreeNode tempNode = (BinaryTreeNode) nodeQueue.dequeue();         
        BinaryTreeNode left = tempNode.getLeft();
        BinaryTreeNode right = tempNode.getRight();

        if (left != null ) {
            if (left.getData() > tempNode.getData()) {
                return 0;
            }
            nodeQueue.enqueue(left);
        }
        if (right != null) {
            if ( tempNode.getData() > right.getData()) {
                return 0;
            }
            nodeQueue.enqueue(right);
        }
        if (tempNode.getData() > maxValue) {
            maxValue = tempNode.getData();
        }           
    }       
    System.out.println("---------- maxVal -------->" +  maxValue);
    return maxValue;
}

private static int rightTreeMin(BinaryTreeNode node) {

    if (node == null) {
        return 0;
    }
    Queue nodeQueue = new Queue();
    nodeQueue.enqueue(node);
    int minValue = node.getData();

    while (!nodeQueue.isEmpty()) {
        BinaryTreeNode tempNode = (BinaryTreeNode) nodeQueue.dequeue();         
        BinaryTreeNode left = tempNode.getLeft();
        BinaryTreeNode right = tempNode.getRight();
        System.out.println("---------- tempNode -------->" + tempNode.getData());

        if (left != null ) {
            System.out.println("---------- left -------->" + left.getData());

            if (left.getData() > tempNode.getData()) {
                return 0;
            }
            nodeQueue.enqueue(left);                
        }
        if (right != null) {
            if ( tempNode.getData() > right.getData()) {
                return 0;
            }
            System.out.println("---------- right -------->" + right.getData());

            nodeQueue.enqueue(right);               
        }           
        if (tempNode.getData() < minValue) {
            minValue = tempNode.getData();
        }
    }       
    System.out.println("---------- minVal -------->" +  minValue);

    return minValue;
        }
}
4

1 に答える 1

1

正直なところ、あなたのコードが非常に複雑であることに驚きました。一連の改善の理由を理解するのは難しいです。書き直す方が簡単に思えます。次のように考えてください。

3 つのルールを満たす必要があります (ウィキペディアから引用)。

  1. ノードの左側のサブツリーには、ノードのキーより小さいキーを持つノードのみが含まれます。
  2. ノードの右側のサブツリーには、ノードのキー以上のキーを持つノードのみが含まれます。
  3. 左と右の部分木は両方とも二分探索木でなければなりません。

ご覧のとおり、ルール番号 3 は、各サブツリーが親ツリーと同じルールを持つ必要があるため、再帰が適切であるという大きなヒントを与えてくれます。

では、次のようなことをしてみませんか。

checkBST(node,min,max) {
    if(node == NULL)
        return true
    if(node.value < min || node.value >= max)
        return false
    return checkBST(left,min,node.value) && checkBST(right,node.value,max)
}

checkBST(root,-infinity,+infinity)

このようにして、サブツリーごとにその値の境界を保持しています。この境界は親によって受け取られます。したがって、左のサブツリーが親よりも小さい必要があるとしましょう。次に、親は最大値です。このサブツリーは、その親よりも大きいか等しい必要がある右側のサブツリーにも当てはまります。

このアルゴリズムは、時間の複雑さに関しては最適ではありませんが、記述と理解が最も簡単です。

于 2012-09-20T15:01:24.717 に答える