第十一章 顺序存储二叉树、线索化二叉树、大顶堆、小顶堆和堆排序

文章目录

第十一章 顺序存储二叉树、线索化二叉树、大顶堆、小顶堆和堆排序一、顺序存储二叉树1.介绍2.代码实现二、线索二叉树1.介绍2.代码实现三、堆1.介绍2.堆排序

一、顺序存储二叉树

1.介绍

二叉树的顺序存储，指的是使用顺序表（数组）存储二叉树。需要注意的是，顺序存储只适用于完全二叉树

如果我们想顺序存储普通二叉树，需要提前将普通二叉树转化为完全二叉树，下图为转化过程及其数组存储状态

从顺序表中还原二叉树也很简单，根据完全二叉树的性质将数组按照二叉树的前序、中序或者后序遍历输出

已知二叉树的中序遍历，再加上前序遍历或者后序遍历就可以重构二叉树

2.代码实现

package com.sisyphus.tree;/*** @Description: 顺序存储二叉树$* @Param: $* @return: $* @Author: Sisyphus* @Date: 7/23$*/public class ArrBinaryTreeDemo {public static void main(String[] args) {int[] arr = {1,2,3,4,5,6,7};//创建一个 ArrayBinaryTreeArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);System.out.println("前序");arrBinaryTree.preOrder(0); //1,2,4,5,3,6,7System.out.println("中序");arrBinaryTree.infixOrder(0);System.out.println("后序");arrBinaryTree.postOrder(0);}}//编写一个 ArrayBinaryTree，实现顺序存储二叉树遍历class ArrBinaryTree {private int[] arr;//存储数据结点的数组public ArrBinaryTree(int[] arr) {this.arr = arr;}//编写一个方法，完成顺序存储二叉树的前序遍历/*** @param index 数组下标*/public void preOrder(int index) {//如果数组为空，或者 arr.length = 0if (arr == null || arr.length == 0) {System.out.println("数组为空，无法遍历");}//输出当前这个元素System.out.println(arr[index]);//向左递归遍历if ((index * 2 + 1) < arr.length){preOrder(2 * index + 1);}//向右递归if ((index * 2 + 2) < arr.length){preOrder(2 * index + 2);}}public void infixOrder(int index) {//如果数组为空，或者 arr.length = 0if (arr == null || arr.length == 0) {System.out.println("数组为空，无法遍历");}//向左递归遍历if ((index * 2 + 1) < arr.length){infixOrder(2 * index + 1);}//输出当前这个元素System.out.println(arr[index]);//向右递归if ((index * 2 + 2) < arr.length){infixOrder(2 * index + 2);}}public void postOrder(int index) {//如果数组为空，或者 arr.length = 0if (arr == null || arr.length == 0) {System.out.println("数组为空，无法遍历");}//向左递归遍历if ((index * 2 + 1) < arr.length){postOrder(2 * index + 1);}//向右递归if ((index * 2 + 2) < arr.length){postOrder(2 * index + 2);}//输出当前这个元素System.out.println(arr[index]);}}

前序遍历：1245367

中序遍历：4251637

后序遍历：4526731

已知前序遍历和后序遍历

根据前序遍历特点，根结点为 1根据中序遍历特点，根结点 1 左边 425 为左子树（但无法确定左子树的结构），右边 637 为右子树左子树 425 在前序遍历中的顺序为 245 意味着 2 为左子树的根结点，且 4 一定是 2 的子结点（但此时无法确定是左还是右）再观察中序遍历 425，可知 4 为 2 的左子结点，5 为 2 的右子结点左子树构建完毕，再看右子树右子树 637 在前序遍历中的顺序为 673 意味着 6 为右子树的根结点，且 7一定是 6 的子结点（但此时无法确定是左还是右）再观察中序遍历 637，可知 6 为 3 的左子结点，7 为 3 的左子结点至此，二叉树构建完成

已知后序遍历和后序遍历

略，思路同上

二、线索二叉树

1.介绍

不管二叉树的形态如何，空链域的个数总是多过非空链域的个数。准确的说，一个有着 n 个结点的二叉树共有 2n 个链域，其中非空链域为 n - 1 个，空链域为 n + 1 个，我们能不能把这些空链域利用起来呢？

因此，提出了线索化二叉树，在原来的空链域里存放指针，指向其他结点，这种指针称为线索

建立线索的规则：

如果左链域为空，则存放中序遍历序列中该结点的前驱结点，这个结点称为当前结点的中序前驱如果右链域为空，则存放中序遍历序列中该结点的后继结点，这个结点称为当前结点的中序后继在每个结点中再增设两个标志域 leftType 和rightType，它们只有 0 和 1 两个值，0 表示左（右）指针指向的是子结点，1 表示左（右）指针指向的是前驱（后继）结点

2.代码实现

实现对二叉树的中序线索化以及对线索化后的二叉树进行遍历

package com.sisyphus.tree.threadedbinarytree;import java.util.ArrayDeque;/*** @Description: 线索化二叉树$* @Param: $* @return: $* @Author: Sisyphus* @Date: 7/23$*/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); //3System.out.println("10 号结点的后继结点为" + rightNode); //1//测试中序遍历线索化二叉树threadedBinaryTree.threadedList(); //8,3,11,10,4,6}}//定义 ThreadedBinaryTree 实现了线索化功能的二叉树class ThreadedBinaryTree{private HeroNode root;//为了实现线索化，需要创建一个指向当前结点的前驱结点的指针//在递归进行线索化时， pre 总是保留前一个结点private HeroNode pre = null;public void setRoot(HeroNode root){this.root = root;}//重载public void threadedNodes(){this.threadedNodes(root);}//遍历线索化二叉树的方法public void threadedList(){//定义一个变量，存储当前遍历的结点，从 root 开始HeroNode node = root;while(node != null){//循环地找到 leftType == 1 的结点，第一个找到的就是 8 结点while(node.getLeftType() == 0){node = node.getLeft();}//打印当前这个结点System.out.println(node);//如果当前结点的右指针指向的是后继节点，就一直输出while(node.getRightType() == 1){//获取到当前结点的后继节点node = node.getRight();System.out.println(node);}//如果当前结点的 rightType ！= 1，说明当前结点的 rightType == 1，也就是它的右指针没被线索化//因为它的右指针已经指向了右子结点，无法指向后继结点//所以我们要用他的右子结点替换当前结点，然后进入下一次循环node = node.getRight();}}//编写对二叉树进行中序线索化的方法public void threadedNodes(HeroNode node){//如果 node == null，不能线索化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());}}class HeroNode{private int no;private String name;private HeroNode left;private HeroNode right;//说明//1.如果 leftType == 0 表示指向的是左子树，如果等于 1 表示指向前驱节点//1.如果 rightType == 0 表示指向的是左子树，如果等于 1 表示指向前驱节点private int leftType;private int rightType;public HeroNode(int no, String name) {this.no = no;this.name = name;}public int getLeftType() {return leftType;}public void setLeftType(int leftType) {this.leftType = leftType;}public int getRightType() {return rightType;}public void setRightType(int rightType) {this.rightType = rightType;}public int getNo() {return no;}public void setNo(int no) {this.no = no;}public String getName() {return name;}public void setName(String name) {this.name = name;}public HeroNode getLeft() {return left;}public void setLeft(HeroNode left) {this.left = left;}public HeroNode getRight() {return right;}public void setRight(HeroNode right) {this.right = right;}@Overridepublic String toString() {return "HeroNode{" +"no=" + no +", name='" + name + '\'' +'}';}}

三、堆

1.介绍

堆(Heap)是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆

同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子

该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：

大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

2.堆排序

堆排序（HeapSort）是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它是不稳定排序。堆排序分为两种方法：

大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

一个子树中 3 个元素交换时，两个相同值的元素不会发生相对位置改变。但是在交换时整个堆中如果有两个相同值的元素，恰巧一个在堆即将发生交换的位置 A，另一个在其他位置 B，交换后在 A 位置的元素就跑到堆顶了。在堆排序的一次交换中，我们可以看出，两个相同值的元素，越靠近堆顶的位置越容易优先交换，越靠近即将发生交换的位置越不容易优先交换。也就是说，原来在位置 B 的元素本应该优先于位置 A 的元素出堆，但现在却可能排在其后，他们的相对顺序发生了改变，因此堆排序是一种不稳定的排序算法

算法步骤

将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行前两部，直到整个序列有序

代码实现

package com.sisyphus.tree;import java.util.Arrays;/*** @Description: 堆排序$* @Param: $* @return: $* @Author: Sisyphus* @Date: 7/24$*/public class HeapSprt {public static void main(String[] args) {int arr[] = {4,6,8,5,9};heapSort(arr);}//编写一个堆排序的方法public static void heapSort(int arr[]){int temp = 0;System.out.println("堆排序");// //分步完成// adjustHeap(arr,1,arr.length);// System.out.println("第一次" + Arrays.toString(arr)); //49856// adjustHeap(arr,0,arr.length);// System.out.println("第二次" + Arrays.toString(arr)); //96854//完成最终代码//将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆for (int i = arr.length / 2 - 1; i >= 0; i--){adjustHeap(arr,i,arr.length);}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("数组为" + Arrays.toString(arr));}//将一个数组（二叉树），调整成一个大顶堆/*** 调整索引为 i 的非叶子结点的位置* arr[] 中元素按照顺序存储顺序排列* arr[] = {4,6,8,5,9} => adjustHeap(arr,1,5) => arr[] = {4,9,8,5,6}* arr[] = {4,9,8,5,6} => adjustHeap(arr,0,5) => arr[] = {9,6,8,5,4}* @param arr 待调整的数组* @param i表示非叶子节点在数组中的索引* @param length 表示对多少个元素继续调整，length 实在逐渐减少的*/public static void adjustHeap(int[] arr, int i, int length){int temp = arr[i]; //先取出当前元素的值，保存在临时变量//开始调整//k = i * 2 + 1 为 i 结点的左子结点for (int k = i * 2 + 1; k < length; k = k * 2 + 1){if(k + 1 < length && arr[k] < arr[k+1]){//说明左子结点的值小于右子结点k++;//k 指向右子结点}if (arr[k] > temp){//如果子结点大于父结点arr[i] = arr[k];//把较大的值赋给当前结点i = k;//i 指向 k，继续循环比较}else{break;}}//当 for 循环结束后，我们已经将以 i 为父结点的树的最大值放在了树顶arr[i] = temp;//将 temp 指向树顶}}