Găsirea înălțimii în arborele de căutare binar (Programare, Algoritm, Recursivitate, Arbore De Căutare Binar)

mike a intrebat.

Mă întrebam dacă mă poate ajuta cineva să refac această metodă pentru a găsi înălțimea unui arbore de căutare binar. Până acum, codul meu arată astfel. Cu toate acestea, răspunsul pe care îl obțin este mai mare decât înălțimea reală cu 1. Dar când înlătur +1 din declarațiile mele de returnare, este mai mică decât înălțimea reală cu 1. Încă încerc să-mi înfășor capul în jurul recursivității cu aceste BST. Orice ajutor ar fi foarte apreciat.

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;
    }
}

Comentarii

  • Ei bine, am reușit să returnez înălțimea corectă returnând findHeight(node)-1 în metoda mea publică. Cu toate acestea, mă simt ca și cum acesta este un cod neglijent, orice sugestii pentru o revizuire? –  > Por mike.
  • Este aceasta abordarea corectă pentru rezolvarea înălțimii copacului ?github.com/joeyajames/Python/issues/1 –  > Por rittam.
24 răspunsuri
Corey

Problema se află în cazul tău de bază.

„Înălțimea unui arbore este lungimea drumului de la rădăcină până la cel mai adânc nod din arbore. Un arbore (înrădăcinat) cu un singur nod (rădăcina) are o înălțime de zero.” – Wikipedia

Dacă nu există niciun nod, trebuie să returnați -1, nu 0. Acest lucru se datorează faptului că adăugați 1 la sfârșit.

Așadar, dacă nu există un nod, se returnează -1, ceea ce anulează +1.

int findHeight(TreeNode<T> aNode) {
    if (aNode == null) {
        return -1;
    }

    int lefth = findHeight(aNode.left);
    int righth = findHeight(aNode.right);

    if (lefth > righth) {
        return lefth + 1;
    } else {
        return righth + 1;
    }
}

Comentarii

  • Da, acest lucru funcționează corect fără a fi nevoie să scad 1 în metoda mea publică. Sunt încă confuz în ceea ce privește modul în care această metodă funcționează cu recursivitatea. Am declarat ints în stânga și în dreapta după instrucțiunea if, dar nu înțeleg cum sunt incrementate prin această metodă –  > Por mike.
  • Această metodă funcționează prin scăderea lui 1 în cazul de bază, ele sunt incrementate ca orice altă metodă dată, atunci când mergeți mai adânc în copac adăugați 1 la înălțime. –  > Por Corey.
  • unde ați găsit citatul dvs. The height of a tree is the length of the path from the root to the deepest node in the tree. A (rooted) tree with only a node (the root) has a height of zero? În pagina wiki, nu există un astfel de citat –  > Por Jackson Tale.
  • Pentru cei confuzi cu privire la modul în care funcționează această recursivitate, am realizat un videoclip care explică mai întâi procesul la un nivel înalt, iar apoi parcurgem codul cu un exemplu: Găsiți înălțimea arborelui binar. Sperăm că mulți dintre voi îl vor găsi util și, în acest caz, ar trebui probabil să-l adăugăm la acest răspuns. –  > Por cute_ptr.
  • „Înălțimea unui nod dintr-un arbore este numărul de muchii de pe cea mai lungă cale descendentă simplă de la nodul respectiv la o frunză, iar înălțimea unui arbore este înălțimea rădăcinii sale.” este de la p. 1177 din CLRS (ed. a 3-a). Pe baza acestei definiții, un arbore format dintr-un singur nod (rădăcină) are înălțimea zero, ceea ce implică faptul că acesta este singurul răspuns corect. –  > Por tmakino.
Stephen

Înălțimea unui arbore de căutare binar este egală cu number of layers - 1.

Vezi diagrama de la http://en.wikipedia.org/wiki/Binary_tree

Recursivitatea ta este bună, așa că trebuie doar să scazi unu la nivelul rădăcinii.

De asemenea, rețineți că puteți curăța puțin funcția prin tratarea nodurilor nule:

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

