我不确定我是否正确执行此操作,因为这是我第一次使用节点进行编码。但是到目前为止,这是我的代码,如果有人可以查看它并帮助我了解我是否做错了什么。我的插入/删除方法也让我很难过。教授为此给了我们伪代码,但我似乎无法掌握如何将其解释为 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);
}
}