cj云 2023-03-11 16:53 采纳率: 25%

# java的数据结构的删除del的方法

BinaryTree创建二叉树

``````
public class BinaryTree {

private Hero root;
Scanner myScanner =new Scanner(System.in);

public Hero createBinary() {

Hero hero = null;

System.out.println("你是否需要创造新节点  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();
hero = new Hero(id, name);
} else if ("n".equals(key)) {
//            hero = null;
return null;
}

hero.setLeftChild(createBinary());
hero.setRightChild(createBinary());
return hero;
}
//        Hero p = root;
//        if (p == null) {
//            root = hero;
//            return;
//        } else {
//            if (p.getLeftChild() == null) {
//                p.setLeftChild(hero);
//                p = p.getLeftChild();
//            } else if (p.getRightChild() == null) {
//                p.setRightChild(root);
//                p = p.getRightChild();
//            }
//        }
public Hero getRoot() {
return root;
}

public void setRoot(Hero root) {
this.root = root;
}
}
``````

Hero节点类

``````public class Hero {
private Hero leftChild;
private Hero rightChild;
private int id;
private String name;
private int tag = 0;//0为未遍历，1为已遍历

public int getTag() {
return tag;
}

public void setTag(int tag) {
this.tag = tag;
}

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;
}
@Override
public String toString() {
return "Hero{" +
"id=" + id +
", name='" + name + '\'' +
'}';
}

}
``````

DeleteTree删除节点的方法

``````public class DeleteTree {

private static Scanner myScanner = new Scanner(System.in);
public static void del(Hero tree, int id) {
Stack<Hero> stack = new Stack<>();

Hero p = tree;
if (p == null) {
System.out.println("该二叉树为空...");
return;
} else {
while (p != null) {
if (p.getId() == id) {
p = null;
}
else {
if (p.getRightChild() != null) {
stack.push(p.getRightChild());
}
if (p.getLeftChild() != null) {
p = p.getLeftChild();
} else if (!stack.empty()) {
p = stack.pop();
} else {
break;
}
}
}
}
}

}
``````

TraMain实现main方法在这实现测试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();//这样子一颗二叉树就搞好了
System.out.println("===============递归前序遍历===============");
traMain.preTravers(BinaryTree);//前序遍历

DeleteTree.del(BinaryTree, 2);

System.out.println("===============递归前序遍历===============");
traMain.preTravers(BinaryTree);//前序遍历
/**
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;
}
}
}
}
}
``````
• 写回答

#### 3条回答默认 最新

• VenYy 2023-03-11 17:00
关注

你的代码中有一些问题需要修正。首先，在二叉树创建方法 `createBinary()` 中，当用户输入 'n' 时，应该返回 `null` 而不是赋值为 `null`。其次，在节点删除方法 `del()` 中，你只是设定要删除的节点为空，但并没有实际上删除它，所以需要对删除操作进行改进。

以下是修改建议：

BinaryTree类中修改如下：

``````public Hero createBinary() {
} else if ("n".equals(key)) {
return null;
}
}
``````

DeleteTree类中修改如下：

``````public static void del(Hero tree, int id) {

if (tree == null) {
System.out.println("该二叉树为空...");
return;
}

Hero p = tree;
Hero parent = null;
boolean isLeftChild = true;

while (p != null && p.getId() != id) {
parent = p;
if (id < p.getId()) {
isLeftChild = true;
p = p.getLeftChild();
} else {
isLeftChild = false;
p = p.getRightChild();
}
}
if (p == null) {
System.out.println("未找到待删除节点");
return;
}

// 如果待删除节点是叶子节点
if (p.getLeftChild() == null && p.getRightChild() == null) {
if (p == tree) {
tree = null;
} else if (isLeftChild) {
parent.setLeftChild(null);
} else {
parent.setRightChild(null);
}
}
// 如果待删除节点只有左子节点
else if (p.getRightChild() == null) {
if (p == tree) {
tree = p.getLeftChild();
} else if (isLeftChild) {
parent.setLeftChild(p.getLeftChild());
} else {
parent.setRightChild(p.getLeftChild());
}
}
// 如果待删除节点只有右子节点
else if (p.getLeftChild() == null) {
if (p == tree) {
tree = p.getRightChild();
} else if (isLeftChild) {
parent.setLeftChild(p.getRightChild());
} else {
parent.setRightChild(p.getRightChild());
}
}
// 如果待删除节点有两个子节点
else {
Hero successor = getSuccessor(p);

if (p == tree) {
tree = successor;
} else if (isLeftChild) {
parent.setLeftChild(successor);
} else {
parent.setRightChild(successor);
}

successor.setLeftChild(p.getLeftChild());
}
}

/**
* 获取待删除节点的后继节点
*/
private static Hero getSuccessor(Hero delNode) {
Hero successorParent = delNode;
Hero successor = delNode;
Hero current = delNode.getRightChild();

while (current != null) {
successorParent = successor;
successor = current;
current = current.getLeftChild();
}

if (successor != delNode.getRightChild()) {
successorParent.setLeftChild(successor.getRightChild());
successor.setRightChild(delNode.getRightChild());
}

return successor;
}
``````

这里建议你创建一个新的 `Hero` 类型的引用来保存删除节点的父节点，这个应该在删除节点时比较容易处理。同时，如果要删除的节点有左右子节点时，需要寻找它的后继节点来替代它，保证删除后仍然是一棵二叉树。

本回答被题主选为最佳回答 , 对您是否有帮助呢?
评论 编辑记录

• 系统已结题 3月20日
• 已采纳回答 3月12日
• 创建了问题 3月11日

#### 悬赏问题

• ¥15 Qt 不小心删除了自带的类，该怎么办
• ¥15 我需要在PC端 开两个抖店工作台客户端.(语言-java)
• ¥15 有没有哪位厉害的人可以用C#可视化呀
• ¥15 可以帮我看看代码哪里错了吗
• ¥15 设计一个成绩管理系统
• ¥15 PCL注册的选点等函数如何取消注册
• ¥15 问一下各位，为什么我用蓝牙直接发送模拟输入的数据，接收端显示乱码呢，米思齐软件上usb串口显示正常的字符串呢？
• ¥15 Python爬虫程序
• ¥15 crypto 这种的应该怎么找flag？
• ¥15 代码已写好，求帮我指出错误，有偿！