在 Java 中遍历 Avl 树

Question

通过函数 height（Node），我得到了树中每个节点的高度。对于树中的每个节点，我想确定从右节点中减去左节点的高度。我只是应该遍历树。但我的代码中有StackOverflow错误。给我一些帮助。我认为我的程序的其他部分有问题。

    public class AvlTree {
private Node root = new Node (0,0,"","");
void devision( Node tmp){
tmp=root;
if(tmp.getLeftChild()!=null){
        tmp.devisionNumber=height(tmp.getLeftChild())-height(tmp.getRightChild());
        devision(tmp.getLeftChild());
}
 if(tmp.getRightChild()!=null){
     tmp.devisionNumber=height(tmp.getLeftChild())-height(tmp.getRightChild());
     devision(tmp.getRightChild());
 }
}
int height(Node node){
    if(node==null)
        return -1;
    int left=height(node.getLeftChild());
    int right=height(node.getRightChild());
    if(left>right)
    {
        return left+1;
    }
    else 
        return right +1;
}
void insert (Node newNode ){
    Node tmp=root;
        if(root.getStdNum()==0){
            root=newNode;
            root.setLeftChild(null);
            root.setRightChild(null);
            root.setRoot(null);
        }
        else{
            while(true) {
                if(newNode.getStdNum()<tmp.getStdNum()){
                    if(tmp.getLeftChild()==null)
                        break;
                    else
                    tmp=tmp.getLeftChild();
                }
            if(newNode.getStdNum()>tmp.getStdNum()){
                if(tmp.getRightChild()==null)
                    break;
                else
                tmp=tmp.getRightChild();
            }
        }
        ////////////////////////
        if(newNode.getStdNum()<tmp.getStdNum())
        {
            tmp.setLeftChild(newNode);
            newNode.setRoot(tmp);                   
        }
        if(newNode.getStdNum()>tmp.getStdNum())
        {
            tmp.setRightChild(newNode);
            newNode.setRoot(tmp);
        }
    }
}
}
public  class Node {
private int StdNum;
private int Avarage;
private String Name;
private String FamillyName;
private Node Root;
public int devisionNumber;
private Node LeftChild;
private Node RightChild;

public Node(int stdNum,int Avarage,String Name,String FamillyName){
    this.StdNum=stdNum;
    this.Avarage=Avarage;
    this.Name=Name;
    this.FamillyName=FamillyName;
}
public boolean CheckForNull (Object a){
    boolean check;
    if(a==null){
        check=true;
    }
    else 
        check=false;
    return check;
}
public void ShowData(){
    System.out.println("ID: "+ getStdNum());
    System.out.println("Avg: " + getAvarage());
    System.out.println("Name: "+ getName());
    System.out.println("Familly: "+ getFamillyName()+"n");
    if(CheckForNull(this.getLeftChild())==false)
    System.out.println("leftNode ID: "+ getLeftChild().getStdNum() );
    else System.out.println("LeftChild : Null ");
    if(CheckForNull(this.getRightChild())==false)
    System.out.println("RightNode ID: "+ getRightChild().getStdNum());
    else System.out.println("RightChild : Null ");
    if(CheckForNull(this.getRoot())==false)
    System.out.println("Root ID: "+ getRoot().getStdNum());
    else System.out.println("Root : Null ");
}
public int getStdNum() {
    return StdNum;
}
public void setStdNum(int stdNum) {
    StdNum = stdNum;
}
public int getAvarage() {
    return Avarage;
}
public void setAvarage(int avarage) {
    Avarage = avarage;
}
public String getName() {
    return Name;
}
public void setName(String name) {
    Name = name;
}
public String getFamillyName() {
    return FamillyName;
}
public void setFamillyName(String famillyName) {
    FamillyName = famillyName;
}
public Node getRoot() {
    return Root;
}
public void setRoot(Node root) {
    Root = root;
}
public Node getLeftChild() {
    return LeftChild;
}
public void setLeftChild(Node leftChild) {
    LeftChild = leftChild;
}
public Node getRightChild() {
    return RightChild;
}
public void setRightChild(Node rightChild) {
    RightChild = rightChild;
}

}

Answer 1

您始终将节点设置为 root（方法的第 2 行），因此您的递归不会沿着子树向下移动，而是每次重新启动......因此，递归永远不会结束 - 导致堆栈溢出。