Comentarii

  • La prima mea încercare la această metodă am folosit ceva de genul acesta, însă am tot primit o excepție StackOverFlow din anumite motive când am rulat codul meu? Presupun că din cauză că am verificat dacă există pointeri care arată spre null? –  > Por mike.
  • (Eliminat comentariul despre c++, care nu se aplică). Este probabil ca „node == null” să nu se termine corect. –  > Por Stephen.
  • Stephen, nu ar trebui să fie 0 pentru un arbore cu un singur nod? Aceasta returnează 1. –  > Por Matthew Flaschen.
  • @Matthew: Aveți dreptate, dar eu am sugerat ca funcția sa publică să scadă 1 din rezultat. În schimb, ați putea „repara” funcția recursivă prin returnarea lui -1 în cazul de bază. –  > Por Stephen.
  • pentru un arbore cu un singur nod, înălțimea arborelui este 0. deci pentru un arbore gol, înălțimea este -1. Acesta este motivul pentru care return -1 funcționează și nu return 0 atunci când nodul este NULL –  > Por AruniRC.
Harish
int getHeight(Node node) {
 if (node == null) return -1;

 return 1 + Math.max(getHeight(node.left), getHeight(node.right));
}

Jerry Coffin

După părerea mea, codul dvs. ar fi bine să fie puțin simplificat. În loc să încercați să încheiați recursivitatea atunci când un copil este nul, ar trebui să o încheiați doar atunci când pointerul curent pointerul curent este nul. Astfel, codul este mult mai simplu de scris. În pseudocod, arată cam așa:

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

Comentarii

  • Totuși, nu se poate apela o metodă pe un obiect nul 🙂 –  > Por jemfinch.
  • @jemfinch, unde o cheamă pe un obiect nul, nu pentru asta este cazul de bază? –  > Por Corey.
  • @jemfinch:Cred că este un lucru bun că nu am sugerat să fac un astfel de lucru! –  > Por Jerry Coffin.
  • de ce returnezi 0 în loc de -1? –  > Por johnny 5.
  • @JerryCoffin Nu îmi fac nicio temă pentru acasă. Este 0 sau -1? Și de ce? –  > Por Faraz.
lingareddyk

Pentru cei ca mine, cărora le plac soluțiile cu o singură linie:

public int getHeight(Node root) {
    return Math.max(root.left != null ? getHeight(root.left) : -1, 
                    root.right != null ? getHeight(root.right) : -1) 
                    + 1;
}

Matthew Flaschen

Iată o modalitate concisă și, sperăm, corectă de exprimare:

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

Dacă nodul curent este nul, nu există niciun arbore. Dacă ambii copii sunt, există un singur strat, ceea ce înseamnă 0 înălțime. Aceasta folosește definiția înălțimii (menționată de Stephen) ca fiind # de straturi – 1

utilizator17711
class Solution{
    public static int getHeight(Node root) {
        int height = -1;

        if (root == null) {
            return height;
        } else {
            height = 1 + Math.max(getHeight(root.left), getHeight(root.right));
        }

        return height;
    }

jemfinch

Acest lucru nu este testat, dar este destul de evident că este corect:

private int findHeight(Treenode<T> aNode) {
  if (aNode.left == null && aNode.right == null) {
    return 0; // was 1; apparently a node with no children has a height of 0.
  } else if (aNode.left == null) {
    return 1 + findHeight(aNode.right);
  } else if (aNode.right == null) {
    return 1 + findHeight(aNode.left);
  } else {
    return 1 + max(findHeight(aNode.left), findHeight(aNode.right));
  }
}

De multe ori, simplificarea codului este mai ușoară decât să vă dați seama de ce este greșit cu un punct. Acest cod este ușor de înțeles: cele patru cazuri posibile sunt gestionate în mod clar și în mod evident corect:

  • Dacă atât arborele din stânga cât și cel din dreapta sunt nule, se returnează 0, deoarece un singur nod are prin definiție o înălțime de 0. (era 1)
  • În cazul în care fie arborele din stânga, fie cel din dreapta (dar nu ambele!) sunt nule, se returnează înălțimea arborelui care nu este nul, plus 1 pentru a ține cont de înălțimea adăugată a nodului curent.
  • Dacă niciunul dintre cei doi arbori nu este nul, se returnează înălțimea subarborelui mai înalt, din nou plus 1 pentru a ține cont de nodul curent.

Comentarii

