# java数据结构

> 来源：梦飞idc云平台 | 原文：https://www.mfisp.com/22057.html | 发布：2023-07-14 | 更新：2023-07-14 | 分类：建站教程

JCF（java集合框架）

 

接口interfaces

 

a.Collection接口说明

 

b.Map接口说明

 

2.类class

 

栈和队列：

 

都是线性表操作的子类

 

1.栈(Stack)LIFO:

 

a.顺序栈（基于数组）（数组末尾添加和删除元素即可）

 

b.链式栈（基于链表）

 

核心操作:push pop peek

 

2.队列(Queue)FIFO：

 

a.链式队列（基于链表）

 

b.顺序队列——循环队列

 

核心操作:offer poll peek

 

3.双端队列（Deque）:LinkedList

 

二叉树

 

1.前身：树：度 叶子结点 父节点 子节点 层次 高度深度 分支节点

 

树的表示形式：

 

Class Node{

 

Int value;

 

Node firstChild

 

Node nextBrother

 

}

 

特点：每个节点最多有两颗子树，即二叉树不存在度大于2的结点

 

二叉树的子树有左右之分，其子树的次序不能颠倒，因此二叉树是有序树

 

特殊的二叉树{ 满二叉树 完全二叉树}  
 性质：1.第i层上最多有2^（i-1）

 

2.深度K最大的结点数2^k-1

 

3.n0=n2+1;

 

4.n个结点完全二叉树深度为log2(n+1)

 

5.存储：顺序存储

 

链式存储：a。孩子表示法

 

b.孩子双亲表示法

 

6.遍历{前序 中序 后序}

 

7. 基本操作{preorderTraversal

 

InOrderTraversal

 

PostOrderTraversal

 

GetSize

 

GetLeafSize

 

getLevelSize}  
堆（heap）

 

优先级队列——入队一样，出队不一样，按照优先级出队

 

普通队列：FIFO

 

概念：堆是一颗完全二叉树（结构上）  
 从节点值的要求

 

最大堆：根节点的值一定不小于左右子树  
 最小堆：根节点的值一定不大于左右子树

 

堆的实现：（基本都是基于二叉树——二叉堆）

 

***最大堆—》根节点>=左右子树

 

层次和节点的大小没有任何关系***

 

相同数据可以构建成多种类型的堆（最大&最小）

 

堆的表示——(数组)

 

堆的三大核心操作 //add(val)向堆中添加元素 siftUp(元素上浮)

 

//ectractMax():取出最大堆 siftDown(元素下沉)

 

//heapify 将任意一个数组堆化 add +siftDown

 

****原地堆排序*** O（nlogn）

 

将任意数组heapify（siftDown） 调整为最大堆  
 调整最大值与数组末尾的位置（siftDown 与之前不同：不考虑已交换元素）

---
本页由 梦飞idc云平台（https://www.mfisp.com）提供。站点导航见 https://www.mfisp.com/llms.txt