İkili Arama Ağacında Yükseklik Bulma

Question

Daha

Kaynak Non AMP-version Düzenle

İkili Arama Ağacında Yükseklik Bulma

İkili arama ağacının yüksekliğini bulmak için bu yöntemi yeniden düzenlememe yardımcı olabilecek biri var mı diye merak ediyordum. Şimdiye kadar kodum şöyle görünüyor. Ancak, aldığım cevap gerçek yükseklikten 1 daha büyük. Ancak, dönüş ifadelerimden +1'i kaldırdığımda, gerçek yükseklikten 1 daha az. Hala bu BST ile özyineleme konusunda kafamı sarmaya çalışıyorum. Herhangi bir yardım çok takdir edilecektir.

public int findHeight(){
    if(this.isEmpty()){
        return 0;
    }
    else{
        TreeNode<T> node = root;
        return findHeight(node);
    }
}
private int findHeight(TreeNode<T> aNode){
    int heightLeft = 0;
    int heightRight = 0;
    if(aNode.left!=null)
        heightLeft = findHeight(aNode.left);
    if(aNode.right!=null)
        heightRight = findHeight(aNode.right);
    if(heightLeft > heightRight){
        return heightLeft+1;
    }
    else{
        return heightRight+1;
    }
}

altern

Edited question 2017ööp9öö8 Ağustos 2017 в 8:09

Programlama

binary-tree

2010ööp47öö4 Nisan 2010 в 4:47

74 görünümler

Stephen · Answer 1 · 2010-04-08T05:08:46+00:00

İkili arama ağacının yüksekliği katman sayısı - 1e eşittir.

http://en.wikipedia.org/wiki/Binary_tree adresindeki şemaya bakın

Özyinelemeniz iyi, bu yüzden kök seviyesinden bir çıkarmanız yeterli.

Ayrıca, null düğümleri işleyerek işlevi biraz temizleyebileceğinizi unutmayın:

int findHeight(node) {
  if (node == null) return 0;
  return 1 + max(findHeight(node.left), findHeight(node.right));
}

Jerry Coffin · Answer 2 · 2010-04-08T05:06:20+00:00

Jerry Coffin

Kaynak Non AMP-version Düzenle

Bence kodunuzun biraz basitleştirilmesinde fayda var. Bir child işaretçisi null olduğunda özyinelemeyi sonlandırmaya çalışmak yerine, yalnızca current işaretçisi null olduğunda sonlandırın. Bu, kodu yazmayı çok daha basit hale getirir. Sözde kodda şöyle bir şey görünüyor:

if (node = null)
    return 0;
else
    left = height(node->left);
    right = height(node->right);
    return 1 + max(left, right);

Soul

Edited answer 2019ööp58öö6 Kasım 2019 в 6:58

9

0

Yorumlar (5)

Matthew Flaschen · Answer 3 · 2010-04-08T04:51:06+00:00

İşte bunu ifade etmenin kısa ve umarım doğru bir yolu:

  private int findHeight(TreeNode aNode){
    if(aNode == null || (aNode.left == null && aNode.right == null))
      return 0;
    return Math.max(findHeight(aNode.left), findHeight(aNode.right)) + 1;
  }

Geçerli düğüm null ise, ağaç yoktur. Her iki çocuk da boşsa, tek bir katman vardır, bu da 0 yükseklik anlamına gelir. Bu, yükseklik tanımını (Stephen tarafından bahsedilen) katman sayısı - 1 olarak kullanır