# struct

**Repository Path**: hwkt/struct

## Basic Information

- **Project Name**: struct
- **Description**: 数据结构
- **Primary Language**: Java
- **License**: Apache-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2020-08-20
- **Last Updated**: 2020-12-19

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# struct

#### 介绍
数据结构

#### 软件架构
软件架构说明

#### 使用说明

1. com.hwk.test -- 斐波那契

2. com.hwk.dynamic.array.ArrayList -- 动态数组
   - 扩容容量 10 -> 15 -> 22 -> 33
   - 缩容 在临界点操作容易造成复杂度震荡，trimToSize方法，扩容和缩容倍数千万不能一致
   - 查找复杂度1，尾部新增复杂度1，下标新增复杂度n
   
3. com.hwk.dynamic.linked.LinkedList 链表
    - 双向链表，根据下标查找可以选择方向，
    - 查找复杂度是n，新增复杂度是1
    - 官方的clear是去除所有连线，目的是help gc和迭代器引用导致不会回收
    - 单向循环链表->尾部指向null变为指向头部

4. com.hwk.stack.Stack 栈
   
    - 用两个栈即可实现浏览器的前进和后退
    
5. 队列
    - 双端队列
    - 循环队列
    
6. 树
    - 基本组成：节点、根结点、父节点、子节点、兄弟节点
    - 节点的度：该节点的子树个数
    - 树的度：所有节点度的最大值
    - 层数：根结点在第一层
    - 节点的深度：从更节点到当前节点的唯一路径的节点总数 从上至下
    - 节点的高度：从当前节点到最远的叶子节点的路径上的节点总数 从下至上
    
    1. 二叉树 Binary Tree
        - 每个节点度最大为2，即一个节点最多有两个子节点
        - 严格区分顺序
        - 只有一个根结点，也可以称为二叉树
        - 第i层，最多有2^(i-1)个节点，整个树最多有2^i-1个节点
        - n(0) = n(2)+1
        
        1. 真二叉树
            所有节点的度要么为0要么为2
            
        2. 满二叉树
            所有节点的度要么为0要么为2，所有叶子节点必须在最后一层，满二叉树一定是真二叉树
            
        3. 完全二叉树
            叶子结点只会在最后两层
            
            ![image-20200822185006504](./src/main/resources/image-20200822185006504.png)