线性存储结构的方式
在学习树结构之前, 我们首先来复习一下线性存储结构的两种方式: 线性存储(包括数组)和链式存储
数组存储方式的分析
- 优点：通过下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。
- 缺点：如果要检索具体某个值，或者插入值(按一定顺序)会整体移动，效率较低
链式存储方式的分析
- 优点：在一定程度上对数组存储方式有优化(比如：插入一个数值节点，只需要将插入节点，链接到链表中即可， 删除效率也很好)。
- -缺点：在进行检索时，效率仍然较低，比如(检索某个值，需要从头节点开始遍历)
树存储方式的分析
- 能提高数据存储，读取的效率, 比如 利用 二叉排序树(Binary Sort Tree)，既可以保证数据的检索速度，同时也可以保证数据的插入，删除，修改的速度。
- 案例: [7, 3, 10, 1, 5, 9, 12]
树的常用术语(结合示意图理解):
- 节点: 又被称为节点元素, 节点对象, 指每个位置上的元素
- 根节点: 处于最顶部的节点
- 父节点、子节点: 相对的概念, 比如1是2,3的父节点. 那么反过来说2,3就是1的子节点
- 叶子节点 : 没有子节点的节点
- 节点的权(节点值)
- 路径(从root节点找到该节点的路线)
- 树的高度(最大层数)
- 森林 :多颗子树构成森林
二叉树
二叉树的概念
-
树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树。
-
二叉树的子节点分为左节点和右节点。
-
如果该二叉树的所有叶子节点都在最后一层，并且结点总数= 2^n -1 , n 为层数，则我们称为满二叉树。
-
如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树
二叉树应用一——二叉树的遍历
代码实现-利用二叉树实现水浒英雄榜
为了对比方便, 将本应该放到最后的代码运行结果图放在这里, 便于对比和观看
- 思路图
三种遍历结果
- 附加题要求如下：
前上图的 3号节点 “卢俊” , 增加一个左子节点 [5, 关胜]
使用前序，中序，后序遍历，请写出各自输出的顺序是什么?
三种遍历结果
代码实现
/**
* 二叉树的前序遍历
*
* @author TimePause
* @create 2020-02-12 9:22
*/
public class BinaryTreeDemo {
public static void main(String[] args) {
//创建一个二叉树对象与图中的四个节点
BinaryTree binaryTree = new BinaryTree();
HeroNode root = new HeroNode(1,"宋江");
HeroNode node2 = new HeroNode(2,"吴用");
HeroNode node3 = new HeroNode(3,"卢俊义");
HeroNode node4 = new HeroNode(4,"林冲");
//新增一个任务->查看二叉树顺序
//HeroNode node5 = new HeroNode(5,"关胜");
//手动创建二叉树, 并赋予每个节点如上图的关系
binaryTree.setRoot(root);
root.setLeft(node2);
root.setRight(node3);
node3.setRight(node4);
//node3.setLeft(node5);
// 进行遍历
System.out.println("前序遍历");
binaryTree.preOrder();//1,2,3,5,4
System.out.println("中序遍历");
binaryTree.midOrder();//2,1,5,3,4
System.out.println("后序遍历");
binaryTree.postOrder();//2,5,4,3,1
}
}
/**
* 再创建存放英雄节点的二叉树
*/
class BinaryTree{
private HeroNode root;//定义了二叉树的根节点
public HeroNode getRoot() {
return root;
}
public void setRoot(HeroNode root) {
this.root = root;
}
//前序遍历
public void preOrder(){
if (this.root!=null){
this.root.preOrder();
}else {
System.out.println("二叉树为空,无法遍历");
}
}
//中序遍历
public void midOrder(){
if (this.root!=null){
this.root.midOrder();
}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;
}
public void setNo(int no) {
this.no = no;
}
public void setName(String name) {
this.name = name;
}
public void setLeft(HeroNode left) {
this.left = left;
}
public void setRight(HeroNode right) {
this.right = right;
}
public int getNo() {
return no;
}
public String getName() {
return name;
}
public HeroNode getLeft() {
return left;
}
public HeroNode getRight() {
return right;
}
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", 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);
}
}
总结
- 前序遍历: 先输出父节点，再遍历左子树和右子树->父左右
- 中序遍历: 先遍历左子树，再输出父节点，再遍历右子树->左父右
- 后序遍历: 先遍历左子树，再遍历右子树，最后输出父节点->左右父
- 小结: 看输出父节点的顺序，就确定是前序，中序还是后序
二叉树应用二——二叉树的查找
二叉树-查找指定节点
- 请编写前序查找，中序查找和后序查找的方法。
- 并分别使用三种查找方式，查找 heroNO = 5 的节点
- 并分析各种查找方式，分别比较了多少次
实现代码
public class BinaryTreeDemo {
public static void main(String[] args) {
//创建一个二叉树对象与图中的四个节点
BinaryTree binaryTree = new BinaryTree();
HeroNode root = new HeroNode(1,"宋江");
HeroNode node2 = new HeroNode(2,"吴用");
HeroNode node3 = new HeroNode(3,"卢俊义");
HeroNode node4 = new HeroNode(4,"林冲");
//新增一个英雄节点->查看二叉树顺序
HeroNode node5 = new HeroNode(5,"关胜");
//手动创建二叉树, 并赋予每个节点如上图的关系
binaryTree.setRoot(root);
root.setLeft(node2);
root.setRight(node3);
node3.setRight(node4);
node3.setLeft(node5);
/* //定义要查找的节点的值
int resarchNO = 5;
//执行查找===>执行4次
System.out.println("执行前序查找!!!");
HeroNode resNode = binaryTree.preOrderSearch(resarchNO);
if (resNode!=null){
System.out.printf("节点找到.该节点编号为%d, 姓名为%s",resNode.getNo(),resNode.getName());
}else {
System.out.printf("没有找到编号为%d的节点",resarchNO);
}*/
//定义要查找的节点的值
int resarchNO = 5;
//执行查找==>3次
System.out.println("执行中序查找!!!");
HeroNode resNode = binaryTree.midOrderSearch(resarchNO);
if (resNode!=null){
System.out.printf("节点找到.该节点编号为%d, 姓名为%s",resNode.getNo(),resNode.getName());
}else {
System.out.printf("没有找到编号为%d的节点",resarchNO);
}
/* //定义要查找的节点的值
int resarchNO = 5;
//执行查找==>2次
System.out.println("执行后序查找!!!");
HeroNode resNode = binaryTree.postOrderSearch(resarchNO);
if (resNode!=null){
System.out.printf("节点找到.该节点编号为%d, 姓名为%s",resNode.getNo(),resNode.getName());
}else {
System.out.printf("没有找到编号为%d的节点",resarchNO);
}*/
}
}
/**
* 再创建存放英雄节点的二叉树
*/
class BinaryTree{
private HeroNode root;//定义了二叉树的根节点
public HeroNode getRoot() {
return root;
}
public void setRoot(HeroNode root) {
this.root = root;
}
//前序查找
public HeroNode preOrderSearch(int no){
if (this.root!=null){
return this.root.preOrderSearch(no);
}else {
return null;
}
}
//中序查找
public HeroNode midOrderSearch(int no){
if (this.root!=null){
return this.root.midOrderSearch(no);
}else {
return null;
}
}
//后序遍历
public HeroNode postOrderSearch(int no){
if (this.root!=null){
return this.root.midOrderSearch(no);
}else {
return null;
}
}
}
/**
* 先英雄节点类
*/
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;
}
public void setNo(int no) {
this.no = no;
}
public void setName(String name) {
this.name = name;
}
public void setLeft(HeroNode left) {
this.left = left;
}
public void setRight(HeroNode right) {
this.right = right;
}
public int getNo() {
return no;
}
public String getName() {
return name;
}
public HeroNode getLeft() {
return left;
}
public HeroNode getRight() {
return right;
}
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", name='" + name + '\'' +
'}';
}
/**
* 前序查找
* 如果找到就返回node, 如果找不到就返回null
* @param no
*/
public HeroNode preOrderSearch(int no){
System.out.println("执行了1次前序查找");
//1.比较当前节点是否是查找对象
if (this.no==no){
return this;
}
//2.创建一个HeroNode对象,用于存放返回的节点
HeroNode resNode = null;
// 如果左子节点不为空, 则向左递归前序查找
if (this.left!=null){
resNode = this.left.preOrderSearch(no);
}
// 如果左子树找到, 则返回
if (resNode!=null){
return resNode;
}
//3.如果右子节点不为空, 则向右递归前序查找
if (this.right!=null){
resNode = this.right.preOrderSearch(no);
}
// 如果右子树找到则返回相应节点, 找不到则返回初始化null
return resNode;
}
/**
* 中序查找
* 如果找到就返回node, 如果找不到就返回null
* @param no
*/
public HeroNode midOrderSearch(int no){
// 1.创建一个HeroNode对象,用于存放返回的节点
HeroNode resNode = null;
// 如果左子节点不为空, 则向左递归前序查找
if (this.left!=null){
resNode = this.left.midOrderSearch(no);
}
// 如果左子树找到, 则返回
if (resNode!=null){
return resNode;
}
System.out.println("执行了1次中序查找");
//2.比较当前节点是否是查找对象
if (this.no==no){
return this;
}
//3. 如果右子节点不为空, 则向右递归前序查找
if (this.right!=null){
resNode = this.right.midOrderSearch(no);
}
// 如果右子树找到则返回相应节点, 找不到则返回初始化null
return resNode;
}
/**
* 后序查找
* 如果找到就返回node, 如果找不到就返回null
* @param no
*/
public HeroNode postOrderSearch(int no){
// 1.如果左边不为空向左递归调用后序查找
HeroNode resNode = null;
if (this.left!=null){
resNode = this.left.postOrderSearch(no);
}
if (resNode!=null){
return resNode;//左子树找到直接返回
}
// 2.如果左边不为空则向右递归调用后序查找
if (this.right!=null){
resNode = this.right.postOrderSearch(no);
}
if (resNode!=null){
return resNode;
}
System.out.println("执行了1次后序查找");
// 3.如果左右子树都没找到,则对当前节点进行判断
if (this.no==no){
return this;//返回当前节点
}else {
return resNode;//返回默认值null
}
}
}
二叉树应用三——二叉树的删除
要求
- 如果删除的节点是叶子节点，则删除该节点
- 如果删除的节点是非叶子节点，则删除该子树.
- 测试，删除掉 5号叶子节点 和 3号子树.
代码实现
-
在HeroNode中添加删除节点的方法
public void delNode(int no){ // 如果当前节点的左子节点不为空, 并且符合删除条件, 则首先置为null然后返回(结束递归删除) if (this.left!=null && this.left.no==no){ this.left=null; return; } // 如果当前节点的右子节点不为空, 并且符合删除条件, 则首先置为null然后返回(结束递归删除) 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); } }2.在BinaryTree中添加删除节点方法
//二叉树的删除 public void delNode(int no){ if (this.root!=null){ // 如果只有一个root节点, 立即判断是不是要删除的节点 if (root.getNo()==no){//如果是, 直接置空 root = null; }else { //递归删除 root.delNode(no); } }else { System.out.println("二叉树为空,无法删除"); }3.在mian()函数中调用该方法
// 进行遍历 System.out.println("前序遍历"); binaryTree.preOrder();//1,2,3,5,4 binaryTree.delNode(5); System.out.println("删除节点5后的前序遍历"); binaryTree.preOrder();//1,2,3,4
结果展示
-
删除的节点为5时
-
删除的节点为3时
二叉树应用四——二叉树的顺序存储
顺序存储二叉树的概念
- 从数据存储来看，数组存储方式和树
- 的存储方式可以相互转换，即数组可
- 以转换成树，树也可以转换成数组，
见如下的示意图
要求:
- 右图的二叉树的结点，要求以数组 的方式来存放 arr : [1, 2, 3, 4, 5, 6, 6]
- 要求在遍历数组 arr时，仍然可以以 前序遍历，中序遍历和后序遍历的 方式完成结点的遍历
顺序存储二叉树的特点(结合上图):
- 顺序二叉树通常只考虑完全二叉树
- 第n个元素的左子节点为 2 * n + 1 , n为该元素在数组中顺序存储时的下标
- 第n个元素的右子节点为 2 * n + 2
- 第n个元素的父节点为 (n-1) / 2
实现代码
- 重载前序遍历的方法,方便我们直接调用
- 为什么我们虽然没有让下标自增, 但是却能够实现自动遍历所有元素?
因为使用了递归调用
/**
* 顺序存储二叉树
*
* @author TimePause
* @create 2020-02-14 11:28
*/
public class ArrBinaryTreeDemo {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7};
ArrBinaryTree bTree = new ArrBinaryTree(arr);
/* bTree.preOrder(0);*/
bTree.preOrder();
}
}
//编写一个ArrBinaryTree, 实现遍历及相关操作
class ArrBinaryTree{
private int[] arr;//存储数据节点的数组
public ArrBinaryTree(int[] arr){//构造方法
this.arr = arr;
}
/**
*** 重载编写好的方法,方便我们直接调用
*/
public void preOrder(){
this.preOrder(0);//这里直接调用了二叉树的遍历方法,并传入了数组的初始下标
}
/**
* 编写一个方法,实现二叉树的遍历
* @param index 数组的下标
*/
public void preOrder(int index) {
System.out.println("该方法被调用了一次");
// 如果数组为空
if (arr == null || arr.length == 0) {
System.out.println("数组为空,不能进行遍历");
}
//输出当前这个元素
System.out.println(arr[index]);
// 向左进行递归遍历
if ((2*index+1)<arr.length){
preOrder(2*index+1);
}
// 向右进行递归遍历
if ((2*index+2)<arr.length){
preOrder(2*index+2);
}
}
}
前序遍历结果测试
中序后序遍历代码实现
/**
* 中序遍历
* @param index
*/
public void midOrder(int index){
if (arr==null || arr.length==0){
System.out.println("数组为空,无法遍历");
}
// 左子树递归调用中序遍历
if ((2*index+1)<arr.length){
midOrder(2*index+1);
}
// 输出当前节点
System.out.println(arr[index]);
// 右子树递归调用中序遍历
if ((2*index+2)<arr.length){
midOrder(2*index+2);
}
}
/**
* 后序遍历
* @param index
*/
public void postOrder(int index){
if (arr==null || arr.length==0){
System.out.println("数组为空,无法进行遍历");
}
// 左子树递归调用后序遍历
if ((2*index+1)<arr.length){
postOrder(2*index+1);
}
// 右子树递归调用后序遍历
if ((2*index+2)<arr.length){
postOrder(2*index+2);
}
// 输出当前节点
System.out.println(arr[index]);
}
结果测试
测试中序遍历
测试后序遍历
- 一定是先遍历了叶子节点(左右子节点)然后才遍历父节点
二叉树应用五——线索化二叉树
将数列 {1, 3, 6, 8, 10, 14 } 构建成一颗二叉树. n+1=7
问题分析:
- 当我们对上面的二叉树进行中序遍历时，数列为 {8, 3, 10, 1, 6, 14 }
- 但是 6, 8, 10, 14 这几个节点的 左右指针，并没有完全的利用上.
- 如果我们希望充分的利用 各个节点的左右指针， 让各个节点可以指向自己的前后节点,怎么办?
- 解决方案-线索二叉树
线索二叉树基本介绍
-
n个结点的二叉链表中含有n+1
公式 2n-(n-1)=n+1个空指针域。利用二叉链表中的空指针域，存放指向该结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为"线索"） -
这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种
-
一个结点的前一个结点，称为前驱结点
-
一个结点的后一个结点，称为后继结点
线索二叉树应用案例
思路分析: 中序遍历的结果：{8, 3, 10, 1, 14, 6}
说明: 当线索化二叉树后，Node节点的 属性 left 和 right ，有如下情况:
-
left 指向的是左子树，也可能是指向的前驱节点. 比如 ① 节点 left 指向的左子树, 而 ⑩ 节点的 left 指向的就是前驱节点.
-
right指向的是右子树，也可能是指向后继节点，比如 ① 节点right 指向的是右子树，而⑩ 节点的right 指向的是后继节点.
代码实现
基于前面代码进行修改, 不重复造轮子
/**
* 线索化二叉树
*
* @author TimePause
* @create 2020-02-14 20:18
*/
public class ThreadedBinaryTreeDemo {
public static void main(String[] args) {
//测试一把中序线索二叉树的功能
HeroNode root = new HeroNode(1, "tom");
HeroNode node2 = new HeroNode(3, "jack");
HeroNode node3 = new HeroNode(6, "smith");
HeroNode node4 = new HeroNode(8, "mary");
HeroNode node5 = new HeroNode(10, "king");
HeroNode node6 = new HeroNode(14, "dim");
//二叉树，后面我们要递归创建, 现在简单处理使用手动创建
root.setLeft(node2);
root.setRight(node3);
node2.setLeft(node4);
node2.setRight(node5);
node3.setLeft(node6);
//测试中序线索化
ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
threadedBinaryTree.setRoot(root);
threadedBinaryTree.threadedNodes();
//测试: 以10号节点测试
HeroNode leftNode = node5.getLeft();
HeroNode rightNode = node5.getRight();
System.out.println("10号结点的前驱结点是 =" + leftNode); //3
System.out.println("10号结点的后继结点是=" + rightNode); //1
System.out.println("遍历线索化二叉树");
threadedBinaryTree.threadedList();
}
}
/**
* 再创建存放英雄节点的二叉树
*/
class ThreadedBinaryTree{
private HeroNode root;//定义了二叉树的根节点
// ***为了实现线索化, 需要创建要给指向当前节点的前驱节点的指针
// ***在递归进行线索化时,pre总是保留前一个节点
private HeroNode pre = null;
public void setRoot(HeroNode root) {
this.root = root;
}
//遍历线索化二叉树的方法
public void threadedList() {
//定义一个变量，存储当前遍历的结点，从root开始
HeroNode node = root;
while(node != null) {
//循环的找到leftType == 1的结点，第一个找到就是8结点
//后面随着遍历而变化,因为当leftType==1时，说明该结点是按照线索化
//处理后的有效结点
while(node.getLeftType() == 0) {
node = node.getLeft();
}
//打印当前这个结点
System.out.println(node);
//如果当前结点的右指针指向的是后继结点,就一直输出
while(node.getRightType() == 1) {
//获取到当前结点的后继结点
node = node.getRight();
System.out.println(node);
}
//替换这个遍历的结点
node = node.getRight();
}
}
// 同名函数,但参数列表不同=>重载=>方便调用
public void threadedNodes() {
threadedNodes(root);
}
/**
* 编写对二叉树进行中序线索化的方法
* @param node 当前需要线索化的节点
*/
public void threadedNodes(HeroNode node){
// 如果node==null,不能线索化
if (node==null){
return;
}
//(一)先线索化左子树
threadedNodes(node.getLeft());
//(二)线索化当前结点[有难度]
//处理当前结点的前驱结点
//以8号结点来理解
//8结点的.left = null , 8结点的.leftType = 1
if(node.getLeft() == null) {
//让当前结点的左指针指向前驱结点
node.setLeft(pre);
//修改当前结点的左指针的类型,指向前驱结点
node.setLeftType(1);
}
//处理后继结点
if (pre != null && pre.getRight() == null) {
//让前驱结点的右指针指向当前结点
pre.setRight(node);
//修改前驱结点的右指针类型
pre.setRightType(1);
}
//!!! 每处理一个结点后，让当前结点是下一个结点的前驱结点
pre = node;
//(三)再线索化右子树
threadedNodes(node.getRight());
}
//前序遍历
public void preOrder(){
if (this.root!=null){
this.root.preOrder();
}else {
System.out.println("二叉树为空,无法遍历");
}
}
//中序遍历
public void midOrder(){
if (this.root!=null){
this.root.midOrder();
}else {
System.out.println("二叉树为空,无法遍历");
}
}
//后序遍历
public void postOrder(){
if (this.root!=null){
this.root.postOrder();
}else {
System.out.println("二叉树为空,无法便利");
}
}
//前序查找
public HeroNode preOrderSearch(int no){
if (this.root!=null){
return this.root.preOrderSearch(no);
}else {
return null;
}
}
//中序查找
public HeroNode midOrderSearch(int no){
if (this.root!=null){
return this.root.midOrderSearch(no);
}else {
return null;
}
}
//后序遍历
public HeroNode postOrderSearch(int no){
if (this.root!=null){
return this.root.midOrderSearch(no);
}else {
return null;
}
}
//二叉树的删除
public void delNode(int no){
if (this.root!=null){
// 如果只有一个root节点, 立即判断是不是要删除的节点
if (root.getNo()==no){//如果是, 直接置空
root = null;
}else {
//递归删除
root.delNode(no);
}
}else {
System.out.println("二叉树为空,无法删除");
}
}
}
/**
* 先英雄节点类
*/
class HeroNode{
private int no;
private String name;
private HeroNode left;//左子节点
private HeroNode right;//右子节点
/*
说明:
1. 如果leftType==0表示指向的是左子树, 如果1则表示指向前驱节点
2. 如果rightType==0表示指向的是右子树, 如果1则表示指向后继节点
*/
private int leftType;
private int rightType;
public int getLeftType() {
return leftType;
}
public int getRightType() {
return rightType;
}
public void setLeftType(int leftType) {
this.leftType = leftType;
}
public void setRightType(int rightType) {
this.rightType = rightType;
}
public HeroNode(int no, String name) {
this.no = no;
this.name = name;
}
public void setNo(int no) {
this.no = no;
}
public void setName(String name) {
this.name = name;
}
public void setLeft(HeroNode left) {
this.left = left;
}
public void setRight(HeroNode right) {
this.right = right;
}
public int getNo() {
return no;
}
public String getName() {
return name;
}
public HeroNode getLeft() {
return left;
}
public HeroNode getRight() {
return right;
}
@Override
public String toString() {
return "HeroNode{" +
"no=" + no +
", 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);
}
/**
* 前序查找
* 如果找到就返回node, 如果找不到就返回null
* @param no
*/
public HeroNode preOrderSearch(int no){
System.out.println("执行了1次前序查找");
//1.比较当前节点是否是查找对象
if (this.no==no){
return this;
}
//2.创建一个HeroNode对象,用于存放返回的节点
HeroNode resNode = null;
// 如果左子节点不为空, 则向左递归前序查找
if (this.left!=null){
resNode = this.left.preOrderSearch(no);
}
// 如果左子树找到, 则返回
if (resNode!=null){
return resNode;
}
//3.如果右子节点不为空, 则向右递归前序查找
if (this.right!=null){
resNode = this.right.preOrderSearch(no);
}
// 如果右子树找到则返回相应节点, 找不到则返回初始化null
return resNode;
}
/**
* 中序查找
* 如果找到就返回node, 如果找不到就返回null
* @param no
*/
public HeroNode midOrderSearch(int no){
// 1.创建一个HeroNode对象,用于存放返回的节点
HeroNode resNode = null;
// 如果左子节点不为空, 则向左递归前序查找
if (this.left!=null){
resNode = this.left.midOrderSearch(no);
}
// 如果左子树找到, 则返回
if (resNode!=null){
return resNode;
}
System.out.println("执行了1次中序查找");
//2.比较当前节点是否是查找对象
if (this.no==no){
return this;
}
//3. 如果右子节点不为空, 则向右递归前序查找
if (this.right!=null){
resNode = this.right.midOrderSearch(no);
}
// 如果右子树找到则返回相应节点, 找不到则返回初始化null
return resNode;
}
/**
* 后序查找
* 如果找到就返回node, 如果找不到就返回null
* @param no
*/
public HeroNode postOrderSearch(int no){
// 1.如果左边不为空向左递归调用后序查找
HeroNode resNode = null;
if (this.left!=null){
resNode = this.left.postOrderSearch(no);
}
if (resNode!=null){
return resNode;//左子树找到直接返回
}
// 2.如果左边不为空则向右递归调用后序查找
if (this.right!=null){
resNode = this.right.postOrderSearch(no);
}
if (resNode!=null){
return resNode;
}
System.out.println("执行了1次后序查找");
// 3.如果左右子树都没找到,则对当前节点进行判断
if (this.no==no){
return this;//返回当前节点
}else {
return resNode;//返回默认值null
}
}
public void delNode(int no){
// 如果当前节点的左子节点不为空, 并且符合删除条件, 则首先置为null然后返回(结束递归删除)
if (this.left!=null && this.left.no==no){
this.left=null;
return;
}
// 如果当前节点的右子节点不为空, 并且符合删除条件, 则首先置为null然后返回(结束递归删除)
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);
}
}
}
转载：https://blog.csdn.net/qq_43371556/article/details/104258832
查看评论