行业知识
图灵之旅--二叉树&&堆&&排序
目录
- 树型结构
- 概念
- 树的表示形式
- 二叉树
- 概念
- 特殊的二叉树
- 二叉树性质
- 二叉树的存储
- 二叉树的遍历
- 前中后序遍历
- 优先级队列(堆)
- 概念
- 优先级队列的模拟实现
- 堆的性质
- 概念
- 堆的存储方式
- 堆的创建
- 堆常用接口介绍
- PriorityQueue的特性
- PriorityQueue常用接口介绍
- 优先级队列的构造
- 插入/删除/获取优先级最高的元素
- 堆的应用
- PriorityQueue的实现
- 堆排序
- Top-k问题
- java对象的比较
- PriorityQueue中插入对象
- 元素比较
- 对象比较
- 覆写基类的equals
- 基于Comparble接口类的比较
- 基于比较器比较
- 三种方式对比
- 集合框架中PriorityQueue的比较方式
- 排序
- 插入排序
- 直接插入排序
- 希尔排序
- 选择排序
- 基本思想
- 直接选择排序
- 堆排序
- 交换排序
- 冒泡排序
- 快速排序
- 快速排序优化
- 快速排序非递归
- 快速排序总结
- 归并排序
- 递归归并排序代码
- 递归归并排序代码
- 海量数据的排序问题
- 非基于比较排序
- 计���排序
树型结构
概念
树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成的有层次关系的集合
特点:
有一个特殊结点,叫作根结点,根节点没有前驱结点
除根结点,其余结点被分成M(M>0)个互不相交的集合T1,T2,…Tm,其中每个集合T又是一棵与树类似的子树,每棵子树的根结点有且只有一个前驱,可以有0或多个后继
树是递归定义
注意:树形结构中,子树之间不能有交际,否则不是树形结构
树:
子树是不相交的
除了根结点外,每个结点有且仅有一个父结点
一棵N个结点的树有N-1条边
结点的度：一个结点含有子树的个数称为该结点的度；
树的度：一棵树中，所有结点度的最大值称为树的度；
叶子结点或终端结点：度为0的结点称为叶结点；
双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点；
孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点；
根结点：一棵树中，没有双亲结点的结点；
结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推
树的高度或深度：树中结点的最大层次；
非终端结点或分支结点：度不为0的结点；
兄弟结点：具有相同父结点的结点互称为兄弟结点；
堂兄弟结点：双亲在同一层的结点互为堂兄弟；
结点的祖先：从根到该结点所经分支上的所有结点；
子孙：以某结点为根的子树中任一结点都称为该结点的子孙。
森林：由m（m>=0）棵互不相交的树组成的集合称为森林
树的表示形式
树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，实际中树有很多种表示方式，如：双亲表示法，孩子表示法、孩子双亲表示法、孩子兄弟表示法等等
二叉树
概念
一棵二叉树是结点的一 个有限集合,该集合:
- 或者为空
- 或者是由一个根节点加上两棵左子树和右子树的二叉树组成
特点:
- 二叉树不存在度大于2的结点
- 二叉树的子树有左右之分,次序不能颠倒,因此二叉树是序树
特殊的二叉树
- 满二叉树: 一棵二叉树，如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树。也就是说，如果一棵二叉树的层数为K，且结点总数是 ，则它就是满二叉树。
- 完全二叉树: 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
二叉树性质
- 根结点的层数是1,则一棵非空二叉树的第i层上最多有2^(i-1)(i>0)个结点
- 只有根结点的二叉树的深度为1,则深度为k的二叉树的最大结点数是2^k-1(k>=0)
- 对任何一棵二叉树,如果其叶结点个数为n0,度为2的非叶结点个数为n2,则有n0=n2+1;
- 具有n个结点的完全二叉树,如果按照上至下从左至右的顺序对所有结点从0开始编号,则对于序号为i的结点有:
若i>0,双亲序号:(i-1)/2;i=0,i为根结点编号,无双亲结点
若2i+1 int val; // 数据域 Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树 Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树}// 孩子双亲表示法class Node { int val; // 数据域 Node left; // 左孩子的引用，常常代表左孩子为根的整棵左子树 Node right; // 右孩子的引用，常常代表右孩子为根的整棵右子树 Node parent; // 当前节点的根节点}h3二叉树的遍历/h3 h4前中后序遍历/h4 p学习二叉树结构，最简单的方式就是遍历。所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题(比如：打印节点内容、节点内容加1)。 遍历是二叉树上最重要的操作之一，是二叉树上进行其它运算之基础。/pp在遍历二叉树时，如果没有进行某种约定，每个人都按照自己的方式遍历，得出的结果就比较混乱，如果按照某种规则进行约定，则每个人对于同一棵树的遍历结果肯定是相同的。如果N代表根节点，L代表根节点的左子树，R代表根节点的右子树，则根据遍历根节点的先后次序有以下遍历方式：/ppNLR：前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点—根的左子树—>根的右子树。
LNR：中序遍历(Inorder Traversal)——根的左子树—>根节点—>根的右子树。
LRN：后序遍历(Postorder Traversal)——根的左子树—>根的右子树—>根节点。
给你一个前序遍历序列和后序遍历序列不能创建一个二叉树,因为前序和后序确定的是根,不能确定左右
public class BinaryTree { public static class TreeNode { public char val; public int res; public TreeNode left; public TreeNode right; public TreeNode(char val) { this.val = val; } public TreeNode(int res) { this.res = res; } } public TreeNode createTree() { TreeNode A = new TreeNode('A'); TreeNode B = new TreeNode('B'); TreeNode C = new TreeNode('C'); TreeNode D = new TreeNode('D'); TreeNode E = new TreeNode('E'); TreeNode F = new TreeNode('F'); TreeNode G = new TreeNode('G'); TreeNode H = new TreeNode('H'); TreeNode root = A; A.left = B; A.right = C; B.left = D; B.right = E; E.right = H; C.left = F; C.right = G; return root; } // 前序遍历 void preOrder(TreeNode root) { if(root==null) { return; } System.out.print(root.val+" "); preOrder(root.left); preOrder(root.right); } // 中序遍历 void inOrder(TreeNode root) { if(root==null) { return; } inOrder(root.left); System.out.print(root.val+" "); inOrder(root.right); } // 后序遍历 void postOrder(TreeNode root) { if(root==null) { return; } postOrder(root.left); postOrder(root.right); System.out.print(root.val+" "); } public int nodeSize; // 获取树中节点的个数 int size(TreeNode root) { if(root==null) { return 0; } return size(root.left)+size(root.right)+1; } // 获取叶子节点的个数 public int leafNode; int getLeafNodeCount(TreeNode root) { if(root==null) { return 0; } if((root.left==null)&&(root.right==null)){ return 1; } return getLeafNodeCount(root.left) + getLeafNodeCount(root.right); } // 子问题思路-求叶子结点个数// 获取第K层节点的个数 int getKLevelNodeCount(TreeNode root,int k) { if(root==null) { return 0; } if(k==1) { return 1; } return getKLevelNodeCount(root.left,k-1) + getKLevelNodeCount(root.right,k-1); } // 获取二叉树的高度 int getHeight(TreeNode root) { if(root==null) { return 0; } return 1+(Math.max(getHeight(root.left), getHeight(root.right))); } // 检测值为value的元素是否存在 TreeNode find(TreeNode root, char val) { if(root==null) { return null; } if(root.val==val) { return root; } if(find(root.left,val)!=null) { return find(root.left,val); }; if(find(root.right,val)!=null) { return find(root.right,val); }; return null; } //层序遍历 public Queue queue = new LinkedList(); void levelOrderQueue(TreeNode root) { if(root==null) { return; } if(root.left!=null) { queue.offer(root.left); } if(root.right!=null) { queue.offer(root.right); } System.out.print(queue.poll().val+" "); levelOrderQueue(queue.peek()); }}优先级队列(堆)
概念
队列是一种先进先出(FIFO)的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队
列时，可能需要优先级高的元素先出队列
要实现上述功能,该数据结构要有两个基本操作,一个是返回最高级优先级对象,一个是添加新的对象,这种数据结构就是优先级队列
优先级队列的模拟实现
JDK1.8中的PriorityQueue底层使用了堆这种数据结构，而堆实际就是在完全二叉树的基础上进行了一些调整
堆的性质
- 堆中的某个结点的值总是不大于或者不小于父结点的值
- 堆总是一棵完全二叉树
概念
如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足：Ki = K2i+2) i = 0，1，2…，则称为 小堆(或大
堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
小根堆: 根结点比左右结点都小,但是左右结点谁更小没有关系,只考虑根结点和左右结点的关系
大根堆: 根结点比左右孩子都大,左右结点的大小无所谓
存储的时候放在数组中
数组中能不能存储一个非完全二叉树?
完全二叉树中,数组存储它的层序遍历结果,如果是存放在一个非完全二叉树中会出现浪费空间的结果
堆的存储方式
在堆的概念中,堆是一颗完全二叉树,因此可以按照层序遍历的规则来进行顺序的存储
注意:对于非完全二叉树,则不适合使用顺序方式进行存储,因为为了能够还原二叉树,空间必须存储空结点,导致空间利用率降低
如何实现代码实现优先级队列,一定要看作大根堆或者小根堆
将元素存储到数组中后。假设i为节点在数组中的下标，则有：
如果i为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i - 1)/2
如果2 * i + 1 小于节点个数，则节点i的左孩子下标为2 * i + 1，否则没有左孩子
如果2 * i + 2 小于节点个数，则节点i的右孩子下标为2 * i + 2，否则没有右孩子
一个普通二叉树转换成一个大根堆或者小根堆,对于大根堆而言,调整过程:
1.对最后一棵子树进行调整
2.然后找到左右结点的最大值和根结点比较,大的话就和根结点的值进行交换
3. 如果得知根结点的下标,那么下一棵子树就是该下标-1
4. 一直调整到0下标这棵树为止
问题:
-
每棵子树调整的时候,结束位置怎么确定?
根据数组长度,如下(之前的结论):
如果2 * i + 1 小于节点个数，则节点i的左孩子下标为2 * i + 1，否则没有左孩子
如果2 * i + 2 小于节点个数，则节点i的右孩子下标为2 * i + 2，否则没有右孩子
根据父结点下标和数组长度判断左右孩子是否存在的方法进行判断,用于向下调整的方法
-
最后一棵子树的根结点下标怎么确实?
已知最后一个结点的下标是数组长度-1,而已知一个结点的下标求父亲结点,就是该下标-1再除以2((index-1)/2=fatherIndex)
堆的创建
import java.util.Arrays;public class Heap { public int[] elements; //堆当中有效的数据个数 public int usedSize; public Heap() { elements = new int[20]; } /** * 初始化数组 */ public void initArray(int[] arr) { for (int i = 0; i = 0 ; i--) { adjustDown(i,usedSize); } } /** * 向下调整 * @param parent * @param len */ private void adjustDown(int parent, int len) { //孩子结点的下标初始化为左孩子的结点的下标 int child = parent*2 +1; //要交换至少你要存在左孩子才能进行交换 //交换之后,child这个变量代表要交换的那个孩子的下标 //如果存在左右孩子的话,就比较哪个孩子的值大 //如果只存在左孩子的话,那么没得选,只能是左孩子下标 //因为是完全二叉树,所以,存在右孩子必然存在左孩子 //但是存在左孩子不一定存在右孩子 while(child //保证右孩子存在,不然可能会导致数组越界 //右孩子存在且比左孩子大,则要更新child变量 //child始终是左右孩子最大的那个下标 if(child+1 child++; } //左右孩子最大值大于父结点的值,数值进行交换 //父结点,孩子结点进行更新,继续向下进行调整 if(elements[child]elements[parent]) { swap(parent,child); parent = child; child = parent*2+1; }else { //如果孩子下标合法,但是父结点比他们最大值还大 //跳出即可,因为下面的子树本来就调整完了,下面 //子树的最大值肯定小于父结点的值,那么父结点 //的值都小于父结点的父亲的值的话,下面没必要进行 //调整了 break; } } } //判断是否满 private boolean isFull() { return usedSize==elements.length; } //扩容 private void enLarger() { elements = Arrays.copyOf(elements,elements.length*2); } private void swap(int parent,int child) { int tmp = elements[parent]; elements[parent] = elements[child]; elements[child] = tmp; } /** * 对于大根堆来说,如果新的数据比父结点的值小,那么就没必要进行向上调整, * 因为父结点的父结点的值一定比父结点大,新的数据比父结点都小,所以一定比 * 父结点的父结点的值小,但是如果新的数据比父结点的值大,就要交换,新的数据在左结点 * 或者右节点都只需要和父结点比较,因为即便新数据在右节点,父结点的左节点一定比 * 父结点小,所以只考虑和父结点的数据进行比较大小即可 * @param val */ public void insertHeap(int val) { if(isFull()) { elements = Arrays.copyOf(elements,elements.length*2); } usedSize++; int child = usedSize-1; int parent = (child-1)/2; elements[child] = val; while (child!=0) { if(elements[parent] swap(parent,child); child = parent; parent = (child-1)/2; }else { break; } } }}
- 计���排序
下一篇：网易官方怎么看服务器?
