Java 树结构的基础部分(一）
2021-06-09 00:05
标签：返回 mic 路径 并且 示意图 子节点 rri Fix 错误 代码实现 在最后面 仅供参考，有错误还请指出！ 有什么想法，评论区留言，互相指教指教。 觉得不错的可以点一下右边的推荐哟 Java 树结构的基础部分(一） 标签：返回 mic 路径 并且 示意图 子节点 rri Fix 错误 原文地址：https://www.cnblogs.com/linzm14/p/14501484.html
package com.lin.tree_0308;
public class BinaryTreeDemo {
public static void main(String[] args) {
BinaryTree binaryTree = new BinaryTree();
HeroNode heroNode1 = new HeroNode(1, "伍六七");
HeroNode heroNode2 = new HeroNode(2, "梅花十一");
HeroNode heroNode3 = new HeroNode(3, "梅花十三");
HeroNode heroNode4 = new HeroNode(4, "江主任");
HeroNode heroNode5 = new HeroNode(5, "希义");
heroNode1.setLeft(heroNode2);
heroNode1.setRight(heroNode3);
heroNode3.setRight(heroNode4);
heroNode3.setLeft(heroNode5);
binaryTree.setRoot(heroNode1);
// System.out.println("前序遍历：");
// binaryTree.preOrder();
// System.out.println("中序遍历：");
// binaryTree.infixOrder();
//
// System.out.println("后序遍历");
// binaryTree.postOrder();
// System.out.println("前序查找：");
// HeroNode preOrderSearch = binaryTree.preOrderSearch(5);
// if(preOrderSearch != null) {
// System.out.println(preOrderSearch);
// } else {
// System.out.println("没有找到");
// }
// System.out.println("中序查找：");
// HeroNode infixOrderSearch = binaryTree.infixOrderSearch(5);
// if(infixOrderSearch != null) {
// System.out.println(infixOrderSearch);
// } else {
// System.out.println("没有找到");
// }
//
// System.out.println("后序查找：");
// HeroNode postOrderSearch = binaryTree.postOrderSearch(5);
// if(postOrderSearch != null) {
// System.out.println(postOrderSearch);
// } else {
// System.out.println("没有找到");
// }
System.out.println("删除前");
binaryTree.preOrder();
binaryTree.delNode(2);
System.out.println("删除后");
binaryTree.preOrder();
}
}
class BinaryTree{
private HeroNode root;
public void setRoot(HeroNode root) {
this.root = root;
}
// 删除节点
public void delNode(int no) {
if (root != null) {
// 如果只有一个root
if (root.getNo() == no) {
root = null;
} else {
root.delNode(no);
}
} else {
System.out.println("空树！");
}
}
// 前序遍历
public void preOrder() {
if(this.root != null) {
this.root.preOrder();
} else {
System.out.println("二叉树为空!");
}
}
// 中序遍历
public void infixOrder() {
if(this.root != null) {
this.root.infixOrder();
} else {
System.out.println("二叉树为空！");
}
}
// 后序遍历
public void postOrder() {
if(this.root != null) {
this.root.postOrder();
} else {
System.out.println("二叉树为空！");
}
}
// 前序查找
public HeroNode preOrderSearch(int no) {
if(root != null) {
return root.preOrderSearch(no);
} else {
return null;
}
}
// 中序查找
public HeroNode infixOrderSearch(int no) {
if (root != null) {
return root.infixOrderSearch(no);
} else {
return null;
}
}
// 后序查找
public HeroNode postOrderSearch(int no) {
if (root != null) {
return root.postOrderSearch(no);
} else {
return null;
}
}
}
class HeroNode{
private String name;
private int no;
private HeroNode left;
private HeroNode right;
public HeroNode(int no, String name) {
this.no = no;
this.name = name;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public HeroNode getLeft() {
return left;
}
public void setLeft(HeroNode left) {
this.left = left;
}
public HeroNode getRight() {
return right;
}
public void setRight(HeroNode right) {
this.right = right;
}
@Override
public String toString() {
return "HeroNode [name=" + name + ", no=" + no + "]";
}
// 前序遍历
public void preOrder() {
System.out.println(this); // 输出父节点
if(this.left != null) {
this.left.preOrder();
}
if(this.right != null) {
this.right.preOrder();
}
}
// 中序遍历
public void infixOrder() {
if (this.left != null) {
this.left.infixOrder();
}
System.out.println(this); // 输出父节点
if (this.right != null) {
this.right.infixOrder();
}
}
// 前序遍历
public void postOrder() {
if (this.left != null) {
this.left.postOrder();
}
if (this.right != null) {
this.right.postOrder();
}
System.out.println(this); // 输出父节点
}
// 前序查找
public HeroNode preOrderSearch(int no) {
System.out.println("1");
// 比较当前节点是不是
if(this.no == no) {
return this;
}
// 1 判断当前节点的左节点是否为空，如果不为空，则递归前序查找
// 2 如果左递归前序查找，找到节点，则返回
HeroNode resNode = null;
if(this.left != null) {
resNode = this.left.preOrderSearch(no);
}
if(resNode != null) {// 说明左子树找到了
return resNode;
}
// 1 左递归如果没有找到，则继续判断
// 2 当前节点的右节点是否为空，如果不为空，则继续向右递归前序查找
if(this.right != null) {
resNode = this.right.preOrderSearch(no);
}
// 这时候不管有没有找到都要返回resNode
return resNode;
}
// 中序查找
public HeroNode infixOrderSearch(int no) {
HeroNode resNode = null;
if(this.left != null) {
resNode = this.left.infixOrderSearch(no);
}
if(resNode != null) {
return resNode;
}
System.out.println("1");
if(this.no == no) {
return this;
}
if(this.right != null) {
resNode = this.right.infixOrderSearch(no);
}
return resNode;
}
// 后序查找
public HeroNode postOrderSearch(int no) {
HeroNode resNode = null;
if(this.left != null) {
resNode = this.left.postOrderSearch(no);
}
if(resNode != null) {
return resNode;
}
if(this.right != null) {
resNode = this.right.postOrderSearch(no);
}
if(resNode != null) {
return resNode;
}
System.out.println("1");
if(this.no == no) {
return this;
}
// 如果都没有找到
return resNode;
}
/**
*
* @Description:1 因为我们的二叉树是单向，所以我们是判断当前节点的子节点是否需要删除节点，而不是直接去判断当前节点是否需要删除节点。
* 2 如果当前节点的左子节点不为空，并且左子节点就是要删除节点，就将this.left = null；并且就返回（结束递归删除）
* 3 如果当前节点的右子节点不为空，并且右子节点就是要删除节点，就将this.right = null；并且就返回（结束递归删除）
* 4 如果第2和第3都没有删除节点，那么我们就需要向左子树进行递归删除
* 5 如果第4补也没有删除节点，则向右子树进行递归删除
* @author LinZM
* @date 2021-3-8 15:17:32
* @version V1.8
*/
public void delNode(int no) {
if(this.left != null && this.left.no == no) {
this.left = null;
return;
}
if(this.right != null && this.right.no == no) {
this.right = null;
return;
}
if(this.left != null) {
this.left.delNode(no);
}
if(this.right != null) {
this.right.delNode(no);
}
}
}
上一篇：java 实现发送邮件功能