从二叉树中删除叶子 [英] Deleting leaves from a binary tree

问题描述

public void deleteLeaves(BSTNode<T> p){                     //deletes leaves
    if(p.left != null){
      if(isLeaf(p.left))
        p.left = null;
    }
    else if(p.right != null){
      if(isLeaf(p.right))
        p.right = null;
    }
    else{
      deleteLeaves(p.right);
      deleteLeaves(p.left); 
    }
  }

我似乎无法弄清楚为什么它没有正确删除叶子.它似乎只删除树的最后一片叶子.任何有帮助的建议将不胜感激.

I cannot seem to figure out as to why it is not correctly deleting the leaves. It seems to only delete the final leaf of the tree. Any advice that helps would greatly be appreciated.

推荐答案

您的if语句有点混乱；仅会使用一个分支.想一想如果高度值p.left或p.right为null会发生什么情况.

Your if-statements are a bit messed up; Only one of the branches will be taken. Think about what should happen if neighter p.left nor p.right is null.

如果我正确理解了您的数据结构，则可能会这样写:

If I understand your data structure correctly, I'd probably write it like this:

// If there is something to the left...
if (p.left != null)
    if (isLeaf(p.left))
        p.left = null;             // delete it if it's a leaf...
    else
        deleteLeaves(p.left);      // else recurse.

// If there's something to the right...
if (p.right != null)
    if (isLeaf(p.right))
        p.right = null;            // delete it if it's a leaf...
    else
        deleteLeaves(p.right);     // else recurse.

这篇关于从二叉树中删除叶子的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！