  • Acest cod funcționează și este mai clar decât cel pe care îl aveam, însă tot returnează înălțimea +1. În cartea mea, înălțimea este definită ca fiind lungimea drumului de la rădăcină la cea mai adâncă frunză. Deci, din câte am înțeles, un BST care conține 15, 25, 30, 45 (în această ordine) ar avea o înălțime de numai 3, corect? –  > Por mike.
  • De fapt, un arbore care conține doar nodul rădăcină are o înălțime de 0, nu de 1. –  > Por Corey.
  • Ciudat. Chiar nu ar trebui să se numească „înălțime”, dacă ceea ce vor să spună cu adevărat este „căi de coborâre”, dar aceasta pare să fie terminologia standard, din păcate. Modul corect de a remedia acest lucru este de a schimba primul caz (node.left == null && node.right == null) pentru a returna 0. – –  > Por jemfinch.
Desire
    public void HeightRecursive()
    {
        Console.WriteLine( HeightHelper(root) ); 
    }

    private int HeightHelper(TreeNode node)
    {
        if (node == null)
        {
            return -1;
        }
        else
        {
            return 1 + Math.Max(HeightHelper(node.LeftNode),HeightHelper(node.RightNode));           
        }
    }

Cod C#. includeți aceste două metode în clasa BST. aveți nevoie de două metode pentru a calcula înălțimea copacului. HeightHelper o calculează, & HeightRecursive o tipărește în main().

amyers

Definiția dată mai sus a înălțimii este incorectă. Aceasta este definiția adâncimii.

„Adâncimea unui nod M într-un arbore este lungimea drumului de la rădăcina arborelui până la M. Înălțimea unui arbore este cu unu mai mare decât adâncimea celui mai adânc nod din arbore. Toate nodurile de adâncime d se află la nivelul d în arbore. Rădăcina este singurul nod de la nivelul 0, iar adâncimea sa este 0.”

Citare: „A Practical Introduction to Data Structures and Algorithm Analysis „Ediția 3.2 (Java Version)Clifford A. ShafferDepartment of Computer ScienceVirginia TechBlacksburg, VA 24061

Saikrishna Rao
public int height(){

    if(this.root== null) return 0;

    int leftDepth = nodeDepth(this.root.left, 1);
    int rightDepth = nodeDepth(this.root.right, 1);

    int height = leftDepth > rightDepth? leftDepth: rightDepth;

    return height;
}


private int nodeDepth(Node node, int startValue){

    int nodeDepth = 0;

    if(node.left == null && node.right == null) return startValue;
    else{
        startValue++;
        if(node.left!= null){
            nodeDepth = nodeDepth(node.left, startValue);
        }

        if(node.right!= null){
            nodeDepth = nodeDepth(node.right, startValue);
        }
    }

    return nodeDepth;
}

Acekizzy

//funcție pentru a găsi înălțimea BST

int height(Node* root) {
    if(root == NULL){
        return -1;
    }

    int sum=0;
    int rheight = height(root->right);
    int lheight = height(root->left);

    if(lheight>rheight){
        sum = lheight +1;
    }
    if(rheight > lheight){
        sum = rheight + 1;
    }

    return sum;
}

Mahendra suthar
int height(Node* root) {
        if(root==NULL) return -1;
        return max(height(root->left),height(root->right))+1;
}

Se ia înălțimea maximă de la subarborele din stânga și din dreapta și se adaugă 1 la ea.Aceasta gestionează și cazul de bază (înălțimea arborelui cu 1 nod este 0).

Yawar Murtaza

Știu că am ajuns târziu la petrecere. După ce m-am uitat în răspunsurile minunate furnizate aici, m-am gândit că al meu va adăuga ceva valoare la acest post. Deși răspunsurile postate sunt uimitoare și ușor de înțeles, totuși, toate calculează înălțimea la BST în timp liniar. Cred că acest lucru poate fi îmbunătățit și Înălțimea poate fi recuperată în constantă timp constant, de aici și scrierea acestui răspuns – sper că vă va plăcea.Să începem cu Nod clasă:

public class Node
{
    public Node(string key)
    {
        Key = key;
        Height = 1;
    }    

    public int Height { get; set; } 
    public string Key { get; set; }
    public Node Left { get; set; }
    public Node Right { get; set; }

