要求：用java编写完整代码，不用C++
创建一个二叉树，结点存放的是整型数据，遵循的规则是：第一个数值作为二叉树的树根，小于父节点的值放在左子节点，大于父节点的值放在右子节点。 在创建好二叉树的基础之上，进行结点统计和删除。 统计的内容包括：结点的个数；树的深度；度为0的点的个数；度为1的点的个数；度为2的点的个数。 删除的策略：如果删除结点是叶子结点，直接删除该点；如果删除结点只有一棵子树，子树的根结点直接替代该结点；如果删除结点同时有左子树和右子树，将右子树中的最小值点移动到删除点的位置上来替代删除结点。
输入格式:
输入数值为整型，多行输入。 第一行：二叉树的结点个数N（1≤N≤30）。 第二行：结点的值，以逗号间隔。 第三行：要删除的结点值。
输出格式:
多行输出。第1行输出结点个数。 第2行输出树的深度。 第3行度为0的结点个数。 第4行输出度为1的结点的个数。 第5行输出度为2的结点的个数。第6行为删除前的中序遍历结果。第7行为删除前的广度优先遍历结果 。第8行为删除后的中序遍历结果。第9行为删除后的广度优先遍历结果。具体的格式于要求参见输入输出样例。
输入样例:
在这里给出一组输入。例如：
5
7,2,5,9,12
7输出样例:
在这里给出相应的输出。例如：
NodeNumbers:5
TreeDepth:3
numbers_0:2
numbers_1:2
numbers_2:1
InOrder:2,5,7,9,12
LayerOrder:7,2,9,5,12
InOrder after:2,5,9,12
LayerOrder after:9,2,12,5输入样例2:
在这里给出一组输入。例如：
1
3
3输出样例2:
在这里给出相应的输出。例如：
NodeNumbers:1
TreeDepth:1
numbers_0:1
numbers_1:0
numbers_2:0
InOrder:3
LayerOrder:3
InOrder after:null
LayerOrder after:nullhttps://blog.csdn.net/weixin_44382383/article/details/101015661
public class BinaryTreeNodes {
private int id; // 节点id
private String name; // 节点名字
private BinaryTreeNodes left; // 节点的左指针
private BinaryTreeNodes right; // 节点的右指针
public BinaryTreeNodes() {
}
public BinaryTreeNodes(int id, String name) {
this.id = id;
this.name = name;
}
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 BinaryTreeNodes getLeft() {
return left;
}
public void setLeft(BinaryTreeNodes left) {
this.left = left;
}
public BinaryTreeNodes getRight() {
return right;
}
public void setRight(BinaryTreeNodes right) {
this.right = right;
}
@Override
public String toString() {
return "BinaryTreeNodes{" +
"id=" + id +
", name='" + name + '\'' +
'}';
}
// 前序遍历
public void PreOrder() {
// 先遍历当前节点
System.out.println(this);
// 递归遍历左子树
if (this.left != null) {
this.left.PreOrder();
}
// 递归遍历右子树
if (this.right != null) {
this.right.PreOrder();
}
}
// 中序遍历
public void MidOrder() {
// 先遍历当前节点的左子树
if (this.left != null) {
this.left.MidOrder();
}
// 遍历当前节点
System.out.println(this);
// 遍历右子树
if (this.right != null) {
this.right.MidOrder();
}
}
// 后序遍历
public void PostOrder() {
// 先遍历当前节点的左子树
if (this.left != null) {
this.left.PostOrder();
}
// 再遍历当前节点的右子树
if (this.right != null) {
this.right.PostOrder();
}
// 遍历当前节点
System.out.println(this);
}
// 删除指定节点
public void DelNodes(int id){
// 左子树删除
if(this.left != null && this.left.id == id){
this.left = null;
}
// 右子树删除
if(this.right != null && this.right.id == id){
this.right = null;
}
// 左子树递归删除
if(this.left != null){
this.left.DelNodes(id);
}
// 右子树递归删除
if(this.right != null){
this.right.DelNodes(id);
}
}
/**
* 先序遍历查找
* 根据节点id查找某个节点
*
* @param id 传入的节点id
* @return 如果找到，返回这个节点，否则返回null
*/
public BinaryTreeNodes PreOrderSearch(int id) {
// 如果找到，则返回当前节点
if (this.id == id) {
return this;
}
BinaryTreeNodes resNodes = null; // 标记位
// 左子树递归
if (this.left != null) {
resNodes = this.left.PreOrderSearch(id);
}
if (resNodes != null) {
return resNodes;
} // 左子树找到
// 右子树递归
if (this.right != null) {
resNodes = this.right.PreOrderSearch(id);
}
return resNodes;
}
/**
* 中序遍历查找
* 根据节点id查找某个节点
*
* @param id 传入的节点id
* @return 如果找到，返回这个节点，否则返回null
*/
public BinaryTreeNodes MidOrderSearch(int id) {
BinaryTreeNodes resNodes = null;
// 先遍历查找当前节点的左子树
if (this.left != null) {
resNodes = this.left.MidOrderSearch(id);
}
if (resNodes != null) {
return resNodes;
} // 左子树的中序遍历完成
// 和当前节点比较
if (this.id == id) {
return this;
}
// 最后中序遍历右子树
if (this.right != null) {
resNodes = this.right.MidOrderSearch(id);
}
return resNodes;
}
/**
* 后序遍历查找
* 根据节点id查找某个节点
*
* @param id 传入的节点id
* @return 如果找到，返回这个节点，否则返回null
*/
public BinaryTreeNodes PostOrderSearch(int id) {
BinaryTreeNodes resNodes = null;
// 先后序遍历左子树
if (this.left != null) {
resNodes = this.left.PostOrderSearch(id);
}
if (resNodes != null) {
return resNodes;
} // 左子树后序遍历完成
if (this.right != null) {
resNodes = this.right.PostOrderSearch(id);
}
if (resNodes != null) {
return resNodes;
} // 右子树后序遍历完成
// 和当前节点比较
if (this.id == id) {
return this;
}
return resNodes;
}
}
public class BinaryTree {
public BinaryTreeNodes root; // 二叉树的根节点
public BinaryTree() {
}
public BinaryTree(BinaryTreeNodes root) {
this.root = root;
}
public void setRoot(BinaryTreeNodes root) {
this.root = root;
}
// 先序遍历
public void PreOrderTraverse() {
if (this.root != null) {
this.root.PreOrder();
} else {
System.out.println("二叉树为空,无法先序遍历");
}
}
// 中序遍历
public void MidOrderTraverse() {
if (this.root != null) {
this.root.MidOrder();
} else {
System.out.println("二叉树为空，无法中序遍历");
}
}
// 后序遍历
public void PostOrderTraverse() {
if (this.root != null) {
this.root.PostOrder();
} else {
System.out.println("二叉树为空，无法后序遍历");
}
}
// 删除指定节点
public void DelNode(int id) {
if (root != null) {
if (root.getId() == id) {
root = null;
}else {
root.DelNodes(id);
}
} else {
System.out.println("树为空，无法删除");
}
}
// 先序遍历查找
public BinaryTreeNodes PreOrderSearch(int id) {
if (root != null) {
return root.PreOrderSearch(id);
} else {
return null;
}
}
// 中序遍历查找
public BinaryTreeNodes MidOrderSearch(int id) {
if (root != null) {
return root.MidOrderSearch(id);
} else {
return null;
}
}
// 后序遍历查找
public BinaryTreeNodes PostOrderSearch(int id) {
if (root != null) {
return root.PostOrderSearch(id);
} else {
return null;
}
}
}
package binaryTreeTraverse;
/**
* @program: 8.二叉树的相关操作
* @description: 入口函数
* @author: Zhou Jian
* @create: 2020-07-18 15:00
*/
public class input {
public static void main(String[] args) {
// 创建一个二叉树
BinaryTree Tree = new BinaryTree();
// 手动创建二叉树的节点
BinaryTreeNodes root = new BinaryTreeNodes(1, "宋江");
BinaryTreeNodes N1 = new BinaryTreeNodes(2, "林冲");
BinaryTreeNodes N2 = new BinaryTreeNodes(3, "鲁智深");
BinaryTreeNodes N3 = new BinaryTreeNodes(4, "武松");
BinaryTreeNodes N4 = new BinaryTreeNodes(5, "李逵");
// 将创建的节点添加到二叉树中
Tree.setRoot(root);
// 构造二叉树
root.setLeft(N1);
root.setRight(N2);
N1.setLeft(N3);
N1.setRight(N4);
//先序遍历
System.out.println("先序遍历的结果:");
Tree.PreOrderTraverse();
// // 中序遍历
// System.out.println("中序遍历的结果:");
// Tree.MidOrderTraverse();
// // 后序遍历
// System.out.println("后序遍历的结果:");
// Tree.PostOrderTraverse();
// 先序遍历查找
// System.out.println("先序遍历查找:");
// BinaryTreeNodes resNodes = Tree.PreOrderSearch(4);
// if (resNodes != null) {
// System.out.printf("您找到的节点信息为:id=%d,name=%s", resNodes.getId(), resNodes.getName());
// } else {
// System.out.printf("没有找到id=%d的节点", 4);
// }
// 删除指定节点
Tree.DelNode(3);
System.out.println("删除后:");
Tree.PreOrderTraverse();
}
}