DataStructures - 04 ：二叉树_二叉树与数组_线索化_堆_线索二叉树 数组_我一直在流浪的博客-程序员宅基地
技术标签： 【Leetcode-算法】
文章目录
1、二叉树
1.1 二叉树的遍历
1、概念：
前序遍历：根节点、当前节点左子树、当前节点右子树： 1、2、3、5、4
中序遍历：当前节点左子树、 根节点、当前节点右子树：2、1、5、3、4
后序遍历：当前节点左子树、当前节点右子树、 根节点：2、5、4、3、1
2、代码实现：
（1）HeroNode节点类的实现：
@Data
public class HeroNode{
private int no;
private String name;
private HeroNode left;
private HeroNode right;
//前序遍历
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(int no, String name) {
this.no = no;
this.name = name;
}
//toString类
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + "]";
}
}
（2）BinaryTree二叉树类的实现：
public class BinaryTree{
private HeroNode 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 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("根节点为空无法遍历");
}
}
}
（3）BinaryDemo测试类：创建一颗二叉树并测试
public class BinaryDemo {
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, "关胜");
//说明，我们先手动创建该二叉树，后面我们学习递归的方式创建二叉树
root.setLeft(node2);
root.setRight(node3);
node3.setRight(node4);
node3.setLeft(node5);
binaryTree.setRoot(root);
// binaryTree.postOrder();
binaryTree.infixOrder();
}
}
1.2 二叉树查找某个节点
1、思路：
查找指定的节点：根据节点编号no进行查找
1、前序查找：
（1）先判断当前节点的no是否等于需要查找的
（2）如果当前节点的左子节点不为空，向左递归前序查找
（3）如果当前节点的右子节点不为空，向右递归前序查找
2、中序查找：
（1）如果当前节点的左子节点不为空，向左递归中序查找
（2）先判断当前节点的no是否等于需要查找的
（3）如果当前节点的右子节点不为空，向右递归中序查找
3、后序查找：
（1）如果当前节点的左子节点不为空，向左递归后序查找
（2）如果当前节点的右子节点不为空，向右递归后序查找
（3）先判断当前节点的no是否等于需要查找的
2、代码实现：
（1）HeroNode节点类：
@Data
public class HeroNode{
private int no;
private String name;
private HeroNode left;
private HeroNode right;
//前序查找
public HeroNode preSearch(int no){
if(this.no==no){
return this;
}
HeroNode resultNode = null;
if(this.left!=null){
resultNode = this.left.preSearch(no);
}
if(resultNode!=null){
return resultNode;
}
if(this.right!=null){
resultNode = this.right.preSearch(no);
}
return resultNode;
}
//中序查找
public HeroNode infixSearch(int no){
HeroNode resultNode = null;
if(this.left!=null){
resultNode = this.left.infixSearch(no);
}
if(resultNode!=null){
return resultNode;
}
if(this.no==no){
return this;
}
if(this.right!=null){
resultNode = this.right.infixSearch(no);
}
return resultNode;
}
//后序查找
public HeroNode postSearch(int no){
HeroNode resultNode = null;
if(this.left!=null){
resultNode = this.left.postSearch(no);
}
if(resultNode!=null){
return resultNode;
}
if(this.right!=null){
resultNode = this.right.postSearch(no);
}
if(resultNode!=null){
return resultNode;
}
if(this.no==no){
return this;
}
return resultNode;
}
//构造方法
public HeroNode(int no, String name) {
this.no = no;
this.name = name;
}
//toString类
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + "]";
}
}
（2）BinaryTree二叉树类：
public class BinaryTree{
private HeroNode root;
public void setRoot(HeroNode root) {
this.root = root;
}
//前序查找
public HeroNode preSearch(int no){
if(root!=null){
return root.preSearch(no);
}else {
return null;
}
}
//中序查找
public HeroNode infixSearch(int no){
if(root!=null){
return root.infixSearch(no);
}else{
return null;
}
}
//后序查找
public HeroNode postSearch(int no){
if(root!=null){
return root.postSearch(no);
}else{
return null;
}
}
}
（3）BinaryDemo 测试类：
public class BinaryDemo {
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, "关胜");
//说明，我们先手动创建该二叉树，后面我们学习递归的方式创建二叉树
root.setLeft(node2);
root.setRight(node3);
node3.setRight(node4);
node3.setLeft(node5);
binaryTree.setRoot(root);
HeroNode heroNode = binaryTree.postSearch(3);
if(heroNode!=null){
System.out.println(heroNode.toString());
}else{
System.out.println("找不到");
}
}
}
1.3 二叉树删除某个节点
需求：
（1）如果删除的节点是叶子节点，就删除该节点
（2）如果删除的是非叶子节点，就删除该子树
1、思路：
1、如果只有一个root节点，等价于将二叉树置空
2、如果当前节点左子节点不为空，并且左子节点就是需要删除的节点，this.left=null，并return
3、如果当前节点右子节点不为空，并且右子节点就是需要删除的节点，this.left=null，并return
4、如果左右节点都不是要删除的节点，向左递归删除节点
5、如果向左递归没有找到要删除的节点，向右递归删除节点
（1）节点类HeroNode：
@Data
public class HeroNode{
private int no;
private String name;
private HeroNode left;
private HeroNode right;
//删除某个节点
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);
}
}
//构造方法
public HeroNode(int no, String name) {
this.no = no;
this.name = name;
}
//toString类
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + "]";
}
}
（2）二叉树类BinaryTree：
public class BinaryTree{
private HeroNode root;
public void setRoot(HeroNode root) {
this.root = root;
}
//删除某个节点
public void delNode(int no){
if(root!=null){
if(root.getNo()==no){
root = null;
}else{
root.delNode(no);
}
}else{
System.out.println("树为空");
}
}
}
（3）测试类BinaryDemo：
public class BinaryDemo {
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, "关胜");
//说明，我们先手动创建该二叉树，后面我们学习递归的方式创建二叉树
root.setLeft(node2);
root.setRight(node3);
node3.setRight(node4);
node3.setLeft(node5);
binaryTree.setRoot(root);
System.out.println("删除前.................");
binaryTree.preOrder();
binaryTree.delNode(5);
System.out.println("删除后.................");
binaryTree.preOrder();
}
}
2、顺序存储二叉树
1、概念：
将二叉树的数据以数组的方式来存放，并且遍历的时候仍然可以以前序、中序、后序的方式来遍历。
顺序存储二叉树的特点：
- 顺序存储二叉树通常只考虑完全二叉树
- 第n个元素的左子节点为2*n+1
- 第n个元素的右子节点为2*n+2
- 第n个元素的父节点为(n-1)/2
2、代码实现：
（1）ArrayBinaryTree：传入一个数组
public class ArrayBinaryTree {
private int[] arr;
public void setArr(int[] arr) {
this.arr = arr;
}
public void preOrder(){
preOrder(0);
}
/**
* 前序遍历
* @param index 数组的索引
*/
public void preOrder(int index){
if(arr==null|| arr.length==0){
return;
}
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);
}
}
}
（2）测试类ArrayBinaryTreeDemo：
public class ArrayBinaryTreeDemo {
public static void main(String[] args) {
int[] arr = {
12,34,45,67,8,289,90};
ArrayBinaryTree arrayBinaryTree = new ArrayBinaryTree();
arrayBinaryTree.setArr(arr);
arrayBinaryTree.preOrder();
}
}
3、线索化二叉树
3.1 实现线索化二叉树
1、概念：
一个节点的前一个节点称为前驱节点
一个节点的后一个节点称为后继节点
n个节点的二叉链表中含有n+1个空指针域，利用二叉链表中的空指针域，存放指向节点在某种遍历次序下的前驱和后继节点的指针（这种附加的指针称为线索）
线索二叉树分为前序线索二叉树、中序线索二叉树、后序线索二叉树。
将二叉树进行中序线索二叉树。中序遍历的数列为{67、34、8、12、289、45}
经过线索化之后：
left指向的可能是左子树也可能是前驱节点
right指向的可能是右子树也可能是后继节点
2、代码实现：
（1）HeroNode节点类：
@Data
public class HeroNode {
private int no;
private String name;
private HeroNode left;
private HeroNode right;
//leftType=0代表指向左子树，leftType=1代表指向前驱节点
private int leftType;
//rightType=0代表指向右子树，leftType=1代表指向后继节点
private int rightType;
public HeroNode(int no, String name) {
this.no = no;
this.name = name;
}
@Override
public String toString() {
return "HeroNode [no=" + no + ", name=" + name + "]";
}
}
（2）ThreadedBinaryTree线索化二叉树类：
public class ThreadedBinaryTree {
private HeroNode root;
public void setRoot(HeroNode root) {
this.root = root;
}
//pre总是指向前驱节点
private HeroNode pre = null;
public void threadedNodes(){
threadedNodes(root);
}
public void threadedNodes(HeroNode node){
if(node==null){
return;
}
//线索化左子树
threadedNodes(node.getLeft());
//线索化当前节点
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());
}
}
（3）测试类ThreadedBinaryTreeDemo：
public class ThreadedBinaryTreeDemo {
public static void main(String[] args) {
//测试一把中序线索二叉树的功能
HeroNode root = new HeroNode(12, "tom");
HeroNode node2 = new HeroNode(34, "jack");
HeroNode node3 = new HeroNode(45, "smith");
HeroNode node4 = new HeroNode(67, "mary");
HeroNode node5 = new HeroNode(8, "king");
HeroNode node6 = new HeroNode(289, "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();
//测试: 以8号节点测试
System.out.println(node5.getLeft());
System.out.println(node5.getRight());
}
}
3.2 线索化二叉树的遍历
对前面实现的中序线索二叉树进行遍历：
在ThreadedBinaryTree类中国添加一个遍历中序线索化二叉树的方法：
//遍历线索化二叉树
public void threadList(){
HeroNode node = root;
while(node!=null){
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();
}
}
4、二叉堆
4.1 堆的概念
1、完全二叉树：
2、堆是具有以下性质的完全二叉树：
（1）大顶堆：每个节点的值都大于或者等于其左右孩子节点的值
（2）小顶堆：每个节点的值都小于或者等于其左右孩子节点的值
4.2 堆排序
1、堆排序的思想：
- 将待排序的序列先构成一个大顶堆
- 此时，整个序列的最大值就是堆顶的元素
- 将其与末尾元素进行交换，此时末尾就是最大值
- 然后将剩余的n-1个元素重新构成堆，这样会得到n个元素的次小值，如此反复，就可以得到一个有序的序列
2、小顶堆映射到数组：
arr[i]>=arr[2*i+1]且arr[i]>=arr[2*i+2]
3、将一个序列调整为大顶堆的过程：
按照从做到右，从上到下的顺序调整各个非叶子节点：
public class HeapSort {
/**
* @param arr
* @param i 表示非叶子节点在数组中的索引
* @param length 表示对多少个元素进行调整
*/
public static void adjustHeap(int arr[],int i,int length){
int temp = arr[i];
//k表示i的左子节点
for(int k=2*i+1;k<length;k=2*k+1){
//如果左子节点<右子节点，就让k指向右子节点
if(k+1<length && arr[k]<arr[k+1]){
k++;
}
if(arr[k]>temp){
arr[i] = arr[k];
arr[k] = temp;
i = k;
}else{
break;
}
}
}
//测试将序列逐步调整为大顶堆的方法
public static void main(String[] args) {
int arr[] = {
12,34,45,67,8,78,5,23,99};
//将以3为对应的非叶子节点的子树调整为大顶堆
adjustHeap(arr,3,arr.length);
System.out.println(Arrays.toString(arr));
//将以2为对应的非叶子节点的子树调整为大顶堆
adjustHeap(arr,2,arr.length);
System.out.println(Arrays.toString(arr));
//将以1为对应的非叶子节点的子树调整为大顶堆
adjustHeap(arr,1,arr.length);
System.out.println(Arrays.toString(arr));
//将以0为对应的非叶子节点的子树调整为大顶堆
adjustHeap(arr,0,arr.length);
System.out.println(Arrays.toString(arr));
}
}
4、堆排序：
package 二叉堆排序;
import java.util.Arrays;
public class HeapSort {
public static void main(String[] args) {
int arr[] = {
12,34,45,67,8,78,5,23,99};
heapSort(arr);
}
//编写一个堆排序的方法
public static void heapSort(int arr[]) {
/**
* 将一个序列转换成大顶堆
*/
for(int i=arr.length/2-1;i>=0;i--){
adjustHeap(arr,i,arr.length);
}
System.out.println("将序列转换为大顶堆：");
System.out.println(Arrays.toString(arr));
int temp;
for(int j=arr.length-1;j>0;j--){
//交换
temp = arr[j];
arr[j] = arr[0];
arr[0] = temp;
//此时只需要调整堆顶节点即可，因此堆顶下面的节点已经符合堆的定义了
adjustHeap(arr,0,j);
System.out.println("将剩余序列转换成大顶堆：");
System.out.println(Arrays.toString(arr));
}
}
/**
* @param arr
* @param i 表示非叶子节点在数组中的索引
* @param length 表示对多少个元素进行调整
*/
public static void adjustHeap(int arr[],int i,int length){
int temp = arr[i];
//k表示i的左子节点
for(int k=2*i+1;k<length;k=2*k+1){
//如果左子节点<右子节点，就让k指向右子节点
if(k+1<length && arr[k]<arr[k+1]){
k++;
}
if(arr[k]>temp){
arr[i] = arr[k];
arr[k] = temp;
i = k;
}else{
break;
}
}
}
}
输出结果：
将序列转换为大顶堆：
[99, 67, 78, 34, 8, 45, 5, 23, 12]
将剩余序列转换成大顶堆：
[78, 67, 45, 34, 8, 12, 5, 23, 99]
将剩余序列转换成大顶堆：
[67, 34, 45, 23, 8, 12, 5, 78, 99]
将剩余序列转换成大顶堆：
[45, 34, 12, 23, 8, 5, 67, 78, 99]
将剩余序列转换成大顶堆：
[34, 23, 12, 5, 8, 45, 67, 78, 99]
将剩余序列转换成大顶堆：
[23, 8, 12, 5, 34, 45, 67, 78, 99]
将剩余序列转换成大顶堆：
[12, 8, 5, 23, 34, 45, 67, 78, 99]
将剩余序列转换成大顶堆：
[8, 5, 12, 23, 34, 45, 67, 78, 99]
将剩余序列转换成大顶堆：
[5, 8, 12, 23, 34, 45, 67, 78, 99]
分析过程：
智能推荐
在Linux如何增加磁盘_linux添加硬盘_杨_修的博客-程序员宅基地
Hello，各位看官好啊~，今天给大家讲解一下，当Linux上磁盘空间不够时，我们该如何去新增一块硬盘呢，废话不多说，直接给大家演示：Linux新增磁盘可以大致划分为一下四步：（1）在虚拟机上添加一块硬盘（2）为硬盘进行分区（3）初始化硬盘分区（4）挂载打开虚拟机，鼠标右键自己搭载的虚拟系统(要进行新增磁盘的那个系统)，点击设置进去后找到添加按键，单击选择硬盘，点击下一步磁盘类型选择SCSI，点击下一步选择创建新的虚拟磁盘，点击下一步磁盘空间大小根据自己需求来设置，注意大家提_linux添加硬盘
Laravel 5.8 正式发布_coderForPhp的博客-程序员宅基地
又可以学习了！ 点击查看地址
warning: C4305从“int”到“char” 截断_从int到char截断怎么办_MoreChiession的博客-程序员宅基地
有时候想打印出一些特殊符号来组成图像的时候，会遇到这种问题：特殊字符无法赋值给char型字符。这时候有两种解决办法。 方法一：将char型改为string型。（#include <string>） 一般来说，没办法赋值给char型是因为这个特殊符号虽然看上去只有一个字符，但实际上它所占的空间是一个字符串。如下图所示： 将普通字符以字符的形式赋值给s1，特殊字符以字符的形式赋..._从int到char截断怎么办
u-boot启动过程分析（源码）_Charistain_huang的博客-程序员宅基地
本文来自程序员宅基地，转载请标明出处：http://blog.csdn.net/linda_si/archive/2008/12/05/3451545.aspx建议之间去看那个帖子（那里有图解）为什么要分析源代码？分析优秀的源代码本身就是一个学习的过程，也是进行深入研究的必经之路。不过在此我们的主要目的并非要研究U-boot或Bootloader技术本身，而仅仅是为了成功的并且恰当的
整数种1出现的次数——js_js算出100~1300的整数中1出现的次数?_wangmumu_zzz的博客-程序员宅基地
整数种1出现的次数求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。思路把数组转化成字符串，再进行正则匹配，把不是1的都去掉，然后..._js算出100~1300的整数中1出现的次数?
Citrix Receive问题解决2_weixin_34268579的博客-程序员宅基地
浏览器1:客户端通过Web界面去访问StoreFront的时候对浏览器是有一定的要求，IE要求必须在IE8版本以上，如果版本低于要求的版本打开显示界面显示报错。图(1)因为IE版本低于IE82:对于火狐浏览器需要做以下设置图(2)在设置里面选择打开的ICA使用CitrixReceiver3：百度浏览器和猎豹浏览器等不推荐使用。CitrixReceiver客户端1:对..._虚拟桌面报错1110
随便推点
MFC ------- AfxGetMainWnd( )_无敌三角猫的博客-程序员宅基地
CWnd* AfxGetMainWnd( ); 使用AfxGetMainWnd函数获取MFC程序中的主框架类指针是一个常用作法。就是获得应用程序主窗口的指针，AfxGetMainWnd()-> m_hWnd是主窗口的句柄。
vue单文件组件_北巷以北的博客-程序员宅基地
简介以前文件的组织是以.HTML、.js以及.css/less/scss这些文件进行垂直分割的，而Vue中我们以组件为单位构造，因此，最好的方式是把这些不同的类型的文件与组件相关的部分，围绕组件组合成一个文件即.vue文件，我称其为水平分割。另外，在中写模板也比原来的字符串形式的模板方便的多。在webpack里面要加载*.vue文件，需要下面两个包$npm install vue-loade...
40余个超好用的在线影视站点_1090影视_HernSong的博客-程序员宅基地
综合影视低端电影：http://ddrk.me/ 1090影视：https://1090ys.com 碟影世界：http://www.952780.com/ 播王：https://bowan.su/ 吾爱看电影：http://www.5aikp.com/ 魔力电影网：https://magbt.net/ 胖子视频：http://www.pangzitv.com/ 白鹿影院：htt..._1090影视
中国人非常喜欢6这个数字，因为大家总爱说66大顺啊。数学狂人李某人喜欢把什么都数字化，于是她把顺利这个词也定义了数量级，6代表1级顺利，66代表2级顺利，666代表3级顺利，以此类推。你看，数学狂人的_666为什么等于110-程序员宅基地
7-133 666 (10 分)中国人非常喜欢6这个数字，因为大家总爱说66大顺啊。数学狂人李某人喜欢把什么都数字化，于是她把顺利这个词也定义了数量级，6代表1级顺利，66代表2级顺利，666代表3级顺利，以此类推。你看，数学狂人的世界总是让人无法理解。今天，李某人决定将数学进行到底，现在她设前n级顺利的和是sn。sn=6+66+666+…+66…66(n个6)。假设你已经知道了数字n，那么，你能帮李某人求出sn么?输入格式:输入一个正整数n，n的范围是[0,10)。输出格式:输出S_666为什么等于110
双偶幻方的c语言算法,任意阶幻方的c++实现----奇阶幻方、双偶幻方、单偶幻方。..._UMCloud优云数智的博客-程序员宅基地
幻方分为3类。奇阶幻方(奇数)、双偶幻方(能够被4整除，如8，12,16……)、单偶幻方(4m+2形式，如6,10……)，构造算法各不相同。下面的程序中，奇阶幻方的构造算法为Merzirac法。双偶幻方的构造算法为Spring法。单偶幻方的构造算法为Strachey法。奇数幻方：在第一行居中的方格内放1，依次向右上方填入2、3、4…，如果右上方已有数字，则向下移一格继续填写。双偶幻方：(1) 先把..._c生成偶数阶幻方
python 复制并重命名文件_Python_复制文件并重新命名_weixin_39638105的博客-程序员宅基地
1 #-*- coding:utf-8 -*-2# 引用 os 和 sys 两个模块3 importos4 importsys5# 定义 n 作为次数，显示 a.txt 文件内的内容6 n =07 h1 = open("a.txt").read()8 printh1# 这里做了一个循环，循环复制文件并修改文件名：9 whileTrue:10# 定义 R 为读取文件内容，检测 G:\ceshi 这个..._python cp后改名字