Wat is het verschil tussen boomdiepte en hoogte?

Dit is een simpele vraag uit de algoritmentheorie.
Het verschil tussen beide is dat je in het ene geval het aantal knooppunten telt en in het andere het aantal randen op het kortste pad tussen wortel en betonnen knooppunt.
Welke is wat?

Antwoord 1, autoriteit 100%

Ik heb geleerd dat diepte en hoogte eigenschappen zijn van een knooppunt:

• De dieptevan een knoop is het aantal randen van de knoop tot de wortelknoop van de boom.
  Een hoofdknoop heeft een diepte van 0.

• De hoogtevan een knooppunt is het aantal randen op het langste padvan het knooppunt naar een blad.
  Een bladknooppunt heeft een hoogte van 0.

Eigenschappen van een boom:

• De hoogtevan een boom is de hoogte van de wortelknoop,
  of equivalent, de diepte van de diepste knoop.

• De diameter(of breedte) van een boom is het aantal knopenop het langste pad tussen twee willekeurige bladknopen . De onderstaande boom heeft een diameter van 6 knopen.

Antwoord 2, autoriteit 6%

hoogte en diepte van een boom is gelijk…

maar de hoogte en diepte van een knoop is niet gelijk omdat…

de hoogte wordt berekend door van het gegeven knooppunt naar het diepst mogelijke blad te gaan.

diepte wordt berekend op basis van het doorlopen van de wortel naar het opgegeven knooppunt…..

Antwoord 3, autoriteit 2%

Volgens Cormen et al. Inleiding tot Algoritmen (Appendix B.5.3), de diepte van een knoop X in een boom T wordt gedefinieerd als de lengte van het eenvoudige pad (aantal randen) van de wortelknoop van T naar X. De hoogte van een knoop Y is het aantal randen op het langsteneerwaartse eenvoudige pad van Y naar een blad. De hoogte van een boom wordt gedefinieerd als de hoogte van zijn wortelknooppunt.

Merk op dat een eenvoudig pad een pad is zonder herhaalde hoekpunten.

De hoogte van een boomis gelijk aan de maximale diepte van een boom. De diepte van een knoop en de hoogte van een knoop zijn niet noodzakelijk gelijk. Zie figuur B.6 van de 3e editie van Cormen et al. voor een illustratie van deze concepten.

Ik heb soms problemen gezien met het vragen om knooppunten (hoekpunten) in plaats van randen te tellen, dus vraag om opheldering als u niet zeker weet of u knooppunten of randen moet tellen tijdens een examen of een sollicitatiegesprek.

Antwoord 4

Ik weet dat het raar is, maar Leetcode definieert diepte ook in termen van het aantal knooppunten in het pad. Dus in zo’n geval moet de diepte beginnen bij 1 (tel altijd de wortel) en niet bij 0. Voor het geval iemand dezelfde verwarring heeft als ik.

Antwoord 5

Eenvoudig antwoord:

Diepte:

1. Boom: Aantal randen/boogvan het wortelknooppunt tot het bladknooppunt van de boom wordt de diepte van de boom genoemd.

2. Knooppunt: Aantal randen/boogvan het hoofdknooppunt naar dat knooppunt wordt de diepte van dat knooppunt genoemd.

Antwoord 6

Een andere manier om dit concept te begrijpen is als volgt:
Diepte: Trek een horizontale lijn bij de wortelpositie en behandel deze lijn als grond. Dus de diepte van de wortel is 0, en al zijn kinderen groeien naar beneden, dus elk niveau van knopen heeft de huidige diepte + 1.

Hoogte: dezelfde horizontale lijn, maar deze keer is de grondpositie externe knooppunten, het blad van een boom en tel omhoog.

Antwoord 7

Ik wilde dit bericht plaatsen omdat ik een bachelorstudent CS ben en we steeds meer OpenDSA en andere open source-leerboeken gebruiken. Het lijkt uit het best beoordeelde antwoord dat de manier waarop hoogte en diepte wordt onderwezen van de ene generatie op de andere is veranderd, en ik plaats dit zodat iedereen weet dat deze discrepantie nu bestaat en hopelijk geen bugs zal veroorzaken in programma’s! Bedankt.

Van de OpenDSA Gegevensstructuren & Algos boek:

Als n₁, n₂,…,n_keen reeks knopen in de boom is, zoals
dat n_ide ouder is van n_i+1 voor 1<=i<k, dan is deze reeks
wordt een pad genoemd van n₁naar n_k. De lengte van het pad is k−1.
Als er een pad is van knoop R naar knoop M, dan is R een voorouder van
M, en M is een afstammeling van R. Dus alle knopen in de boom zijn
afstammelingen van de wortel van de boom, terwijl de wortel de voorouder is van
alle knooppunten. De diepte van een knoop M in de boom is de lengte van de
pad van de wortel van de boom naar M. De hoogte van een boom is één meer
dan de diepte van het diepste knooppunt in de boom.Alle knooppunten met diepte d
bevinden zich op niveau d in de boom. De wortel is het enige knooppunt op niveau 0, en
de diepte is 0.

Figuur 7.2.1: Een binaire boom. Knooppunt A is de wortel. Knooppunten B en C zijn
A’s kinderen. Knooppunten B en D vormen samen een deelboom. Knooppunt B heeft
twee kinderen: het linkerkind is de lege boom en het rechterkind is
D. Knooppunten A, C en E zijn voorouders van G. Knooppunten D, E en F
make-up niveau 2 van de boom; knoop A bevindt zich op niveau 0. De randen van A
naar C naar E naar G vormen een pad met lengte 3. Knooppunten D, G, H en I
zijn bladeren. Knooppunten A, B, C, E en F zijn interne knooppunten. De diepte
van I is 3. De hoogte van deze boom is 4.

Antwoord 8

Het antwoord van Daniel A.A. De analogie van Pelsmaeker en Yesh is uitstekend. Ik zou graag wat meer willen toevoegen aan de hackerrank-tutorial. Ik hoop dat het ook een beetje helpt.

• De diepte (of het niveau) van een knoop is de afstand (d.w.z. het aantal randen) vanaf de wortelknoop van de boom.
• De hoogte is het aantal randen tussen de wortelknoop en het verste blad.
• height(node) = 1 + max(height(node.leftSubtree),height(node.rightSubtree)).
  Houd rekening met de volgende punten voordat u het volgende voorbeeld leest.
• Elke knoop heeft een hoogte van 1.
• Hoogte van lege substructuur is -1.
• Hoogte van een enkel element boom of bladknooppunt is 0.
  

Antwoord 9

De “diepte” (of equivalent het “niveaunummer”) van een knooppunt is het aantal randen op het “pad” vanaf het hoofdknooppunt

De “hoogte” van een knoop is het aantal randen op het langste pad van de knoop naar een bladknoop.

Antwoord 10

De totale diepte van de boom is gelijk aan de hoogte van de boom en hetzelfde voor het niveau van de boom, maar als voor een bepaald knooppunt de hoogte niet gelijk is aan de diepte omdat de definitie van Dieptestelt dat het langste pad van het hoofdknooppunt naar dat knooppunt, in het geval van Hoogtehet is van dat knooppunt naar het bladknooppunt.

algemene boom, D=H=L
maar voor een knoop D=L Maar D kan niet gelijk zijn aan H.