BinaryTree类创建二叉树,和del方法,实现删除根节点,但不知道为什么根节点一直无法删除,本人已经困在这很久了,想让CSDN的java技术大拿帮我看看怎么删除根节点啊,求大拿来看看,我已经停在这几天了
public class BinaryTree {
private Hero root;
Scanner myScanner =new Scanner(System.in);
public BinaryTree() {
root = createBinary();
}
public Hero createBinary() {
// while (true) {
// System.out.print("你是否需要创造新节点 y/n: ");
// String key = myScanner.next();
// if ("y".equals(key)) {
// System.out.print("请输入 id = ");
// int id = myScanner.nextInt();
// System.out.print("请输入 name = ");
// String name = myScanner.next();
//
// if (root == null) {
// root = new Hero(id, name);
// } else {
// root.addNode(new Hero(id, name));
// }
// } else {
// break;
// }
// }
Hero hero = null;
System.out.print("你是否需要创造新节点 y/n: ");
String key = myScanner.next();
if ("y".equals(key)) {
System.out.print("请输入 id = ");
int id = myScanner.nextInt();
System.out.print("请输入 name = ");
String name = myScanner.next();
// if (root == null) {
// root = new Hero(id, name);
// } else{
hero = new Hero(id, name);
// }
} else if ("n".equals(key)) {
return null;
}
hero.setLeftChild(createBinary());
hero.setRightChild(createBinary());
return hero;
}
public void del(Hero tree, int id) {
if (root.getId() == id && root != null) {
// root = getRoot();
// root = null;
} else {
new DeleteTree().del(tree, id);
}
}
public Hero getRoot() {
return root;
}
public void setRoot(Hero root) {
this.root = root;
}
}
DeleteTree实现删除节点的方法,但这个方法只能删除根节点以外的节点,删除不了根节点
public class DeleteTree {
public void del(Hero tree, int id) {
Stack<Hero> stack = new Stack<>();
Stack<Hero> parentStack = new Stack<>();
Hero parent = null;
Hero p = tree;
if (p == null) {
System.out.println("该二叉树为空...");
return;
} else {
while (p != null && p.getId() != id) {
parent = p;
if (p.getLeftChild() == null && p.getRightChild() == null && !parentStack.empty()) {
parent = parentStack.pop();
}
if (p.getLeftChild() != null && p.getLeftChild().getId() == id) {
p = p.getLeftChild();
} else {
if (p.getLeftChild() != null) {
parentStack.push(parent);
if (p.getRightChild() != null) {
stack.push(p.getRightChild());
}
p = p.getLeftChild();
} else if (p.getRightChild() != null){
p = p.getRightChild();
} else if (!stack.empty()) {
p = stack.pop();
} else {
break;
}
}
}
if (p.getId() == id && parent.getLeftChild() == p) {
parent.setLeftChild(null);
} else if (p.getId() == id && parent.getRightChild() == p) {
parent.setRightChild(null);
} else {
System.out.println(id + " 节点不存在...");
}
}
}
}
Hero是节点类
public class Hero {
private Hero leftChild;
private Hero rightChild;
private int id;
private String name;
private int tag = 0;//0为未遍历,1为已遍历
Scanner myScanner = new Scanner(System.in);
public int getTag() {
return tag;
}
public void setTag(int tag) {
this.tag = tag;
}
public Hero() {
}
public Hero(int id, String name) {
this.id = id;
this.name = name;
}
public Hero getLeftChild() {
return leftChild;
}
public void setLeftChild(Hero leftChild) {
this.leftChild = leftChild;
}
public Hero getRightChild() {
return rightChild;
}
public void setRightChild(Hero rightChild) {
this.rightChild = rightChild;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
// public void addNode(Hero hero) {
//
// if (hero == null) {
// return;
// }
// if (hero.getId() > this.getId()) {
// if (this.rightChild == null) {
// this.rightChild = hero;
// } else {
// this.rightChild.addNode(hero);
// }
// }
// if (hero.getId() < this.getId()) {
// if (this.leftChild == null) {
// this.leftChild = hero;
// } else {
// this.leftChild.addNode(hero);
// }
// }
// }
@Override
public String toString() {
return "Hero{" +
"id=" + id +
", name='" + name + '\'' +
'}';
}
}
TraMain类里有main方法调用BinaryTree里的del方法
public class TraMain {
static Scanner myScanner = new Scanner(System.in);
public static void main(String[] args) {
TraMain traMain = new TraMain();
BinaryTree binaryTree = new BinaryTree();
// Hero BinaryTree = binaryTree.createBinary();//这样子一颗二叉树就搞好了
// binaryTree.createBinary();
Hero Head ;
Head = binaryTree.getRoot();
System.out.println("===============递归前序遍历===============");
traMain.preTravers(Head);//前序遍历
binaryTree.del(Head, 1);
// DeleteTree.del(BinaryTree, 2);
System.out.println("===============递归前序遍历===============");
traMain.preTravers(Head);//前序遍历
/**
System.out.println("===============递归中序遍历===============");
traMain.inorderTra(BinaryTree);
System.out.println("===============递归后序遍历===============");
traMain.postTra(BinaryTree);
System.out.println("===============非递归前序遍历===============");
traMain.nonRePreTra(BinaryTree);
System.out.println("===== 中序非递归遍历(order) / 后序非递归遍历(post) =====");
System.out.print("请输入 order 或 post: ");
String key = myScanner.next();
if ("order".equals(key)) {
System.out.println("===============非递归中序遍历===============");
traMain.nonReorderTra(BinaryTree);
} else {
System.out.println("===============非递归后序遍历===============");
traMain.nonRepostTra(BinaryTree);
}
**/
}
//前序遍历二叉树的方法
public void preTravers(Hero tree) {
Hero p = tree;
if (p == null) {
return;
}
System.out.println(p);
preTravers(p.getLeftChild());
preTravers(p.getRightChild());
}
public void inorderTra(Hero tree) {
Hero p = tree;
if (p == null) {
return;
}
inorderTra(p.getLeftChild());
System.out.println(p);
inorderTra(p.getRightChild());
}
public void postTra(Hero tree) {
Hero p = tree;
if (p == null) {
return;
}
postTra(p.getLeftChild());
postTra(p.getRightChild());
System.out.println(p);
}
public void nonRePreTra(Hero tree) {
Stack<Hero> stack = new Stack<Hero>();
Hero p = tree;
if (p == null) {
return;
}
while (p != null) {
if (p.getRightChild() != null) {
stack.push(p.getRightChild());
}
System.out.println(p);
if (p.getLeftChild() != null) {
p = p.getLeftChild();
} else if (stack.size() > 0) {
p = stack.pop();
} else {
p = null;
}
}
}
public void nonReorderTra(Hero tree) {
Stack<Hero> stack = new Stack<Hero>();
Hero p = tree;
if (p == null) {
return;
}
while (p != null) {
while (p.getLeftChild() != null && p.getLeftChild().getTag() == 0) {
stack.push(p);
p = p.getLeftChild();
}
System.out.println(p);
p.setTag(1);
if (p.getRightChild() != null) {
p = p.getRightChild();
} else if (stack.size() != 0){
p = stack.pop();
} else {
p = null;
}
}
}
public void nonRepostTra(Hero tree) {
Stack<Hero> stack = new Stack<Hero>();
Hero p = tree;
if (p == null) {
return;
}
while (p != null) {
while (p.getLeftChild() != null && p.getLeftChild().getTag() == 0) {
stack.push(p);
p = p.getLeftChild();
}
if (p.getRightChild() != null && p.getRightChild().getTag() == 0) {
stack.push(p);
p = p.getRightChild();
} else {
System.out.println(p);
p.setTag(1);
if (stack.size() != 0) {
p = stack.pop();
} else if (stack.size() == 0) {
p = null;
}
}
}
}
}