    public override string ToString()
    {
        return $"{Key}";
    }
}

BinarySearchTree clasa

Poate ați ghicit care este șmecheria aici… Păstrez variabila de instanță a nodului Height pentru a ține evidența fiecărui nod atunci când este adăugat.Să trecem la clasa BinarySearchTree care ne permite să adăugăm noduri în BST-ul nostru:

public class BinarySearchTree
{
    public Node RootNode { get; private set; }

    public void Put(string key)
    {
        if (ContainsKey(key))
        {
            return;
        }

        RootNode = Put(RootNode, key);
    }

    private Node Put(Node node, string key)
    {
        if (node == null) return new Node(key);

        if (node.Key.CompareTo(key) < 0)
        {
            node.Right = Put(node.Right, key);
        }
        else
        {
            node.Left = Put(node.Left, key);
        }       
        
        // since each node has height property that is maintained through this Put method that creates the binary search tree.
        // calculate the height of this node by getting the max height of its left or right subtree and adding 1 to it.        
        node.Height = Math.Max(GetHeight(node.Left), GetHeight(node.Right)) + 1;
        return node;
    }

    private int GetHeight(Node node)
    {
        return node?.Height ?? 0;
    }

    public Node Get(Node node, string key)
    {
        if (node == null) return null;
        if (node.Key == key) return node;

        if (node.Key.CompareTo(key) < 0)
        {
            // node.Key = M, key = P which results in -1
            return Get(node.Right, key);
        }

        return Get(node.Left, key);
    }

    public bool ContainsKey(string key)
    {
        Node node = Get(RootNode, key);
        return node != null;
    }
}

După ce am adăugat cheia, valorile în BST, putem apela proprietatea Height a obiectului RootNode care ne va returna înălțimea arborelui RootNode în constantă truc este de a menține înălțimea actualizată atunci când un nou nod este adăugat în arbore.Sper că acest lucru ajută pe cineva din lumea sălbatică a pasionaților de informatică!

Test de unitate:

[TestCase("SEARCHEXAMPLE", 6)]
[TestCase("SEBAQRCHGEXAMPLE", 6)]
[TestCase("STUVWXYZEBAQRCHGEXAMPLE", 8)]
public void HeightTest(string data, int expectedHeight)
{
    // Arrange.
    var runner = GetRootNode(data);

    
    //  Assert.
    Assert.AreEqual(expectedHeight, runner.RootNode.Height);
}

private BinarySearchTree GetRootNode(string data)
{
    var runner = new BinarySearchTree();
    foreach (char nextKey in data)
    {
        runner.Put(nextKey.ToString());
    }

    return runner;
}

Notă: Această idee de menținere a înălțimii arborelui la fiecare operațiune Put este inspirată de metoda Size of BST, care se găsește în capitolul 3 (pagina 399) din cartea Algorithm (ediția a patra).

Mr_Hmp

Cred că această întrebare poate însemna două lucruri diferite…

  1. Înălțimea este numărul de noduri din cea mai lungă ramură:-

    int calcHeight(node* root){
    if(root==NULL)
    return 0;
    int l=calcHeight(root->left);
    int r=calcHeight(root->right);
    if(l>r)
    return l+1;
    else
    return r+1;
    }

  2. Înălțimea este numărul total de noduri din arbore în sine:

    int calcSize(node* root){
    if(root==NULL)
    return 0;
    return(calcSize(root->left)+1+calcSize(root->right));
    }

avishek gurung
public int getHeight(Node node)
{
    if(node == null)
        return 0;

    int left_val = getHeight(node.left);
    int right_val = getHeight(node.right);
    if(left_val > right_val)
        return left_val+1;
    else
        return right_val+1;
}

Atira_Jak

Setați o tempHeight ca variabilă statică (inițial 0).

static void findHeight(Node node node, int count) {

    if (node == null) {
        return;
    }
    if ((node.right == null) && (node.left == null)) {
        if (tempHeight < count) {
            tempHeight = count;

        }

    }

    findHeight(node.left, ++count);
    count--; //reduce the height while traversing to a different branch
    findHeight(node.right, ++count);

}

warl0ck

Iată o soluție în Java un pic cam lungă, dar funcționează…

public static int getHeight (Node root){
    int lheight = 0, rheight = 0;
    if(root==null) {
        return 0;
    }
    else {
        if(root.left != null) {
            lheight = 1 + getHeight(root.left);
            System.out.println("lheight" + " " + lheight);
        }
        if (root.right != null) {
            rheight = 1+ getHeight(root.right);
            System.out.println("rheight" + " " + rheight);
        }
        if(root != null && root.left == null && root.right == null) {
            lheight += 1; 
            rheight += 1;
        }

    }
    return Math.max(lheight, rheight);
    }

rashedcs
 int getHeight(Node* root)
 {
   if(root == NULL) return -1;
   else             return max(getHeight(root->left), getHeight(root->right)) + 1;
 }

Vbp

Iată o soluție în C#

