正确地从树中删除节点
|
我有以下修剪树数据结构的功能：
public static void pruneTree(final ConditionTreeNode treeNode) {
final List<ConditionTreeNode> subTrees = treeNode.getSubTrees();
for (ConditionTreeNode current : subTrees) {
pruneTree(current);
}
if(subTrees.isEmpty()) {
final ConditionTreeNode parent = treeNode.getParent();
parent.removeConditionTreeNode(treeNode);
}
if (treeNode.isLeaf()) {
//this is the base case
if (treeNode.isPrunable()) {
final ConditionTreeNode parent = treeNode.getParent();
parent.removeConditionTreeNode(treeNode);
}
return;
}
}
没有找到相关结果
已邀请:
2 个回复
掸牛浓疗
搁手
public boolean remove( int target ) { if( find( target ) ) //TreeNode containing target found in Tree { if( target == root.getInfo( ) ) //target is in root TreeNode { if( root.isLeaf( ) ) root = null; else if( root.getRight( ) == null ) root = root.getLeft( ); else if( root.getLeft( ) == null ) root = root.getRight( ); else { root.getRight( ).getLeftMostNode( ).setLeft( root.getLeft( ) ); root = root.getRight( ); } } else //TreeNode containing target is further down in Tree { if( cursor.isLeaf( ) ) //TreeNode containing target has no children { if( target <= precursor.getInfo( ) ) precursor.removeLeftMost( ); else precursor.removeRightMost( ); } else if( cursor.getRight( ) == null ) //TreeNode containing target { //has no right subtree if( target <= precursor.getInfo( ) ) precursor.setLeft( cursor.getLeft( ) ); else precursor.setRight( cursor.getLeft( ) ); } else if( cursor.getLeft( ) == null ) //TreeNode containing target { //has no left subtree if( target <= precursor.getInfo( ) ) precursor.setLeft( cursor.getRight( ) ); else precursor.setRight( cursor.getRight( ) ); } else //TreeNode containing target has two subtrees { cursor.getRight( ).getLeftMostNode( ).setLeft( cursor.getLeft( ) ); if( target <= precursor.getInfo( ) ) precursor.setLeft( cursor.getRight( ) ); else precursor.setRight( cursor.getRight( ) ); } } cursor = root; return true; } else //TreeNode containing target not found in Tree return false; }