Meddelande

Du befinner dig just nu på en äldre version av Pluggakuten, gamla.pluggakuten.se. Nya Pluggakuten lanserades den 6 februari 2017 och du finner forumet på www.pluggakuten.se.

På gamla.pluggakuten.se kan du fortfarande läsa frågorna och svaren som ställts, men du kan inte skapa ett nytt konto eller nya trådar. Är du redan medlem kan du däremot fortfarande logga in och svara i befintliga trådar. Nya frågor och nytt konto skapar du på det nya forumet, välkommen dit!

C# binärt sökträd - Ta bort värden ur träd

oskillz
Medlem

Offline

Registrerad: 2016-04-02
Inlägg: 34

C# binärt sökträd - Ta bort värden ur träd

Håller på med en implementation av ett binärt sökträd i c++ och har fastnat på delen där man ska ta bort noder i trädet. Man måste ta hänsyn till tre fall av borttagning, dels när noden är ett löv och därmed inte har några barn noder, dels när noden har ett barn och till sist när noden har två barn. Vi har fått koden för det sista fallet och den ser ut såhär:

Kod:

 public void Delete(int value)
        {

        TreeNode nodeToDelete = new TreeNode(value);
        TreeNode parent = SearchForParent(value);

            TreeNode successor = LeftMostNodeOnRight(nodeToDelete, ref parent);
            TreeNode temp = new TreeNode(successor.value);

            if (parent.left == successor)
            {
                parent.left = successor.right;
            }
            else
                parent.right = successor.right; nodeToDelete.value = temp.value;

        }

När man kallar på Delete() så letar den upp noden med det minsta värdet som är större än värdet man tar bort. Detta görs med metoden LeftMostNodeOnRight() som ser ut enligt:

Kod:

 public TreeNode LeftMostNodeOnRight(TreeNode nodeToDelete, ref TreeNode parent)
        {
            parent = nodeToDelete;
            nodeToDelete = nodeToDelete.right;

            while (nodeToDelete.left != null)
            {
                parent = nodeToDelete;
                nodeToDelete = nodeToDelete.left; 
            }

            return nodeToDelete;            
        }

Men när jag debuggar programmet så får jag NullReferenceException i while loopen och den säger att nodeToDelete är null fastän Delete() metoden visar rätt värde på både nodeToDelete och parent vid metod anropet. Förstår inte riktigt varför det blir så. Är det någon som ser vad som blir fel här? (Fick även LeftMostNodeOnRight() metoden från början.)

Senast redigerat av oskillz (2016-10-10 10:34)

 
oskillz
Medlem

Offline

Registrerad: 2016-04-02
Inlägg: 34

Re: C# binärt sökträd - Ta bort värden ur träd

Hittade vad jag hade gjort fel, skapade en ny nodeToDelete i Delete() metoden istället för att leta upp noden med det sökta värdet med min Find() metod. Det innebar att den nya noden och dess parent bara fanns i scopet för Delete() metoden om jag tänker rätt ^^. Blir till att gå på dom andra fallen för borttagning nu istället.

 


Sidfot

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson

Powered by Mattecentrum
 |  Denna sida använder cookies |  Kontakta oss |  Feedback |