Hvordan avgjøre om en Binary Tre er symmetrisk?

Et binært tre er en av måtene dataene organisert i en datamaskin. Det er en samling av "poster" arrangert på en bestemt måte som gjør postene lett å få tilgang. Den binære treet har en inngangspunkt --- roten, som er adressen til en post. En post kan inneholde noe informasjon, men hvis det er et binært tre, vil det alltid inneholde to adresser til andre poster i minnet. Ideelt sett vil de to adresser i roten være begynnelsen på veier til samme antall poster. Med andre ord, vil treet være symmetriske.

Bruksanvisning

1 Definere noen grunnleggende begreper, slik at vi kan beskrive hva det betyr for et tre for å være symmetrisk. Terminalen noder i et tre kalles bladene. I blad poster, begge adresser er tomt. Adressene i interne noder har adresser til andre poster, og vi si at disse adressene "punkt til venstre og høyre undertrær." En bane er hva vi får hvis vi følger adresse linker fra en node til et blad. Den lengste banen --- størst antall poster --- fra en node er dybden av treet som begynner på node.

2 Skriv funksjonen som ser på hver node i et tre og finner dybden av undertrærne. Den vanlige måten å definere symmetri i et binært tre er "et binært tre er symmetrisk om dybden av undertrærne av enhver node avviker med ikke mer enn en." Dybden funksjonen kan beskrives ved hjelp av tre tilfeller: Dybden fra posten X er null hvis adressene begge undertreene er blank. Hvis bare én adresse er tomt, er dybden en pluss dybden av den andre treet. Hvis ingen adresse er tomt, er dybden en pluss de maksimale dypet av de to undertrær.

3 Bruk dybde funksjonen for å skrive funksjonen som forteller om et tre er symmetrisk. Begynn ved roten av treet og finne dybden på hvert subtre. Ring dypet D1 og D2. Hvis D1 = D2, eller D1 = d2 + 1 eller d2 = d1 + 1, og deretter sette variabelen s for å "true"; ellers gjør s "false". returnere verdien av s som verdien av den symmetri-testfunksjon. På hvert trinn av symmetrien sjekk ser på avkastningen fra symmetri-test av venstre og høyre undertrær. Hvis begge er symmetrisk, returnere verdien "true". Sluttverdien som returneres fra noden vil beskrive den symmetri av treet.

Hint

• Når du finner ut at en node --- inkludert roten --- er ubalansert, trenger du ikke å søke resten av treet. Bygge denne snarveien inn i algoritmen kan gjøre det mye raskere.
• Ikke glem å sjekke for det spesielle tilfellet når treet ikke har noder. En tom tre shold bli vurdert symmetrisk.