Träd, gräs och stenar

Det blir en del programmering här just nu, men jag kanske är periodare. Eftersom jag är periodare så skriver jag inte kod tillräckligt ofta för att vara speciellt bra på det. Därför kan jag bli entusiastisk över idéer som smarta människor, som DU, tycker är bisarrt uppenbara.

Idag skulle jag skriva en funktion för att kolla hur djupt och brett ett träd är, där varje nod i trädet kan ha ett godtyckligt antal barn. Enligt KISS-principen så delade jag upp den i två, och skrev den enklaste först. Det enklaste är djupet, där man helt enkelt gör en rekursiv djupet-först-sökning (ah, direktöversättningar av datatermer, jag borde söka jobb på IDG) och adderar ett till djupet för varje steg i rekursionen och returnerar det största värdet.

Sen skulle jag göra bredd-funktionen (the bread function), och då tänkte jag först breadth first search. Det är lite jobbigt, man måste hålla i listor med noder så att man inte doppar tårna för djupt innan man har promenerat igenom alla syskon, kusiner, sysslingar, bryllingar, tremänningar etc. Och loopar i koden, känns inte det som att det ökar den cyklomatiska komplexiteten och är allmänt 60-tal sådär? Jo.

Alltså gjorde jag så här istället: jag skrev en rekursiv djupet-först-funktion, till vilken jag skickade med en noll-initialiserad int-array och det aktuella djupet. För varje nod som besöks så ökar jag numret på djupets index i arrayen med ett, och för varje rekursivt anrop så ökar jag djupet med ett. När det första rekursiva anropet returnerar så har jag en array med antalet noder på varje djupnivå, så det är bara att gå igenom den och plocka det största numret i arrayen, som är trädets största bredd. Eller på ren svenska:

void checkBreadthRec(Node node, int currDepth, int breadths[])
    Node curr = GetFirstChild(node)
    
    breadths[currDepth]++    

    while(curr)
        checkBreadthRec(curr, currDepth+1, breadths)
        curr = GetNextSibling(curr)

Det mest komplicerade i den här funktionen är typ att jag använde ordet "breadth" som det är lite jobbigt att skriva och uttala. Om jag har gjort något misstag i pseudo-koden så blir det extra pinsamt, eftersom det här är så sjukt enkelt.