Comment supprimer les feuilles d'un arbre binaire?

Question

J'essaye d'enlever toutes les feuilles. Je sais que les feuilles n'ont pas d'enfants, c'est ce que j'ai jusqu'ici.

public void removeLeaves(BinaryTree n){ 

    if (n.left == null && n.right == null){ 

     n = null; 

    } 

    if (n.left != null) 

     removeLeaves(n.left); 

    if (n.right != null) 

     removeLeaves(n.right); 

} 

Answer 1

Il est beaucoup plus facile si vous décomposer comme ceci:

public void removeLeaves(BinaryTree n){ 
    if (n.left != null) { 
    if (n.left.isLeaf()) { 
     n.removeLeftChild(); 
    } else { 
     removeLeaves(n.left); 
    } 
    } 
    // repeat for right child 
    // ... 
} 

isLeaf, removeLeftChild et removeRightChild devrait être trivial à mettre en œuvre.

Answer 2

au lieu de n = null, il devrait être:

if(n.parent != null) 
    { 
    if(n.parent.left == n) 
    { 
     n.parent.left = null; 
    } 
    else if(n.parent.right == n) 
    { 
     n.parent.right == null); 
    } 
    } 

Answer 3

n = null; ne vous aidera pas, puisque n est juste une variable locale de votre fonction. Au lieu de cela, vous devez définir n.left = null; ou n.right = null; sur le parent.

Je ne vais pas vous donner une solution complète, car cela ressemble beaucoup à des devoirs, mais vous pouvez, par exemple, ajouter une valeur de retour à votre fonction pour indiquer si le noeud en question est une feuille et prendre actions appropriées dans le parent (après l'appel à removeLeaves).

Answer 4

Puisque Java passe les références par les valeurs n = null; ne fonctionne tout simplement pas. Avec cette ligne n pointait vers la feuille et ne pointe plus vers rien. Donc, vous ne le supprimez pas du parent, vous réacheminez simplement une référence locale factice. Pour la solution faites ce que Matthew a suggéré.

Answer 5

/* @author abhineet*/ 

public class DeleteLeafNodes { 


    static class Node{ 
     int data; 
     Node leftNode; 
     Node rightNode; 
     Node(int value){ 
      this.data = value; 
      this.leftNode = null; 
      this.rightNode = null; 
     } 
    } 



    public static void main(String[] args) { 

     Node root = new Node(1); 
     Node lNode = new Node(2); 
     lNode.leftNode = new Node(4); 
     root.leftNode = lNode; 
     Node rNode = new Node(3); 
     rNode.rightNode = new Node(5); 
     root.rightNode = rNode; 
     printTree(root); 
     deleteAllLeafNodes(root, null,0); 
     System.out.println("After deleting leaf nodes::"); 
     printTree(root); 

    } 

    public static void deleteAllLeafNodes(Node root, Node parent, int direction){ 
     if(root != null && root.leftNode == null && root.rightNode == null){ 
      if(direction == 0){ 
       parent.leftNode = null; 
      }else{ 
       parent.rightNode = null; 
      } 

     } 
     if(root != null && (root.leftNode != null || root.rightNode != null)){ 
      deleteAllLeafNodes(root.leftNode, root, 0); 
      deleteAllLeafNodes(root.rightNode, root, 1); 
     } 

    } 
    public static void printTree(Node root){ 
     if(root != null){ 
      System.out.println(root.data); 
      printTree(root.leftNode); 
      printTree(root.rightNode); 
     } 
    } 

} 

Answer 6

est ici un simple méthode java à nœuds feuilles suppression de l'arbre binaire

public BinaryTreeNode removeLeafNode(BinaryTreeNode root) { 
    if (root == null) 
     return null; 
    else { 
     if (root.getLeft() == null && root.getRight() == null) {  //if both left and right child are null 
      root = null;            //delete it (by assigning null) 
     } else { 
      root.setLeft(removeLeafNode(root.getLeft()));   //set new left node 
      root.setRight(removeLeafNode(root.getRight()));   //set new right node 
     } 
     return root; 
    } 

} 

Answer 7

Cela devrait TRAVAiL

public boolean removeLeaves(Node n){ 
    boolean isLeaf = false; 
    if (n.left == null && n.right == null){ 
     return true; 
     //n = null; 
    } 

    if (n!=null && n.left != null){ 

     isLeaf = removeLeaves(n.left); 
     if(isLeaf) n.left=null; //remove left leaf 
    } 

    if (n!=null && n.right != null){ 

     isLeaf = removeLeaves(n.right); 
     if(b) n.right=null; //remove right leaf 
    } 
    return false; 

}