我们最初学习数据结构的时候，肯定是先从线性结构和链式结构讲起，回顾一下他们的特点。
线性结构以数组为例，它通过下标的方式访问元素，访问速度很快，但是当我们向数组中插入或删除某个元素时，会将插入位置的元素整体移动，从而造成效率低下。
链式结构以单链表为例，它在插入或删除元素时，只改变链表的指向并且不移动元素，能够解决线性结构插入或删除元素效率不足的问题，但是当我们需要访问某个元素时，只能从单链表头依次循环直到找到待访问元素为止，因此访问元素效率低下。
那么有没有哪种数据结构，既可以提高访问元素的速度，又可以提高插入或删除元素的效率呢?
它来了，能够提高数据存储和读取效率的树来了。以二叉排序树为例，它既可以保证数据的检索速度，又能够保证数据的插入、删除、修改的速度。
那么什么是二叉树呢? 每个节点最多只能有两个子节点的一种树称为二叉树。
二叉树又有满二叉树和完全二叉树：
有了二叉树的概念，就要用代码来实现它。
二叉树结构的创建：二叉树拥有左右结点和父结点，根据这个特点来创建下图所示的二叉树结构。
创建具有左右结点的单个结点：
-
class HeroNode{
-
private
int no;
-
private String name;
-
private HeroNode left;
// 左结点
-
private HeroNode right;
// 右结点
-
-
-
// 单个二叉树结点的操作
-
// ...
-
}
创建带有头结点的二叉树：
-
class BinaryTree{
-
private HeroNode root;
// 头结点
-
-
// 将单个结点的二叉树结点连接起来的操作
-
// ...
-
}
二叉树的遍历：前序遍历、中序遍历、后续遍历。三种遍历的区别在于，父结点所在的位置，父结点在前为前序遍历、在中为中序遍历、在后为后续遍历。前序遍历：父--->左--->右；中序遍历：左--->父--->右；后续遍历：右--->左--->父;
三种遍历的前提条件是初始化父结点root。
前序遍历思路:
- 先输出当前结点(初始为root结点);
- 如果当前结点的左子结点不为空，则递归前序遍历；
- 如果当前结点的右子结点不为空，则递归前序遍历；
中序遍历思路:
- 如果当前结点的左子结点不为空，则递归中序遍历；
- 输出当前结点(初始为root结点);
- 如果当前结点的右子结点不为空，则递归中序遍历；
后序遍历思路:
- 如果当前结点的左子结点不为空，则递归后序遍历；
- 如果当前结点的右子结点不为空，则递归后序遍历；
- 输出当前结点(初始为root结点)；
-
class BinaryTree{
-
private HeroNode root;
// 根结点
-
-
public BinaryTree(HeroNode root){
// 指定根结点
-
this.root = root;
-
}
-
-
// 前序遍历
-
public void preOrder(){
-
if (
this.root !=
null){
-
this.root.preOrder();
// 调用HeroNode中的前序遍历方法
-
}
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(
"二叉树为空，无法遍历");
-
}
-
}
-
}
-
class HeroNode{
-
private
int no;
-
private String name;
-
private HeroNode left;
// 左结点
-
private HeroNode right;
// 右结点
-
-
public HeroNode(int no, String name) {
-
this.no = no;
-
this.name = name;
-
}
-
-
// 省略getter、setter方法以及toString方法
-
-
// 前序遍历
-
public void preOrder(){
-
// 1.输出当前父结点
-
System.out.println(
this);
-
// 2.如果当前结点的左子结点不为空，前序遍历
-
if (
this.left !=
null){
-
this.left.preOrder();
-
}
-
// 3.如果当前结点的右子结点不为空，前序遍历
-
if (
this.right !=
null){
-
this.right.preOrder();
-
}
-
}
-
-
// 中序遍历
-
public void infixOrder(){
-
// 1.如果当前结点的左子结点不为空，中序遍历
-
if (
this.left !=
null){
-
this.left.infixOrder();
-
}
-
// 2.输出当前父结点
-
System.out.println(
this);
-
// 3.如果当前结点的右子结点不为空，中序遍历
-
if (
this.right !=
null){
-
this.right.infixOrder();
-
}
-
}
-
-
// 后序遍历
-
public void postOrder(){
-
// 1.如果当前结点的左子结点不为空，中序遍历
-
if (
this.left !=
null){
-
this.left.infixOrder();
-
}
-
// 2.如果当前结点的右子结点不为空，中序遍历
-
if (
this.right !=
null){
-
this.right.infixOrder();
-
}
-
// 3.输出当前父结点
-
System.out.println(
this);
-
}
-
}
-
public
class BinaryTreeDemo {
-
public static void main(String[] args) {
-
HeroNode heroNode1 =
new HeroNode(
1,
"宋江");
-
HeroNode heroNode2 =
new HeroNode(
2,
"吴用");
-
HeroNode heroNode3 =
new HeroNode(
3,
"武松");
-
HeroNode heroNode4 =
new HeroNode(
4,
"林冲");
-
BinaryTree binaryTree =
new BinaryTree(heroNode1);
// 指定根结点
-
heroNode1.setLeft(heroNode2);
// 根节点的左子结点
-
heroNode1.setRight(heroNode3);
// 根节点的右子结点
-
heroNode3.setRight(heroNode4);
// 根节点的右子结点的右子结点
-
// 遍历
-
System.out.println(
"前序遍历：");
-
binaryTree.preOrder();
//前序遍历
-
System.out.println(
"中序遍历：");
-
binaryTree.infixOrder();
//中序遍历
-
System.out.println(
"后序遍历：");
-
binaryTree.postOrder();
//后序遍历
-
}
-
}
二叉树的查找:查找的思路和遍历的思路类似，只是多了一步判断查找条件是否相等。查找也分为三种，前序查找、中序查找和后序查找，三种查找的区别还是根据处理父结点的顺序。
前序查找：
- 先判断当前结点的no值是否等于要查找的no值，如果相等，就返回当前结点；
- 如果不等，先判断当前结点的左结点是否为空，不为空就向左递归前序查找，如果找到，返回当前结点，
- 如果没找到，先判断当前结点的右子结点是否为空，不为空就向右子结点递归前序查找，如果找到，就返回当前结点，
- 没找到就返回null。
- 注：一定要有先判断左右结点是否为空这个条件，否则会出现空指针异常。
中序查找：
- 先判断当前结点的左子结点是否为空，不为空则向左结点递归中序查找，如果相等，就返回当前结点，
- 如果不等，就和当前结点比较，
- 如果当前结点和要查找的no值相等，就返回，不等就先判断右子节点是否为空，不为空则向右结点递归中序查找，
- 向右结点递归中序查找，找到就返回当前结点的右子结点，找不到返回null。
后序查找思路:
- 先判断当前结点的左子结点是否为空，不为空则向左结点递归后序查找，如果相等，就返回当前结点的左子结点，
- 如果不等，就判断当前结点的右子节点是否为空，如果不为空就向右子节点递归后序查找，
- 如果找到就返回，没找到就和当前结点比较，如果找到就返回，没找到就返回null。
-
class HeroNode{
-
private
int no;
-
private String name;
-
private HeroNode left;
// 左结点
-
private HeroNode right;
// 右结点
-
-
// 省略getter、setter和构造方法等
-
-
// 查找：
-
// 前序查找
-
public HeroNode preOrderSearch(int id){
-
// 1.判断id和当前结点是否相等
-
if (
this.no == id){
-
return
this;
-
}
-
// 2.当前结点没有找到，向左子结点递归前序查找
-
HeroNode temp =
null;
// 用来接收递归是否找到相等元素
-
if (
this.left !=
null){
-
temp =
this.left.preOrderSearch(id);
-
}
-
// 向左子结点递归找到了
-
if (temp !=
null){
-
return temp;
-
}
-
// 3.当前左子结点没有找到，向右子结点递归前序查找
-
if (
this.right !=
null){
-
temp =
this.right.preOrderSearch(id);
-
}
-
// 返回右子结点是否找到，不用判断temp是否为null，可以在函数调用的地方来判断
-
return temp;
-
}
-
// 中序查找
-
public HeroNode infixOrderSearch(int id){
-
// 1.当前结点的左子结点是否相等,判断是否找到
-
HeroNode temp =
null;
// 用来判断递归结果是否找到
-
if (
this.left !=
null){
-
temp =
this.left.infixOrderSearch(id);
-
}
-
if (temp !=
null){
-
return temp;
-
}
-
// 2.当前结点是否相等
-
if (
this.no == id){
-
return
this;
-
}
-
// 3.当前结点的右子节点是否相等,判断是否找到
-
if (
this.right !=
null){
-
temp =
this.right.infixOrderSearch(id);
-
}
-
return temp;
-
}
-
-
// 后序查找
-
public HeroNode postOrderSearch(int id){
-
// 1.当前结点的左子结点是否相等,判断是否找到
-
HeroNode temp =
null;
// 用来判断递归结果是否找到
-
if (
this.left !=
null){
-
temp =
this.left.infixOrderSearch(id);
-
}
-
if (temp !=
null){
-
return temp;
-
}
-
// 2.当前结点的右子节点是否相等,判断是否找到
-
if (
this.right !=
null){
-
temp =
this.right.infixOrderSearch(id);
-
}
-
if (temp !=
null){
-
return temp;
-
}
-
// 3.当前结点是否相等
-
if (
this.no == id){
-
return
this;
-
}
-
return temp;
-
}
-
}
-
class BinaryTree{
-
private HeroNode root;
// 根结点
-
-
public BinaryTree(HeroNode root){
// 指定根结点
-
this.root = root;
-
}
-
-
// 前序查找
-
public HeroNode preOrderSearch(int id){
-
if (
this.root !=
null){
-
return
this.root.preOrderSearch(id);
-
}
-
return
null;
-
}
-
// 中序查找
-
public HeroNode infixOrderSearch(int id){
-
if (
this.root !=
null){
-
return
this.root.infixOrderSearch(id);
-
}
-
return
null;
-
}
-
// 后序查找
-
public HeroNode postOrderSearch(int id){
-
if (
this.root !=
null){
-
return
this.root.postOrderSearch(id);
-
}
-
return
null;
-
}
-
}
-
public
class BinaryTreeDemo {
-
public static void main(String[] args) {
-
HeroNode heroNode1 =
new HeroNode(
1,
"宋江");
// 根结点
-
HeroNode heroNode2 =
new HeroNode(
2,
"吴用");
// 根节点的左子结点
-
HeroNode heroNode3 =
new HeroNode(
3,
"武松");
// 根节点的右子结点
-
HeroNode heroNode4 =
new HeroNode(
4,
"林冲");
// 根节点的右子结点的右子结点
-
BinaryTree binaryTree =
new BinaryTree(heroNode1);
-
heroNode1.setLeft(heroNode2);
-
heroNode1.setRight(heroNode3);
-
heroNode3.setRight(heroNode4);
-
-
// 查找
-
System.out.println(
"前序查找:");
-
if (binaryTree.preOrderSearch(
2) !=
null){
-
System.out.println(
"找到了,"+binaryTree.preOrderSearch(
2));
// 前序查找
-
}
else {
-
System.out.println(
"没有找到");
-
}
-
-
System.out.println(
"中序查找:");
-
if (binaryTree.preOrderSearch(
2) !=
null){
-
System.out.println(
"找到了,"+binaryTree.infixOrderSearch(
2));
// 中序查找
-
}
else {
-
System.out.println(
"没有找到");
-
}
-
-
System.out.println(
"后序查找:");
-
if (binaryTree.preOrderSearch(
2) !=
null){
-
System.out.println(
"找到了,"+binaryTree.postOrderSearch(
2));
// 后序查找
-
}
else {
-
System.out.println(
"没有找到");
-
}
-
-
}
-
}
如果想要比较这三种查找的优越性，可以在if(this.no = id)上面添加一个变量来判断它们各自递归了几次，这里就不演示了。注意的是一定是在if(this.no = id)上，因为不论怎么递归最终目的都是判断当前结点是否相等。
二叉树的删除:
这里的删除指的是递归删除结点，我们暂且规定，（1）如果删除的结点是叶子结点，那么删除该节点；（2）如果删除的结点不是叶子结点，那么删除该子树。(当然我们可以把子节点转为根节点，这里先不讨论那种情况)
满足上面两个条件的删除结点的思路:
- 首先考虑，如果树是空树或者只有一个根节点root，直接将root置空即可，否则递归删除。
- 因为二叉树是单向的，所以我们判断当前结点的子结点是否为需要删除的结点，而不能去判断当前结点是不是需要删除的结点。（这是因为，二叉树单向，所以子结点找不到父结点,比如我们要删除5号，我们找不到5号的父结点，没法置为null）
- 如果当前结点的左子结点不为空，并且左子结点就是要删除的结点，就将this.left = null，然后返回，递归结束，
- 如果当前结点的右子结点不为空，并且右子结点就是要删除的结点，就将this.right = null，然后返回，递归结束，
- 如果3和4没有删除掉，就需要向左子树递归删除，
- 如果5还没有删掉，就需要向右子树递归删除。
-
class HeroNode{
-
private int no;
-
private String name;
-
private HeroNode left;
// 左结点
-
private HeroNode right;
// 右结点
-
-
// 省略getter、setter和构造方法等
-
-
-
/* 删除结点要求：（1）如果删除的结点是叶子结点，那么删除该节点；
-
（2）如果删除的结点不是叶子结点，那么删除该子树。
-
0.首先考虑，如果树是空树或者只有一个根节点root，直接将root置空即可。
-
我们把0放到BinaryTree中 */
-
-
public void delNode(int id){
-
// 1.如果当前结点的左子结点不为空，并且左子结点就是要删除的结点，就将this.left=null，然后递归结束
-
if (
this.left !=
null &&
this.left.no == id){
-
this.left =
null;
-
return;
-
}
-
// 2.如果当前结点的右子结点不为空，并且右子结点就是要删除的结点，就将this.right=null，然后递归结束
-
if (
this.right !=
null &&
this.right.no == id){
-
this.right =
null;
-
return;
-
}
-
// 3.如果1和2没有删除掉，就需要向左子树递归删除
-
if (
this.left !=
null){
-
this.left.delNode(id);
-
}
-
// 4.如果3还没有删掉，就需要向右子树递归删除
-
if (
this.right !=
null){
-
this.right.delNode(id);
-
}
-
}
-
}
-
class BinaryTree{
-
private HeroNode root;
// 根结点
-
-
public BinaryTree(HeroNode root){
// 指定根结点
-
this.root = root;
-
}
-
-
-
// 删除结点
-
public void delNode(int id){
-
// 0.首先考虑，如果树是空树或者只有一个根节点root，直接将root置空即可,否则递归删除
-
if (
this.root !=
null){
-
if (root.getNo() == id){
//只有一个根节点root
-
root =
null;
-
}
else {
-
root.delNode(id);
-
}
-
}
else{
-
System.out.println(
"二叉树为空，无法删除");
-
}
-
}
-
}
-
public
class BinaryTreeDemo {
-
public static void main(String[] args) {
-
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,
"李逵");
// 根节点的右子结点的右子结点
-
BinaryTree binaryTree =
new BinaryTree(heroNode1);
-
heroNode1.setLeft(heroNode2);
-
heroNode1.setRight(heroNode3);
-
heroNode3.setLeft(heroNode4);
-
heroNode3.setRight(heroNode5);
-
-
int delNode =
2;
-
System.out.println(
"删除二叉树中的结点:"+delNode);
-
binaryTree.delNode(delNode);
-
System.out.println(
"删除后的二叉树遍历:");
-
binaryTree.preOrder();
-
-
}
-
}
转载：https://blog.csdn.net/weixin_43574446/article/details/105444451
查看评论