Kan iemand het verschil uitleggen tussen binaire boomen binaire zoekboommet een voorbeeld?
Antwoord 1, autoriteit 100%
Binaire boom: boom waarbij elke knoop maximaal twee bladeren heeft
1
/ \
2 3
Binaire zoekboom: gebruikt voor zoeken. Een binaire boom waarin het linkerkind alleenknooppunten bevat met waarden die kleiner zijn dan het bovenliggende knooppunt, en waarbij het rechterkind alleenknooppunten bevat met waarden die groter zijn dan of gelijk zijn aan het bovenliggende knooppunt.
2
/ \
1 3
Antwoord 2, autoriteit 10%
Binaire boomis een gespecialiseerde vorm van een boom met twee kinderen (links kind en rechts Kind).
Het is gewoon een weergave van gegevens in de boomstructuur
Binaire zoekboom (BST)is een speciaal type binaire boom die volgt op de volgende staat:
- linker onderliggend knooppunt is kleiner dan het bovenliggende knooppunt
- rechter onderliggende node is groter dan zijn bovenliggende node
Antwoord 3, autoriteit 7%
Een binaire boomis gemaakt van knooppunten, waarbij elk knooppunt een “links”-aanwijzer, een “rechts”-aanwijzer en een gegevenselement bevat. De “root”-aanwijzer wijst naar het bovenste knooppunt in de boom. De linker- en rechteraanwijzers wijzen recursief naar kleinere “subbomen” aan weerszijden. Een null-pointer vertegenwoordigt een binaire boom zonder elementen – de lege boom. De formele recursieve definitie is: een binaire boom is ofwel leeg (weergegeven door een nulaanwijzer), of bestaat uit een enkel knooppunt, waarbij de linker- en rechteraanwijzers (recursieve definitie verderop) elk naar een binaire boom wijzen.
Een binaire zoekboom(BST) of “geordende binaire boom” is een type binaire boom waarin de knooppunten in volgorde zijn gerangschikt: voor elk knooppunt zijn alle elementen in de linker subboom minder het knooppunt (<), en alle elementen in de rechter subboom zijn groter dan het knooppunt (>).
5
/ \
3 6
/ \ \
1 4 9
De hierboven getoonde boom is een binaire zoekboom — het “root” knooppunt is een 5, en de linker subboom knooppunten (1, 3, 4) zijn < 5, en de rechter subboomknooppunten (6, 9) zijn > 5. Recursief moet elk van de subbomen ook voldoen aan de binaire zoekboombeperking: in de (1, 3, 4) substructuur is de 3 de wortel, de 1 < 3 en 4 > 3.
Pas op voor de exacte bewoording in de opgaven — een “binaire zoekboom” is anders dan een “binaire boom”.
Antwoord 4, autoriteit 3%
Zoals iedereen hierboven heeft uitgelegd over het verschil tussen binaire boom en binaire zoekboom, voeg ik alleen toe hoe te testen of de gegeven binaire boom een binaire zoekboom is.
boolean b = new Sample().isBinarySearchTree(n1, Integer.MIN_VALUE, Integer.MAX_VALUE);
.......
.......
.......
public boolean isBinarySearchTree(TreeNode node, int min, int max)
{
if(node == null)
{
return true;
}
boolean left = isBinarySearchTree(node.getLeft(), min, node.getValue());
boolean right = isBinarySearchTree(node.getRight(), node.getValue(), max);
return left && right && (node.getValue()<max) && (node.getValue()>=min);
}
Ik hoop dat het je zal helpen. Sorry als ik afwijk van het onderwerp, want ik vond het de moeite waard om dit hier te vermelden.
Antwoord 5, autoriteit 2%
Binaire boomstaat voor een gegevensstructuurdie bestaat uit knooppuntendie slechts>twee kinderenreferenties.
Binaire zoekboom(BST) daarentegen is een speciale vorm van de gegevensstructuur Binaire boomwaarbij elk knooppunt heeft een vergelijkbare waarde, en kleinere gewaardeerde kinderen gehecht aan links en grotere gewaardeerde kinderen gehecht aan rechts.
Dus alle BST‘s zijn Binary Tree, maar slechts enkele Binary Tree‘s kunnen ook BST. Geef aan dat BSTeen subset is van Binary Tree.
Dus Binaire boomis meer een algemene gegevensstructuur dan Binaire zoekboom. En u moet ook melden dat Binaire zoekboomeen gesorteerdeboom is, terwijl er geen dergelijke set regels is voor generieke Binaire boom.
Binaire boom
Een Binary Treedie geeneen BSTis;
5
/ \
/ \
9 2
/ \ / \
15 17 19 21
Binaire zoekboom (gesorteerde boom)
Een Binaire zoekboomdie ook een Binaire boomis;
50
/ \
/ \
25 75
/ \ / \
20 30 70 80
Binaire zoekboom Node-eigenschap
Vermeld ook dat voor elk bovenliggend knooppuntin de BST;
-
Alle linker knooppunten hebben een kleinere waarde dan de waarde van het bovenliggende knooppunt. In het bovenste voorbeeld zijn de knooppunten met de waarden { 20, 25, 30 } die allemaal aan de linkerkant(links afstammelingen) van 50 liggen, kleiner dan 50.
-
Alle juiste knooppunten hebben een grotere waarde dan de waarde van het bovenliggende knooppunt. In het bovenste voorbeeld zijn de knooppunten met waarden { 70, 75, 80 } die allemaal aan de rechterkant(rechts afstammelingen) van 50 staan, groter dan 50.
Er is geen dergelijke regel voor Binary TreeNode. De enige regel voor Binary TreeNode is het hebben van twee kinderen, dus het verklaart zichzelf waarom het binairwordt genoemd.
Antwoord 6, autoriteit 2%
Een binaire zoekboom is een speciaal soort binaire boom die de volgende eigenschap vertoont: voor elke knoop n is de waarde van elke onderliggende knoop in de linker subboom van n kleiner dan de waarde van n, en de waarde van elke onderliggende knoop in de rechter subboom is groter dan de waarde van n.
Antwoord 7, autoriteit 2%
Binaire boom
Binaire boom kan alleszijn met 2 onderliggende en 1 ouder. Het kan worden geïmplementeerd als gekoppelde lijst of array, of met uw aangepaste API. Zodra je er meer specifieke regels aan begint toe te voegen, wordt het een meer gespecialiseerde boom. De meest bekende implementatie is dat je kleinere knooppunten aan de linkerkant en grotere aan de rechterkant toevoegt.
Bijvoorbeeld een gelabelde binaire boom van grootte 9 en hoogte 3, met een hoofdknooppunt waarvan de waarde 2 is. Boom is ongebalanceerd en niet gesorteerd.
https://en.wikipedia.org/wiki/Binary_tree
Bijvoorbeeld, in de boom aan de linkerkant, heeft A de 6 kinderen {B,C,D,E,F,G}. Het kan worden omgezet in de binaire boom aan de rechterkant.
Binair zoeken
Binair zoeken is een techniek/algoritme dat wordt gebruikt om een specifiek item in een knoopketen te vinden. Binair zoeken werkt op gesorteerde arrays.
Binair zoeken vergelijkt de doelwaarde met het middelste elementvan de array; als ze ongelijk zijn, wordt de helft waarin het doelwit niet kan liggen geëlimineerd en gaat de zoektocht door op de resterende helft totdat deze succesvol is of de resterende helft leeg is. https://en.wikipedia.org/wiki/Binary_search_algorithm
Een boom die binair zoekenvertegenwoordigt. De array die hier wordt doorzocht is [20, 30, 40, 50, 90, 100] en de doelwaarde is 40.
Binaire zoekboom
Dit is een van de implementaties van de binaire boom. Dit is gespecialiseerd voor zoeken.
Binaire zoekstructuur en B-tree-gegevensstructuren zijn gebaseerd op binair zoeken.
Binaire zoekbomen (BST), soms geordende of gesorteerde binaire bomen genoemd, zijn een specifiek type container: gegevensstructuren die “items” (zoals getallen, namen enz.) in het geheugen opslaan . https://en.wikipedia.org/wiki/Binary_search_tree
Een binaire zoekboom van grootte 9 en diepte 3, met 8 aan de basis. De bladeren zijn niet getekend.
En tot slot een geweldig schema voor prestatievergelijking van bekende datastructuren en toegepaste algoritmen:
Afbeelding afkomstig van Algoritmen (4e editie)
Antwoord 8
Een binaire boom is een boom waarvan de kinderen nooit meer dan twee zijn. Een binaire zoekboom volgt de invariant dat het linkerkind een kleinere waarde zou moeten hebben dan de sleutel van het hoofdknooppunt, terwijl het rechterkind een grotere waarde zou moeten hebben dan de sleutel van het hoofdknooppunt.
Antwoord 9
- Binaire zoekboom: wanneer er een inorder-traversal wordt gemaakt op de binaire boom, krijg je gesorteerde waarden van ingevoegde items
- Binaire boom: er is geen gesorteerde volgorde gevonden in welke vorm van traversal dan ook
Antwoord 10
Om te controleren of een bepaalde binaire boom wel of niet een binaire zoekboom is, is hier een alternatieve benadering.
Traverse Tree in Inorder Fashion(d.w.z. Left Child –> Parent –> Right Child ),
Sla de doorkruiste knooppuntgegevens op in een tijdelijke variabele, laten we zeggen temp, net voor het opslaan in temp, controleer of de gegevens van het huidige knooppunt hoger zijn dan de vorige of niet .
Dan breekhet gewoon uit, Boom is niet binair Zoekboom anders doorkruisen tot het einde.
Hieronder staat een voorbeeld met Java:
public static boolean isBinarySearchTree(Tree root)
{
if(root==null)
return false;
isBinarySearchTree(root.left);
if(tree.data<temp)
return false;
else
temp=tree.data;
isBinarySearchTree(root.right);
return true;
}
Temperatuurvariabele buiten behouden
Antwoord 11
In een binaire zoekboom zijn alle knooppunten in een specifieke volgorde gerangschikt – knooppunten links van een hoofdknooppunt hebben een kleinere waarde dan de wortel, en alle knooppunten rechts van een knooppunt hebben waarden die groter zijn dan de waarde van de wortel.
Antwoord 12
Een boom kan als een binaire boom worden aangeroepen als en alleen als het maximum aantal kinderen van een van de knooppunten twee is.
Een boom kan worden aangeroepen als een binaire zoekboom als en alleen als het maximum aantal kinderen van een van de knooppunten twee is en het linkerkind altijd kleiner is dan het rechterkind.