Wie bekomme ich das erste Element, wenn ich mit inorder einen binären Suchbaum durchblättere?

Question

Mein Versuch (gab mir eine Nullpointer):

public Karte giveFirst(BinarySearchTree<Karte> t){ 
    if(t.getLeftTree() != null) { 
     return giveFirst(t.getLeftTree()); 
    }else{ 
     return t.getContent(); 
    } 
} 

komplette binärer Suchbaum-Code:

package Model; 


    private class BSTNode<CT extends ComparableContent<CT>> { 

     private CT content; 
     private BinarySearchTree<CT> left, right; 

     public BSTNode(CT pContent) { 

      this.content = pContent; 
      left = new BinarySearchTree<CT>(); 
      right = new BinarySearchTree<CT>(); 
     } 

    } 

    private BSTNode<ContentType> node; 

    public BinarySearchTree() { 
     this.node = null; 
    } 

    public void insert(ContentType pContent) { 
     if (pContent != null) { 
      if (isEmpty()) { 
       this.node = new BSTNode<ContentType>(pContent); 
      } else if (pContent.isLess(this.node.content)) { 
       this.node.left.insert(pContent); 
      } else if(pContent.isGreater(this.node.content)) { 
       this.node.right.insert(pContent); 
      } 
     } 
    } 

    public BinarySearchTree<ContentType> getLeftTree() { 
     if (this.isEmpty()) { 
      return null; 
     } else { 
      return this.node.left; 
     } 
    } 

    public ContentType getContent() { 
     if (this.isEmpty()) { 
      return null; 
     } else { 
      return this.node.content; 
     } 
    } 

    public BinarySearchTree<ContentType> getRightTree() { 
     if (this.isEmpty()) { 
      return null; 
     } else { 
      return this.node.right; 
     } 
    } 

    public void remove(ContentType pContent) { 
     if (isEmpty()) { 
      return; 
     } 

     if (pContent.isLess(node.content)) { 
      node.left.remove(pContent); 
     } else if (pContent.isGreater(node.content)) { 
      node.right.remove(pContent); 
     } else { 
      if (node.left.isEmpty()) { 
       if (node.right.isEmpty()) { 
        node = null; 
       } else { 
        node = getNodeOfRightSuccessor(); 
       } 
      } else if (node.right.isEmpty()) { 
       node = getNodeOfLeftSuccessor(); 
      } else { 
       if (getNodeOfRightSuccessor().left.isEmpty()) { 
        node.content = getNodeOfRightSuccessor().content; 
        node.right = getNodeOfRightSuccessor().right; 
       } else { 
        BinarySearchTree<ContentType> previous = node.right 
          .ancestorOfSmallRight(); 
        BinarySearchTree<ContentType> smallest = previous.node.left; 
        this.node.content = smallest.node.content; 
        previous.remove(smallest.node.content); 
       } 
      } 
     } 
    } 

    public ContentType search(ContentType pContent) { 
     if (this.isEmpty() || pContent == null) { 
      return null; 
     } else { 
      ContentType content = this.getContent(); 
      if (pContent.isLess(content)) { 
       return this.getLeftTree().search(pContent); 
      } else if (pContent.isGreater(content)) { 
       return this.getRightTree().search(pContent); 
      } else if (pContent.isEqual(content)) { 
       return content; 
      } else { 
       return null; 
      } 
     } 
    } 
    private BinarySearchTree<ContentType> ancestorOfSmallRight() { 
     if (getNodeOfLeftSuccessor().left.isEmpty()) { 
      return this; 
     } else { 
      return node.left.ancestorOfSmallRight(); 
     } 
    } 

    private BSTNode<ContentType> getNodeOfLeftSuccessor() { 
     return node.left.node; 
    } 

    private BSTNode<ContentType> getNodeOfRightSuccessor() { 
     return node.right.node; 
    } 

} 

("Es sieht aus wie Sie Ihre Post meist Code ist, fügen Sie bitte einige weitere Details" ^^) Wie kann ich meinen Code ändern/umschreiben, damit er funktioniert? Jede Hilfe wird geschätzt!

Answer 1

Überlegen Sie, was passieren würde, wenn Sie den linken Blattknoten erreichen.

Ihr linker Baum ist Null, was bedeutet, dass Sie aus der while-Schleife ausbrechen werden. Sie geben danach null zurück, und jeder Versuch, auf den Status des Rückgabewerts zuzugreifen, löst eine Ausnahme aus.

Sie müssen diesen Knoten zurück, wenn es nicht mehr linke Kinder hat wie das kleinste Element im Baum auch

Answer 2

sein wird, weiß ich nicht, warum Sie BinarySearchTree und BSTNode haben. A BSTNode sollte gut genug sein, um einen Baum zu konstruieren. Bitte gehen Sie ein paar Tutorials/Lektionen zum besseren Verständnis durch.

Wie erhält man das erste Element, wenn man einen binären Suchbaum mit inorder durchläuft?

Gehen Sie weiter nach links, bis Sie nicht mehr links gehen können ... Wenn ein Knoten ein linkes Kind hat, gehen Sie darauf. Machen Sie das so lange, bis Sie zu einem Knoten gelangen, der kein linkes Kind mehr hat. Wenn Sie dort sind, wissen Sie, dass Sie sich im linken Teil des Baumes befinden. Das folgende Code-Snippet zeigt eine Vorstellung davon, wie dies mit der root eines BST erreicht werden kann.

public BSTNode getSmallest(BSTNode root) { 
    if(root.left != null) 
     return getSmallest(root.left); 
    return root; 
}