height - 查找二叉搜索树的高度

Question

/* * 求 BST 树的高度 */

public void findHeight(){
    if(this.root == null){
        System.out.println("BST Tree is Empty ");
    }
    else
        findHeight(this.root);
}
public int findHeight(Tnode temp){
    if(temp == null){
        System.out.println("BST Tree is Empty ");
        return  -1;
    }
    else{
        return 1 + Math.max(findHeight(temp.getLeft()) ,findHeight(temp.getRight()) ) ;
    }
}

程序无限运行。找不到原因，如果有人指导我会很有帮助

提前致谢

Answer 1

“BST Tree is Empty”也将打印在树的每个终端叶子上。

要了解发生了什么，您可以添加一些调试输出：

private spaces(int len){
    String s = "       ";

    while (s.Length < len) {
      s += "        ";
    }

   return s.substring(0, len);
}

public int findHeight(Tnode temp, int nesting, String msg){
    String margin = spaces(2*nesting);

    if(temp == null){
        System.out.println(margin + msg + ": no sub-tree to explore");
        return  -1;
    }
    else{
        System.out.println(margin + msg);
        int hl = findHeight(temp.getLeft(), nesting + 1, "left");
        int hr = findHeight(temp.getRight(), nesting + 1, "right");

        return 1 + (hl >= hr ? hl : hr) ;
    }
}

您的无限递归可能是由于您的树结构中的一些错误。如果您的左/右子引用从不为空，则递归不会终止。

Answer 2

您确定 findHeight() 函数不返回任何内容吗？你对那个功能有什么期待吗？发布更多代码会有所帮助。