Как удалить листья двоичного дерева?

Question

Я пытаюсь удалить все листья. Я знаю, что у листьев нет детей, это то, что у меня есть до сих пор.

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

Это гораздо проще, если вы нарушите это вниз, как это:

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 и removeRightChild должны быть просто реализовать.

Answer 2

Вместо п = NULL, это должно быть:

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; не поможет, так как n только локальная переменная вашей функции. Вместо этого вам нужно будет установить n.left = null; или n.right = null; на родителя.

Я не дам вам полного решения, так как это сильно пахнет домашней работой, но вы можете, например, добавить возвращаемое значение к своей функции, чтобы указать, является ли данный узел листом или нет, и принять соответствующие действия в родительском (после вызова removeLeaves).

Answer 4

Поскольку Java передает ссылки по значениям n = null;, это просто не работает. С этой линией n указывала на лист и теперь ничего не указывает. Таким образом, вы фактически не удаляете его из родителя, вы просто перенаправляете фиктивную локальную ссылку. Для решения делайте то, что предложил Мэтью.

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

Вот простой Java метод к Удаление листьев узлы из бинарного дерева

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

Это должно работы-

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; 

}