返回二叉查找樹的高度

我有兩個類，BSTSet和BSTNode，它們都有一個可以返回高度的height（）方法。我得到一個stackoverflow錯誤，並不確定是什麼導致它。返回二叉查找樹的高度

BSTSet

public class BSTSet <E extends Comparable<E>> extends AbstractSet <E> { 

    // the root of the supporting binary search tree 
    private BSTNode<E> root; 

    // number of elements in the set 
    private int count = 0; 

    public boolean isEmpty() { 
     return count == 0; 
    } 

    public int size() { 
     return count; 
    } 


    public int height() { 
     if(root == null) return -1; 
     else return root.height(); 
    } 
}

BSTNode

public class BSTNode <E extends Comparable<E>> { 

    private E value; 
    private BSTNode<E> left; 
    public BSTNode<E> right; 

    public BSTNode(E value) { 
     this.value = value; 
    } 

    public E getValue() { 
     return value; 
    } 

    public BSTNode<E> getLeft() { 
     return left; 
    } 

    public BSTNode<E> getRight() { 
     return right; 
    } 

    public int height() { 
     if(left == null && right == null) return 0; 
     if(left != null && right == null) {UI.println("left");return left.height()+ 1; } 
     else if(right != null && left == null){UI.println("right");return right.height()+ 1;} 
     else{UI.println("both"); return Math.max(right.height(), left.height()) + 1;} 
    } 
}

如果您想了代碼或不再需要的信息，請隨時提問。

來源

2014-10-12 M0rty

if(left == null && right == null) return 0;

變化

if(left == null && right == null) return 1;

如果一個節點沒有孩子仍然具有高度1

然後，只需做一個遞歸調用這樣 else return Max(left.height(), right.tHeight) + 1;

根據定義，高度節點的t是它的最大高度是子髮辮+ 1

堆棧溢出是由於調用height()方法相同的節點在這裏：

else if(left != null && right == null || left == null && right != null) return height()+ 1; 
else return height()+ 2;

我只是想扔這如果你想一個節點，在高度0開始明顯保持 if(left == null && right == null) return 0;

來源

2014-10-12 03:24:27 qbit

不幸的是，我無法使用最多，但我修改了代碼，得到它的工作，但我相信它不是返回正確的值.. – M0rty 2014-10-12 03:51:23

的問題是，你的遞歸height()方法調用thisheight()。這不是算法應該如何工作的原因，它是無限遞歸循環的明顯原因，它會給你堆棧溢出。

@ xgeorgekx的方法應該給出正確的答案，但我不相信它是最優的。如果樹是平衡的，那麼左邊和右邊的子樹的高度是相關的......並且你可能不需要穿過兩邊。如果可以避免，那麼height方法可以實現爲O(logN)而不是O(N)。

我懷疑你原來的做法是試圖將O(logN) ...

來源

2014-10-12 03:26:00

當然這是有道理的。是試圖成爲O（logN）。我仍然對最佳解決方案應該有些困惑，但是仍然在學習 – M0rty 2014-10-12 03:38:14

我不確定我自己......這就是爲什麼我的回答在這一點上是「模糊」的:-)。最佳解決方案取決於您正在實施的平衡樹的精確不變量。 – 2014-10-12 04:53:08

我已經設法讓代碼工作一些，但是我遇到的問題是當它既是左邊節點，也是右邊節點時...檢查我編輯的BSTNode – M0rty 2014-10-12 06:22:33

返回二叉查找樹的高度

回答

相關問題