Ik vroeg me af of iemand me zou kunnen helpen deze methode te herwerken om de hoogte van een binaire zoekboom te vinden. Tot nu toe ziet mijn code er zo uit. Het antwoord dat ik krijg is echter met 1 groter dan de werkelijke hoogte. Maar wanneer ik de +1 uit mijn retourverklaringen verwijder, is het minder dan de werkelijke hoogte met 1. Ik probeer nog steeds mijn hoofd rond recursie te wikkelen met deze BST. Alle hulp wordt zeer op prijs gesteld.
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;
}
}
Antwoord 1, autoriteit 100%
Het probleem ligt in uw basisscenario.
“De hoogte van een boom is de lengte van het pad van de wortel naar het diepste knooppunt in de boom. Een (gewortelde) boom met alleen een knooppunt (de wortel) heeft een hoogte van nul.” – Wikipedia
Als er geen knoop is, wil je -1 en niet 0 teruggeven. Dit komt omdat je aan het einde 1 toevoegt.
Dus als er geen knooppunt is, retourneert u -1 die de +1 opheft.
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;
}
}
Antwoord 2, autoriteit 28%
De hoogte van een binaire zoekboom is gelijk aan number of layers - 1.
Zie het diagram op http://en.wikipedia.org/wiki/Binary_tree
Uw recursie is goed, dus trek er één af op het hoofdniveau.
Houd er rekening mee dat je de functie een beetje kunt opschonen door null-knooppunten te hanteren:
int findHeight(node) {
if (node == null) return 0;
return 1 + max(findHeight(node.left), findHeight(node.right));
}
Antwoord 3, autoriteit 18%
int getHeight(Node node) {
if (node == null) return -1;
return 1 + Math.max(getHeight(node.left), getHeight(node.right));
}
Antwoord 4, autoriteit 8%
Naar mijn mening zou uw code er baat bij hebben als deze een beetje vereenvoudigd wordt. In plaats van te proberen de recursie te beëindigen wanneer een childaanwijzer nul is, beëindigt u deze alleen wanneer de huidigeaanwijzer is nul. Dat maakt de code een stuk eenvoudiger om te schrijven. In pseudo-code ziet het er ongeveer zo uit:
if (node = null)
return 0;
else
left = height(node->left);
right = height(node->right);
return 1 + max(left, right);
Antwoord 5, autoriteit 4%
Voor mensen zoals ik die van éénregelige oplossingen houden:
public int getHeight(Node root) {
return Math.max(root.left != null ? getHeight(root.left) : -1,
root.right != null ? getHeight(root.right) : -1)
+ 1;
}
Antwoord 6, autoriteit 3%
Hier is een beknopte en hopelijk correcte manier om het uit te drukken:
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;
}
Als het huidige knooppunt null is, is er geen boom. Als beide kinderen zijn, is er een enkele laag, wat 0 hoogte betekent. Dit gebruikt de definitie van hoogte (vermeld door Stephen) als # van lagen – 1
Antwoord 7, autoriteit 3%
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;
}
Antwoord 8, autoriteit 3%
Dit is niet getest, maar overduidelijk correct:
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));
}
}
Vaak is het eenvoudiger om je code te vereenvoudigen dan uit te zoeken waarom deze er één naast zit. Deze code is gemakkelijk te begrijpen: de vier mogelijke gevallen worden duidelijk op een duidelijk correcte manier afgehandeld:
- Als zowel de linker- als de rechterboom nul zijn, retourneert u 0, aangezien een enkel knooppunt per definitie een hoogte van 0 heeft. (was 1)
- Als de linker- of rechterboom (maar niet beide!) Null is, retourneert u de hoogte van de niet-null-boom, plus 1 om rekening te houden met de toegevoegde hoogte van het huidige knooppunt.
- Als geen van beide bomen nul is, retourneert u de hoogte van de hogere substructuur, nogmaals plus één voor het huidige knooppunt.
Antwoord 9, autoriteit 2%
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));
}
}
C#-code.
Neem deze twee methoden op in uw BST-klasse. je hebt twee methoden nodig om de hoogte van de boom te berekenen. HeightHelper berekent het, & HoogteRecursief print het in main().
Antwoord 10
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;
}
Antwoord 11
//functie om hoogte van BST te vinden
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;
}
Antwoord 12
int height(Node* root) {
if(root==NULL) return -1;
return max(height(root->left),height(root->right))+1;
}
Neem de maximale hoogte van de linker- en rechtersubboom en voeg er 1 aan toe. Dit behandelt ook het basisscenario (hoogte van boom met 1 knoop is 0).
Antwoord 13
Ik weet dat ik te laat op het feest ben. Na het bekijken van de prachtige antwoorden die hier worden gegeven, dacht ik dat de mijne enige waarde aan dit bericht zou toevoegen. Hoewel de geposte antwoorden verbazingwekkend en gemakkelijk te begrijpen zijn, berekenen ze allemaal de hoogte tot de BST in lineaire tijd. Ik denk dat dit kan worden verbeterd en dat de hoogte in constantetijd kan worden opgehaald, vandaar dat ik dit antwoord schrijf – ik hoop dat je het leuk zult vinden.
Laten we beginnen met de klasse Node:
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}";
}
}
BinarySearchTreeklasse
Dus je raadt misschien de truc hier… Ik houd de hoogte van de instantie van het knooppunt variabel om elk knooppunt bij te houden wanneer het wordt toegevoegd.
Laten we naar de BinarySearchTree-klasse gaan waarmee we knooppunten kunnen toevoegen aan onze BST:
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;
}
}
Zodra we de sleutel, waarden in de BST hebben toegevoegd, kunnen we de eigenschap Height op het RootNode-object aanroepen die ons de hoogte van de RootNode-boom in constantetijd teruggeeft.
De truc is om de hoogte up-to-date te houden wanneer een nieuwe knoop aan de boom wordt toegevoegd.
Ik hoop dat dit iemand helpt in de wilde wereld van informatica-enthousiastelingen!
Eenheidstest:
[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;
}
Opmerking: dit idee om de hoogte van de boom bij elke putbewerking te behouden, is geïnspireerd op de methode Grootte van BST die te vinden is in het derde hoofdstuk (pagina 399) van Algoritme (vierde editie)boek.
Antwoord 14
Ik denk dat deze vraag twee verschillende dingen kan betekenen…
-
Hoogte is het aantal knopen in de langste tak:-
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;
}
-
Hoogte is het totale aantal knopen in de boomzelf:
int calcSize(node* root){
if(root==NULL)
return 0;
return(calcSize(root->left)+1+calcSize(root->right));
}
Antwoord 15
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;
}
Antwoord 16
Stel een tempHeight in als een statische variabele (aanvankelijk 0).
static void findHeight(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);
}
Antwoord 17
Hier is een oplossing in Java, een beetje lang maar werkt..
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);
}
Antwoord 18
int getHeight(Node* root)
{
if(root == NULL) return -1;
else return max(getHeight(root->left), getHeight(root->right)) + 1;
}
Antwoord 19
Hier is een oplossing in 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);
}
Antwoord 20
Voor iedereen die dit leest!!!!
HEIGHT wordt gedefinieerd als het aantal knooppunten in het langste pad van het hoofdknooppunt naar een bladknooppunt. Daarom: een boom met alleen een wortelknoop heeft een hoogte van 1 en niet van 0.
Het NIVEAU van een bepaald knooppunt is de afstand van de wortel plus 1. Daarom: De wortel bevindt zich op niveau 1, de onderliggende knooppunten bevinden zich op niveau 2 enzovoort.
(Informatie met dank aan Data Structures: Abstraction and Design Using Java, 2nd Edition, door Elliot B. Koffman & Paul A. T. Wolfgang) – Boek gebruikt in de cursus Data Structures die ik momenteel volg aan de Columbus State University.
Antwoord 21
voer hier de afbeeldingsbeschrijving in
Volgens “Inleiding tot algoritmen” door Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest en Clifford Stein volgt de definitie van boomhoogte:
De hoogte van een knoop in a
boom is het aantal randen op het langste eenvoudige neerwaartse pad van het knooppunt naar
een blad, en de hoogte van een boom is de hoogte van zijn wortel. De hoogte van een boom is ook
gelijk aan de grootste diepte van een knoop in de boom.
Hierna volgt mijn robijnrode oplossing. De meeste mensen vergaten de hoogte van een lege boom of een enkele knoop in hun implementatie.
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
Antwoord 22
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));
}
Antwoord 23
Hoogte van binaire boom
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));
}