2

我不确定我是否正确执行此操作，因为这是我第一次使用节点进行编码。但是到目前为止，这是我的代码，如果有人可以查看它并帮助我了解我是否做错了什么。我的插入/删除方法也让我很难过。教授为此给了我们伪代码，但我似乎无法掌握如何将其解释为 Java 代码，因为我以前从未做过这种类型的代码。主要是因为有一个 if 语句检查高度以查看树是否平衡，我将如何在其中实现高度？非常感谢提示或任何帮助，我已经坚持了一段时间。谢谢！

我也不认为我的构造函数是正确的，我不确定。插入/删除中的返回可以忽略，它只是放在那里以确保其余代码能够编译。

public class AvlNode{

    public static void main(String[]args){

    }
    //constructor
    public class AvlTreeNode{
        private int num;
        private AvlTreeNode left;
        private AvlTreeNode right;

        public AvlTreeNode left(){
            return this.left;
        }

        public AvlTreeNode right(){
            return this.right;
        }

        public int value(){
            return this.num;
        }
    }
    //method to find the number specified on the node
    public AvlTreeNode find(AvlTreeNode t, int x){
        if(t == null){
            return null;
        }
        if( t.value() == x){
            return t;
        }
        else if(x < t.value()){
            return find(t.left(), x);
        }
        else{
            return find(t.right(), x);
        }
    }
    //method to insert a new node and number to a tree
    public AvlTreeNode insert(AvlTreeNode t, int x){
        if(t == null){
            t = new AvlTreeNode(x, null, null);
            return t;
        }
        if(x < t.value()){
            t.left = insert(t.left(), x);
        }
        return t;
    }
    //method to remove a node and number from the tree
    public AvlTreeNode remove(AvlTreeNode t, int x){
        return t;
    }
    //Inorder traversal method, should print out numbers in ascending order if correct
    public void inOrder(AvlTreeNode t){
        if(t != null){
            inOrder(t.left());
            System.out.print(t.value() + " ");
            inOrder(t.right());
        }
    }
    //single rotation of nodes to balance tree, rotating leftwards
    public static AvlTreeNode singleRotateWithLeft( AvlTreeNode k1){
        AvlTreeNode k2 = k1.left;
        k1.left = k2.right;
        k2.right = k1;
        return k2;
    }
    //single rotation of nodes to balance tree, rotating rightwards
    public static AvlTreeNode singleRotateWithRight( AvlTreeNode k2){
        AvlTreeNode k1 = k2.right;
        k2.right = k1.left;
        k1.left = k2;
        return k1;
    }
    //double rotation of nodes towards the left
    public static AvlTreeNode doubleRotateWithLeft( AvlTreeNode k3){
        k3.left = doubleRotateWithRight(k3.left);
        return doubleRotateWithLeft(k3);
    }
    //double rotation of nodes towards the right
    public static AvlTreeNode doubleRotateWithRight( AvlTreeNode k2){
        k2.right = doubleRotateWithLeft(k2.right);
        return doubleRotateWithRight(k2);
    }
}
4

1 回答 1

1

关于构造函数：我认为错误在于您将用于描述 AvlTreeNode 的内部类误认为构造函数。很可能，您不需要编写显式构造函数，因为默认（空）构造函数会为您完成。

树的构造可以看作是将其所有节点插入到一棵空树中。

关于高度，您可能应该将树的高度视为每个 AvlTreeNode 的属性（因此，在num您旁边需要一个height变量）。接下来将实现插入和删除，以便使用正确的局部变换/旋转，并适当增加或减少插入节点及其子节点的高度。

编辑：我现在看到您的代码使用带有三个参数的构造函数。您可以使用本示例代码中的构造函数。

//inner class for the node
public class AvlTreeNode{
    private int num;
    private int height;

    private AvlTreeNode left;
    private AvlTreeNode right;

    //this is the constructor!
    public AvlTreeNode(int value, AvlTreeNode left, AvlTreeNode right){
        this.num = value;
        this.left = left;
        this.right = right;
        this.height = 1;

        if (left != null && left.height() >= height){
            height = left.height() + 1;
        }
        if (right != null && right.height() >= height){
            height = right.height() + 1;
        }
    }

    public AvlTreeNode left(){
        return this.left;
    }

    public AvlTreeNode right(){
        return this.right;
    }

    public int value(){
        return this.num;
    }

    public int height(){
        return height;
    }
}
于 2013-10-20T20:07:58.497 回答