二叉树----遍历、查找、删除
1、为什么需要树？
- 数组的查找效率高，但是插入效率低。
- 链表的插入效率高，查找效率低。
2、二叉树
- 二叉树的基本概念：每个节点最多只能由两个子节点的一种树叫做二叉树
- 满二叉树：如果该二叉树的所有叶子节点都在最后一层，并且结点总数= 2n -1 , n为层数，则我们称为满二叉树。
- 完全二叉树：如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树
3、二叉树的遍历
-
前序遍历
先遍历父节点，再遍历左子节点，最后遍历右子节点
-
中序遍历
先遍历左子节点，再遍历父节点，最后遍历右子节点
-
后序遍历
先遍历左子节点，再遍历右子节点，最后遍历父节点
区别：看父节点什么时候遍历，在最前面就是前序，在中间就是中序，在最后就是后续
4、二叉树的遍历代码实现
class BinaryTree {
/**
* 根节点
*/
private StuNode root;
public void setRoot(StuNode root) {
this.root = root;
}
public void preTraverse() {
if(root != null) {
System.out.println("前序遍历");
root.preTraverse();
System.out.println();
}else {
System.out.println("二叉树为空！");
}
}
public void midTraverse() {
if(root != null) {
System.out.println("中序遍历");
root.midTraverse();
System.out.println();
}else {
System.out.println("二叉树为空！");
} }
public void lastTraverse() {
if(root != null) {
System.out.println("后序遍历");
root.lastTraverse();
System.out.println();
}else {
System.out.println("二叉树为空！");
} }
}
/**
* 二叉树中的一个节点
* 保存了学生信息和左右孩子信息
*/
@Data
class StuNode {
int id;
String name;
StuNode left;
StuNode right;
public StuNode(int id, String name) {
this.id = id;
this.name = name;
}
@Override
public String toString() {
return "StuNode{" +
"id=" + id +
", name='" + name + '\'' +
'}';
}
/**
* 前序遍历
*/
public void preTraverse() {
//父节点最开始就输出
System.out.println(this);
if(left != null) {
left.preTraverse();
}
if(right != null) {
right.preTraverse();
}
}
/**
* 中序遍历
*/
public void midTraverse() {
if(left != null) {
left.midTraverse();
}
//父节点在中间输出
System.out.println(this);
if(right != null) {
right.midTraverse();
}
}
public void lastTraverse() {
if(left != null) {
left.lastTraverse();
}
if(right != null) {
right.lastTraverse();
}
//父节点在最后输出
System.out.println(this);
}
}
5、二叉树的查找
与3是类似的，在遍历的过程中加一个判断，找到对应的元素直接返回即可！
6、二叉树的查找代码实现
class BinarySearchTree {
private Student root;
public void setRoot(Student root) {
this.root = root;
}
public void preSearch(int id) {
System.out.println("前序查找");
if(root == null) {
System.out.println("树为空！");
return;
}
Student result = root.preSearch(id);
if(result == null) {
System.out.println("未找到该元素");
System.out.println();
return;
}
System.out.println(result);
System.out.println();
}
public void midSearch(int id) {
System.out.println("中序查找");
if(root == null) {
System.out.println("树为空！");
return;
}
Student result = root.midSearch(id);
if(result == null) {
System.out.println("未找到该元素");
System.out.println();
return;
}
System.out.println(result);
System.out.println();
}
public void lastSearch(int id) {
System.out.println("后序查找");
if(root == null) {
System.out.println("树为空！");
return;
}
Student result = root.lastSearch(id);
if(result == null) {
System.out.println("未找到该元素");
System.out.println();
return;
}
System.out.println(result);
System.out.println();
}
}
@Data
class Student {
int id;
String name;
Student left;
Student right;
public Student(int id, String name) {
this.id = id;
this.name = name;
}
@Override
public String toString() {
return "Student{" +
"id=" + id +
", name='" + name + '\'' +
'}';
}
/**
* 前序查找
* home.php?mod=space&uid=952169 id 要查找的学生id
* home.php?mod=space&uid=155549 查找到的学生
*/
public Student preSearch(int id) {
//如果找到了，就返回
if(this.id == id) {
return this;
}
//在左子树中查找，如果找到了就返回
Student student = null;
if(left != null) {
student = left.preSearch(id);
}
if(student != null) {
return student;
}
//在右子树中查找，无论是否找到，都需要返回
if(right != null) {
student = right.preSearch(id);
}
return student;
}
/**
* 中序查找
* @param id 要查找的学生id
* @return 查找到的学生
*/
public Student midSearch(int id) {
Student student = null;
if(left != null) {
student = left.midSearch(id);
}
if(student != null) {
return student;
}
//找到了就返回
if(this.id == id) {
return this;
}
if(right != null) {
student = right.midSearch(id);
}
return student;
}
/**
* 后序查找
* @param id 要查找的学生id
* @return 查找到的学生
*/
public Student lastSearch(int id) {
Student student = null;
if(left != null) {
student = left.lastSearch(id);
}
if(student !=null) {
return student;
}
if(right != null) {
student = right.lastSearch(id);
}
if(this.id == id) {
return this;
}
return student;
}
}
7、二叉树节点的删除
-
如果删除的节点是叶子节点，则删除该节点
-
如果删除的节点是非叶子节点，则删除该子树.
7.1、删除节点的思路：
- 先考虑是否是个空树，即root节点是否为null
- 因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除结点，而不能去判断当前这个结点是不是需要删除结点(假如找到了当前节点，就无法找到当前节点的父节点，也就意味着无法删除当前节点了)
- 如果当前结点的左子结点不为空，并且左子结点就是要删除结点，就将 this.left = null; 并且就返回 (结束递归删除)
- 如果当前结点的右子结点不为空，并且右子结点就是要删除结点，就将 this.right= null ;并且就返回 (结束递归删除)
- 如果第2和第3步没有删除结点，那么我们就需要向左子树进行递归删除
- 如果 4步也没有删除结点，则应当向右子树进行递归删除
7.2、删除节点的代码实现
class BinaryDeleteTree {
StudentNode root;
public void setRoot(StudentNode root) {
this.root = root;
}
/**
* 删除节点
* @param id 删除节点的id
*/
public void deleteNode(int id) {
System.out.println("删除节点");
if(root.id == id) {
root = null;
System.out.println("根节点被删除");
return;
}
//调用删除方法
root.deleteNode(id);
}
}
@Data
class StudentNode {
int id;
String name;
StudentNode left;
StudentNode right;
public StudentNode(int id, String name) {
this.id = id;
this.name = name;
}
@Override
public String toString() {
return "StudentNode{" +
"id=" + id +
", name='" + name + '\'' +
'}';
}
/**
* 删除节点
* @param id 删除节点的id
*/
public void deleteNode(int id) {
//如果左子树不为空且是要查找的节点，就删除
if(left != null && left.id == id) {
left = null;
System.out.println("删除成功");
return;
}
//如果右子树不为空且是要查找的节点，就删除
if(right != null && right.id == id) {
right = null;
System.out.println("删除成功");
return;
}
//左递归，继续查找
if(left != null) {
left.deleteNode(id);
}
//右递归，继续查找
if(right != null) {
right.deleteNode(id);
}
}
}
| 
发表于 2021-3-25 20:21
