实际的结构

链表

单向链表

由以下两个部分组成

  1. value
  2. 指向下一个节点的指针
    简单的java程序表示为：

双向链表

由以下三个部分组成

  1. value
  2. 指向下一个节点的指针
  3. 指向上一个节点的指针

简单的java程序表示为：

逻辑概念的结构

栈Stack

数据先进后出

队列Queue

数据先进先出

实现栈和队列的方法

  1. 双向链表
    1. 实现一个从头部存取和尾部存取双向链表的类即可
  2. 数组
    1. 前提限定长度的栈和队列（不涉及动态数组）
      1. 栈很好实现，维护一个当前位置的index。加值取值加减即可
      2. 队列需要循环利用这块内存空间
        1. putIndex,popIndex,size,limit
        2. 定义了上面四个变量，size小于limit可以一直加，size大于0可以一直取，nextIndex>limit时候回到0.

树

二叉树


二叉树的先序遍历

对于任何子树的处理流程

  1. 头
  2. 左
  3. 右
    1245367

二叉树的中序遍历

对于任何子树的处理流程

  1. 左
  2. 头
  3. 右
    4251637

二叉树的后序遍历

对于任何子树的处理流程

  1. 左
  2. 右
  3. 头
    4526731

递归实现遍历二叉树

非递归实现

压栈，弹出
这是后序遍历，前序遍历，先右后左且pop直接打印

中序遍历

BST（二叉查找树）

每个节点的值大于其任意左侧子节点的值，小于其任意右节点的值。

AVL(AVL树)平衡树

AVL树中任何节点的两个子树的高度最大差别为1。

红黑树（自平衡的二叉查找树）

1.结点是红色或黑色。
2.根结点是黑色。
3.每个叶子结点都是黑色的空结点（NIL结点）。
4 每个红色结点的两个子结点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色结点)
5.从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。

旋转和变色维持平衡