1
提供されているすべてのコードがあらかじめご迷惑をおかけしています。問題がどこで発生するのか不明なため、私はすべてを追加しています。AVLツリーが印刷されていない
私のプログラムで何か（空白スペースのみ）を出力するのに問題があります。このコードの大部分は私の本からまっすぐに来ていますが、私が働いた以前の（しかし同様の）プログラムからのものではありません。私は主に、levelOrderとののメソッドに焦点を当てていましたが、後者かもしれないと思っています。
import java.util.Scanner;
import java.lang.*;
public class AVLTree {
private static class AvlNode {
int key;
AvlNode left;
AvlNode right;
int height; //height difference between right and left subtrees at node
AvlNode(int x) {
key = x;
left = right = null;
height = 0;
}
AvlNode(int x, AvlNode l, AvlNode r) {
key = x;
left = l;
right = r;
}
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
boolean keepRunning = true;
while (keepRunning) {
System.out.print(">> Enter choice [1-7] from menu below: \n");
System.out.println("\t 1) Insert node");
System.out.println("\t 2) Remove node");
System.out.println("\t 3) Print level order");
System.out.println("\t 4) Exit program ");
int choice = input.nextInt();
int value;
switch (choice)
{
case 1:
System.out.print("Enter element to insert: ");
value = input.nextInt();
insert(value, root);
break;
case 2:
System.out.print("Enter element to remove: ");
value = input.nextInt();
remove(value);
break;
case 3:
levelOrder();
System.out.println("");
break;
case 4:
keepRunning = false;
break;
default:
System.out.println("Invalid Choice!");
keepRunning = false;
}
}
}
private static AvlNode root;
public AvlNode getroot() {
return root;
}
private static int height(AvlNode t) {
if(t == null) {
return 1;
}
else
return t.height;
}
private static final int ALLOWED_IMBALANCE = 1;
private static AvlNode balance(AvlNode t) {
if (t == null) {
return t;
}
if (height(t.left) - height(t.right) > ALLOWED_IMBALANCE) {
if (height(t.left.left) >= height(t.left.right)) {
t = singleRotateLL(t);
} else {
t = doubleRotateLR(t);
}
} else {
if (height(t.right) - height(t.left) > ALLOWED_IMBALANCE) {
if (height(t.right.right) >= height(t.right.left)) {
t = singleRotateRL(t);
} else {
t = doubleRotateRL(t);
}
}
}
t.height = Math.max(height(t.left), height(t.right)) + 1;
return t;
}
//public methods for insert, remove, findMin, findMax, find....
//The find function will not require modification because they do not change the structure of the tree
private static AvlNode singleRotateLL(AvlNode k2) {
AvlNode k1 = k2.left; //next make "poiner" adjustments for the LL rotate operation
k2.left = k1.right;
k1.right = k2;
k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
k1.height = Math.max(height(k1.left), height(k1.right)) + 1;
return k1;
}
private static AvlNode doubleRotateLR(AvlNode k3) {
AvlNode k1 = k3.left; //next make "poiner" adjustments for the LL rotate operation
AvlNode k2 = k1.right;
k1.right = k2.left;
k3.left = k2.right;
k2.left = k1;
k2.right = k3;
k1.height = Math.max(height(k1.left), height(k1.right)) + 1;
k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
k3.height = Math.max(height(k3.left), height(k3.right)) + 1;
return k2;
}
private static AvlNode singleRotateRL(AvlNode k2) {
AvlNode k1 = k2.right; //next make "poiner" adjustments for the LL rotate operation
k2.right = k1.left;
k1.left = k2;
k2.height = Math.max(height(k2.right), height(k2.left)) + 1;
k1.height = Math.max(height(k1.right), height(k1.left)) + 1;
return k1;
}
private static AvlNode doubleRotateRL(AvlNode k3) {
AvlNode k1 = k3.right; //next make "poiner" adjustments for the LL rotate operation
AvlNode k2 = k1.left;
k1.left = k2.right;
k3.right = k2.left;
k2.right = k1;
k2.left = k3;
k1.height = Math.max(height(k1.right), height(k1.left)) + 1;
k2.height = Math.max(height(k2.right), height(k2.left)) + 1;
k3.height = Math.max(height(k3.right), height(k3.left)) + 1;
return k2;
}
private static AvlNode insert(int x, AvlNode t) {
if(t == null)
return new AvlNode(x, null, null);
int compareResult = Integer.compare(x, t.key);
if(compareResult < 0) {
t.left = insert(x, t.left);
}
else if(compareResult > 0) {
t.right = insert(x, t.right);
}
else; // duplicate, do nothing
return balance(t);
}
public int findMin() {
return findMin(root).key;
}
private static AvlNode findMin(AvlNode t) {
if (t == null) {
return null;
}
if (t.left == null) {
return t;
}
return findMin(t.left);
}
public static void remove(int x) {
remove(x, root);
}
private static AvlNode remove(int x, AvlNode t) {
if (t == null) {
return t;
}
int compareResult = Integer.compare(x, t.key);
if (compareResult < 0) {
t.left = remove(x, t.left);
}
else if (compareResult > 0) {
t.right = remove(x, t.right);
}
else if ((t.left != null) && (t.right != null)) {
t.key = findMin(t.right).key;
t.right = remove(t.key, t.right);
}
else {
t = (t.left != null) ? t.left : t.right;
}
return balance(t);
}
private static void levelOrder() { //prints the level order traversal of the tree
int h = height(root);
for(int i = 1; i <= h; i++) {
printLevel(root, i);
}
}
private static void printLevel(AvlNode t, int level) {
if(t == null) {
return;
}
if(level == 1) {
System.out.print(t.key + " ");
}
else if(level > 1) {
printLevel(t.left, level - 1);
printLevel(t.right, level - 1);
}
}
}
は、デバッガを使用する方法を学習する必要があるような音。 – Henry