java 二叉树按引用传递删除值为x的树

Question

为什么LeverDeleteX（）方法（BiTree class中最后一个方法）按引用传递删除值为x的树不成功呢？
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.*;
class BiNode{
public String data;
public BiNode lchild;
public BiNode rchild;
public void BiNode(){
}
public void BiNode(String Data){
this.data=Data;
}
}
class Element{
BiNode ptr;
int flag;
}
class BiTree{
public BiNode root;
public int o=1;
public void BiTree(){root=null;}
public BiNode Grow(BiNode node,Scanner scn) {
if(scn.hasNext()){
String temp=scn.next();
if(temp.equals("#")){
return null;
}
else{
node = new BiNode();//为什么不加不行？使得每一个节点实例化！！不实例化就不能调用其data
node.data=temp;
System.out.println(node.data);
//System.out.println(this.root.data);
node.lchild=Grow(node.lchild,scn);
node.rchild=Grow(node.rchild,scn);
return node;
}
}
else return null;
}
public void PreOrder(BiNode bt){
if(bt==null) return;
else{
System.out.println(bt.data);
PreOrder(bt.lchild);
PreOrder(bt.rchild);
}
}
public void NDPreOrder(){
BiNode[] STA=new BiNode[100];
int top=0;
STA[0]=null;
BiNode bt=root;
while(bt!=null){
System.out.println(bt.data);
if(bt.rchild!=null) STA[++top]=bt.rchild;
if(bt.lchild!=null) bt=bt.lchild;
else bt=STA[top--];
}
}
public void InOrder(BiNode bt){
if(bt==null) return;
else{
InOrder(bt.lchild);
System.out.println(bt.data);
InOrder(bt.rchild);
}
}
public void NDInOrder(){
BiNode[] STA=new BiNode[100];
int top=-1;
BiNode bt=root;
while(bt!=null||top!=-1){
while(bt!=null){
STA[++top]=bt;
bt=bt.lchild;
}
if(top!=-1){
bt=STA[top--];
System.out.println(bt.data);
bt=bt.rchild;
}
}
}
public void PostOrder(BiNode bt){
if(bt==null) return;
else{
PostOrder(bt.lchild);
PostOrder(bt.rchild);
System.out.println(bt.data);
}
}
public void NDPostOrder(){
Element[] STA=new Element[100];
int top=-1;
BiNode bt=root;
while(bt!=null||top!=-1){
while(bt!=null){
STA[++top].ptr=bt;
STA[top].flag=1;
bt=bt.lchild;
}
while(top!=-1&&STA[top].flag==2){
bt=STA[top--].ptr;
System.out.println(bt.data);
}
if(top!=-1){
STA[top].flag=2;
bt=STA[top].ptr.rchild;
}
}
}
public void LeverOrder(){
BiNode[] Q=new BiNode[100];
int front=-1;
int rear=-1;
Q[++rear]=root;
while(rear!=front){
BiNode p=Q[++front];
System.out.println(p.data);
if(p.lchild!=null) Q[++rear]=p.lchild;
if(p.rchild!=null) Q[++rear]=p.rchild;
}
}
public BiNode DeleteX(BiNode p,String x){
if(p!=null){
if(p.data.equals(x)) {
System.out.println("match");
return null;
}
else{
p.lchild=DeleteX(p.lchild,x);
p.rchild=DeleteX(p.rchild,x);
return p;
}
}
else return null;
}
public void LeverDeleteX(BiTree A,String x){
BiNode[] Q=new BiNode[100];
int front=-1;
int rear=-1;
Q[++rear]=A.root;
while(rear!=front){
BiNode p=Q[++front];
if(p.data.equals(x)) {p=null;System.out.println("match");}
else{
if(p.lchild!=null) Q[++rear]=p.lchild;
if(p.rchild!=null) Q[++rear]=p.rchild;
}
}
}
}
public class TestBiTree{
public static void main(String[] args) {
int i=0;
System.out.println("ENTER NOW$$");
Scanner scn=null;
try{
scn= new Scanner(new File("input.txt"));
} catch (FileNotFoundException e) {
e.printStackTrace();
};
BiTree ATree=new BiTree();
ATree.root=ATree.Grow(ATree.root,scn);
System.out.println("IT IS IN NOw");
ATree.LeverOrder();
String s="B";
//ATree.root=ATree.DeleteX(ATree.root,s);
ATree.LeverDeleteX(ATree,s);
ATree.LeverOrder();
}
}

Answer 1

你的问题我在java编写二叉树中也运到过我把我解决的方法说下，你要删掉一个节点你先要保存它的父节点，在c语言中没有这么麻烦，然你在判断要删
的节点是否有左右孩子，不同情况不同做法当你要把你保存的那个父节点指向你要删的节点的孩子节点（但它为只有左孩子或右孩子或都没有时），
如果有两孩子你就要判断找到它的右子树的最小的节点并把它的值替换掉要删的节点。。。