java - AVL 树不打印

Question

提前对提供的所有代码表示歉意，因为我不确定问题可能出在哪里，所以我正在添加整个代码。

我无法让我的程序输出任何内容(只是空白)。大部分代码直接来 self 们的书，而不是来 self 以前工作过的(但类似的)程序。我主要关注 levelOrder 和 insert 方法，尽管我认为可能是后者。

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);
        }
    }
}

Answer 1

您必须进行两项更改，一项是第一次初始化 root，第二项是相应地更改高度。只需更改以下类和函数:

private static AvlNode insert(int x, AvlNode t) {
    if (t == null && root==null)
        return (root = new AvlNode(x, null, null));
    else if (t==null) {
        return  new AvlNode(x, null, null);
    }

    t.height++;
    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 {
        t.height--;
    }

        return balance(t);
    }

private static class AvlNode {
    int key;
    AvlNode left;
    AvlNode right;
    int height=0; 

    AvlNode(int x, AvlNode l, AvlNode r) {
        key = x;
        left = l;
        right = r;
        this.height++;
    }
}