    private static int heightOfTree(Node root)
    {
        if (root == null)
        {
            return 0;
        }

        int left = 1 + heightOfTree(root.left);
        int right = 1 + heightOfTree(root.right);

        return Math.Max(left, right);
    }

Aalyiah7492

Pentru oricine altcineva care citește acest!!!!

Înălțimea este definită ca fiind numărul de noduri din cea mai lungă cale de la nodul rădăcină la un nod frunză. Prin urmare: un arbore care are doar un nod rădăcină are înălțimea 1 și nu 0.

NIVELUL unui anumit nod este distanța de la rădăcină plus 1. Prin urmare: Rădăcina se află la nivelul 1, nodurile sale copil sunt la nivelul 2 și așa mai departe.

(Informații oferite de Data Structures: Abstraction and Design Using Java, ediția a 2-a, de Elliot B. Koffman & Paul A. T. Wolfgang) – Carte utilizată în cadrul cursului de structuri de date pe care îl urmez în prezent la Columbus State University.

Comentarii

  • PENTRU ORICINE ALTCINEVA CARE CITEȘTE ACEST!!!! Această definiție a înălțimii este greșită! Înălțimea unui arbore este numărul de muchii de la nodul rădăcină până la cel mai îndepărtat nod de frunze (sau unul dintre cele mai îndepărtate dacă există un număr de frunze echidistante). Deoarece este vorba de muchii, un arbore care are doar un nod rădăcină va avea o înălțime de zero. Mergeți la ro.wikipedia.org/wiki/Tree_(data_structure)#Definition și se citește „Înălțimea nodului” și „Înălțimea copacului”. În plus, atât manualele de algoritmi Cormen, cât și Weiss susțin această definiție. Definiția dată pentru nivel este corectă. –  > Por Nick Chapman.
saikat sarkar

introduceți aici descrierea imaginii

Conform cărții „Introduction to Algorithms” de Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest și Clifford Stein, următoarea definiție a înălțimii arborelui este următoarea:

Înălțimea unui nod dintr-un arbore este numărul de muchii de pe cea mai lungă cale descendentă simplă de la nodul respectiv la o frunză, iar înălțimea unui arbore este înălțimea rădăcinii sale. Înălțimea unui arbore este, de asemenea, egală cu cea mai mare adâncime a oricărui nod din arbore.

În continuare este soluția mea ruby. Majoritatea oamenilor au uitat de înălțimea arborelui gol sau a arborelui cu un singur nod în implementarea lor.

def height(node, current_height)
  return current_height if node.nil? || (node.left.nil? && node.right.nil?)
  return [height(node.left, current_height + 1), height(node.right, current_height + 1)].max if node.left && node.right
  return height(node.left, current_height + 1) if node.left
  return height(node.right, current_height + 1)
end

Phat Nguyen
int maxDepth(BinaryTreeNode root) {
    if(root == null || (root.left == null && root.right == null)) {
       return 0;
    }

    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

Comentarii

  • Bună Phat, bine ai venit pe StackOverflow. Ai putea să adaugi câteva propoziții la răspunsul tău pentru a explica care este punctul central. Asta l-ar face mai util. –  > Por Kaadzia.
  • btw nu este nevoie să verifici pe null root.left și root.right -.  > Por Normal.
RAJNISH YADAV

Înălțimea arborelui binar

public static int height(Node root)
    {
        // Base case: empty tree has height 0
        if (root == null) {
            return 0;
        }

        // recursively for left and right subtree and consider maximum depth
        return 1 + Math.max(height(root.left), height(root.right));
    }