0
我有這個代碼工作正常,但有什麼方法可以統計這個程序的操作次數/步驟嗎?可以這麼說,我需要計算出平均執行時間(如果int值傳入程序時的數字/將數字按順序排序所需的步驟數)以及需要的步數信息獲得這個?隨着它是一個隨機數發生器,我不認爲這是可能的,但我知道必須有一種方法。計算一個BST中的移動次數java
此外,我希望能夠在手之前將我的根節點設置爲特定數字,然後將所有隨機數添加到根。我不喜歡在這裏問,但認爲我試了一下。
這是我迄今所做的:
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 ]));
}
}