java - 计算 BST java 中的移动次数

Question

我的代码运行良好，但是有什么方法可以计算该程序执行的操作/步骤的数量吗？可以说，操作的跟踪，我需要计算出平均执行时间(这是传递给程序的 int 值的数量/将数字按顺序排序所采取的步骤数)并且需要步骤数信息获得这个？由于它是一个随机数生成器，我认为这是不可能的，但我知道一定有办法。

此外，我希望能够预先将根节点设置为特定数字，然后将所有随机数添加到根中。我不喜欢在这里提问，但我想尝试一下。

这是我到目前为止所做的:

    public class BinarySearchTree {


    private Node root; 

    private static class Node {
        Node parent;
        Node left;
        Node right;
        int data;

        Node( int data ) {
            this.data = data;
        }

        @Override
        public String toString( ) {
            return "" + data;
        }
    }


    public void insert( int data ) {
        root = insert( root, data );
    }

    public Node insert( Node node, int data ) {
        if( node == null ) {
            node = new Node( data );
        } else if( data < node.data ) {
            node.left = insert( node.left, data );
            node.left.parent = node;
        } else {
            node.right = insert( node.right, data );
            node.right.parent = node;
        }
        return node;
    }

    private void swap( Node a, Node b ) {

        if( a.parent == null ) {
            root = b;
        } else if( a == a.parent.left ) {
            a.parent.left = b;
        } else {
            a.parent.right = b;
        }

        if( b != null ) {
            b.parent = a.parent;
        }
    }

    public void delete( int data ) {
        delete( root, data );
    }

    public void delete( Node node, int data ) {

        if( node == null ) {
            return;
        }
        else if ( data == node.data) {
            if( node.left == null ) {
                swap( node, node.right ); 
            }
            else if( node.right == null ) {
                swap( node, node.left );
            }
            else {
                Node minNode = node.right;
                while( minNode.left != null ) {
                    minNode = minNode.left;
                }
                if( minNode.parent != node ) {
                    swap( minNode, minNode.right );
                    minNode.right = node.right;
                    minNode.right.parent = minNode;
                }

                swap( node, minNode );
                minNode.left = node.left;
                minNode.left.parent = minNode;
            }
        } 
        // Continue searching in the left subtree.
        else if( data < node.data) {
            delete( node.left, data );
        } 
        // Continue searching in the right subtree.
        else {
            delete( node.right, data );
        }
    }

    public boolean lookup( int data ) {
        return lookup( root, data );
    }

    public boolean lookup( Node node, int data ) {
        if( node == null ) {
            // Can't find it.
            return false;
        } else if( data == node.data) {
            // Found it.
            return true;
        } else if( data < node.data) {
            // Search left subtree.
            return lookup( node.left, data );
        } else {
            // Search right subtree.
            return lookup( node.right, data );
        }
    }

    public int minValue( ) {
        return minValue( root );
    }

    public int minValue( Node node ) {
        Node cursor = node;
        while( cursor.left != null ) {
            cursor = cursor.left;
        }
        return cursor.data;
    }

    public int maxValue( ) {
        return maxValue( root );
    }

    public int maxValue( Node node ) {
        Node cursor = node;
        while( cursor.right != null ) {
            cursor = cursor.right;
        }
        return cursor.data;
    }

    public void inorderTraversal( ) {
        inorderTraversal( root );
    }

    private void inorderTraversal( Node node ) {
        if( node != null ) {
            inorderTraversal( node.left );
            System.out.print( node.data + " " );
            inorderTraversal( node.right );
        }
    }

    public static int[] generateRandomNumbers( int size ) {
    if ( size <= 0 ) {
        throw new IllegalArgumentException( "size must be greater than 0" );
    }
    Random random = new Random( System.currentTimeMillis() );
    int[] results = new int[ size ];
    for ( int i = 0; i < size; i++ ) {
        results[ i ] = random.nextInt( size );
    }
    return results;
}

   public static void main( String[] args ) {
    BinarySearchTree bst = new BinarySearchTree();
    int[] randoms = generateRandomNumbers( 10 );
    for ( int i : randoms ) {
        bst.insert( i );
    }




    System.out.println( "\n Sorted :" );
    bst.inorderTraversal();

    System.out.println( "\nMax Value:" );
    System.out.println( bst.maxValue() );
    System.out.println( "\n Min Value:" );
    System.out.println( bst.minValue() );

    System.out.println( bst.lookup( randoms[ 1 ] ) );
    System.out.println( bst.lookup( randoms[ 9 ] ) );
    }
    }

Answer 1

您可以简单地声明一个计数变量:

public class BinarySearchTree {
  private int operationCount = 0;

然后更改您想要计数的任何操作的代码以增加此变量:

public boolean lookup( Node node, int data ) {
    operationCount = operationCount + 1;
    if( node == null ) {
        // the rest of your code here

您唯一需要弄清楚的是您想要计算哪些操作。然后，您可以更改所有这些操作中的计数，并在程序完成后检查 operationCount 的值。