二叉树----遍历、查找、删除
# 二叉树----遍历、查找、删除## 1、为什么需要树？
> - 数组的查找效率高，但是插入效率低。
> - 链表的插入效率高，查找效率低。
## 2、二叉树
- 二叉树的基本概念：每个节点最多只能由**两个子节点**的一种树叫做二叉树
- 满二叉树：如果该二叉树的所有**叶子节点**都在**最后一层**，并且结点总数= **2n -1** , n为层数，则我们称为满二叉树。
- 完全二叉树：如果该二叉树的所有**叶子节点**都在**最后一层**或者**倒数第二层**，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树
## 3、二叉树的遍历
1. #### 前序遍历
**先遍历父节点**，再遍历左子节点，最后遍历右子节点
2. #### 中序遍历
先遍历左子节点，**再遍历父节点**，最后遍历右子节点
3. #### 后序遍历
先遍历左子节点，再遍历右子节点，**最后遍历父节点**
**区别：看父节点什么时候遍历，在最前面就是前序，在中间就是中序，在最后就是后续**
## 4、二叉树的遍历代码实现
```java
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、二叉树的查找代码实现
```java
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 + '\'' +
'}';
}
/**
* 前序查找
* @Param id 要查找的学生id
* @Return 查找到的学生
*/
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、删除节点的思路：
1. **先考虑是否是个空树**，即root节点是否为null
2. 因为我们的二叉树是**单向的**，所以我们是判断**当前结点的子结点**是否需要删除结点，而不能去判断当前这个结点是不是需要删除结点(假如找到了当前节点，就无法找到当前节点的父节点，也就意味着无法删除当前节点了)
3. 如果当前结点的**左子结点不为空**，并且左子结点就是要删除结点，就将 **this.left = null**; 并且就返回 (结束递归删除)
4. 如果当前结点的**右子结点不为空**，并且右子结点就是要删除结点，就将 **this.right= null** ;并且就返回 (结束递归删除)
5. 如果第2和第3步没有删除结点，那么我们就需要向左子树进行递归删除
6. 如果 4步也没有删除结点，则应当向右子树进行递归删除
### 7.2、删除节点的代码实现
```java
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);
}
}
}
``` 以前学得很好，现在全忘了{:301_1004:} 学无止境 谢谢大佬分享数据结构相关教程和代码，受益良多。 学过不用，渐渐忘记
页:
[1]