0
我現在要做的是在我的二叉搜索樹(BST)中找到重複計數的最小值。如何找到我的BST中的最小計數
這意味着當插入值時BST是正常的,但是當它獲得相同的值兩次時,它會增加重複計數的值,而樹不依賴於它(所以我不能只是向左走的最小值)。
我已經嘗試獲得最小值,但它總是短。試圖讓最小的功能是findSmallest
public static void main(String[] args) {
int x = 0; //random number
Random rnum = new Random();
SBT sbt = new SBT();
for(int i = 0; i < 100; i++){
x = rnum.nextInt(20) + 1;
sbt.insert(x);
}
sbt.printLargestCount();
sbt.printSmallestCount();
sbt.FS();
sbt.deleteBoth();
System.out.println("Sum of the key values is: " + sbt.sumKeyValue());
System.out.println("Sum of the repeat counts is: " + sbt.sumReapeatCount());
sbt.inorder();
}
這裏是試圖讓現在我試圖去通過樹中的所有節點並將它們與當前最小值的值的功能。 如果節點repeatCount
小於該值,它將改變值並且全局節點smallestCount
。
我在下面添加了這些全局變量。
private BSTNode root;
private BSTNode largestCount;
private BSTNode smallestCount;
private int sumKeyVal;
public void FS(){
findSmallest(root, 0);
System.out.println("data is: " + smallestCount.data + " repeatCount is: " + smallestCount.repeatCount);
}
private void findSmallest(BSTNode r, int val){
if(r == null) return;
if(r == root)val = r.repeatCount;
if(r.repeatCount < val){
val = r.repeatCount;
smallestCount = r;
System.out.println(val);
}
if(r.right == null && r.left == null)
return;
else if(r.left != null)
findSmallest(r.left,val);
else if(r.right != null)
findSmallest(r.right,val);
}
private BSTNode insert(int x, BSTNode t){
if (t == null){
t = new BSTNode(x);
smallestCount = t;
}
else if (x < t.data)
t.left = insert(x, t.left);
else if (x > t.data)
t.right = insert(x, t.right);
else
t.height = max(height(t.left), height(t.right)) + 1;
return t;
}
private int height(BSTNode t) {
return t == null ? -1 : t.height;
}
// Function to max of left/right node
private int max(int lhs, int rhs) {
return lhs > rhs ? lhs : rhs;
}
這裏使用的節點類:
public class BSTNode {
BSTNode left, right;
int data;
int height;
int repeatCount;
/* Constructor */
public BSTNode(){
left = null;
right = null;
data = 0;
height = 0;
repeatCount = 0;
}
/* Constructor */
public BSTNode(int n){
left = null;
right = null;
data = n;
height = 0;
repeatCount = 0;
}
}