总结

一、复杂度

1.1、时间复杂度
1.2、空间复杂度

二、线性数据结构

2.1、动态数组(ArrayList)
2.2、链表(LinkedList)
✓ 单向链表
✓ 双向链表
✓ 循环链表
✓ 静态链表
2.3、栈(Stack)
2.4、队列(Queue)
✓ 双端队列(Deque)
✓ 循环队列
2.5、哈希表(HashTable)

三、树形数据结构

3.1、二叉树(BinaryTree)、二叉搜索树(BinarySearchTree、BST)
3.2、平衡二叉搜索树(BalancedBinarySearchTree、BBST)
✓ AVL树(AVLTree)、红黑树(RebBlackTree)
3.3、B树(B-Tree)
3.4、集合(TreeSet)、映射(TreeMap)
3.5、哈夫曼树
3.6、Trie

四、线性+树形数据结构

4.1、集合(HashSet)
4.2、映射(HashMap、LinkedHashMap)
4.3、二叉堆(BinaryHeap)
4.4、优先级队列(PriorityQueue)

补充

zig、zag

◼ 有些教程里面
把右旋转叫做zig，旋转之后的状态叫做zigged
把左旋转叫做zag，旋转之后的状态叫做zagged

满二叉树、完全二叉树定义

四则运算

◼ 四则运算的表达式可以分为3种
1、前缀表达式(prefix expression)，又称为波兰表达式
2、中缀表达式(infix expression)
3、后缀表达式(postfix expression)，又称为逆波兰表达式

表达式树

◼ 如果将表达式的操作数作为叶子节点，运算符作为父节点(假设只是四则运算)
这些节点刚好可以组成一棵二叉树
比如表达式:A / B + C * D – E

◼ 如果对这棵二叉树进行遍历

• 前序遍历
  – + / A B * C D E
  刚好就是前缀表达式(波兰表达式)

• 中序遍历
  A / B + C * D – E
  刚好就是中缀表达式

• 后序遍历
  A B / C D * + E –
  刚好就是后缀表达式(逆波兰表达式)

二叉树的非递归遍历

前序遍历 – 非递归

◼ 利用栈实现

1. 设置node=root
2. 循环执行以下操作
   如果 node != null
   ✓对node 进行访问
   ✓将node.right 入栈
   ✓ 设置 node = node.left
   如果 node == null
   ✓ 如果栈为空，结束遍历
   ✓ 如果栈不为空，弹出栈顶元素并赋值给 node

◼ 利用栈实现

1. 将root入栈
2. 循环执行以下操作，直到栈为空
   弹出栈顶节点 top，进行访问
   将 top.right 入栈
   将 top.left 入栈

// 非递归前序遍历
public void preorder(Visitor<E> visitor) {
    if (visitor == null || root == null) return;
    Node<E> node = root;
    Stack<Node<E>> stack = new Stack<>();// 会开辟空间
    while (true) {
        if (node != null) {
            // 访问node节点
            if (visitor.visit(node.element)) return;
            // 将右子节点入栈
            if (node.right != null) {
                stack.push(node.right);
            }
            // 向左走
            node = node.left;
        } else if (stack.isEmpty()) {
            return;
        } else {
            // 处理右边
            node = stack.pop();
        }
    }
}

中序遍历 – 非递归

◼ 利用栈实现

设置node=root
循环执行以下操作
如果 node != null
✓将node 入栈
✓ 设置 node = node.left
如果 node == null
✓ 如果栈为空，结束遍历
✓ 如果栈不为空，弹出栈顶元素并赋值给 node ➢对node 进行访问
➢设置 node = node.right

// 非递归中序遍历
public void inorder(Visitor<E> visitor) {
    if (visitor == null || root == null) return;
    Node<E> node = root;
    Stack<Node<E>> stack = new Stack<>();
    while (true) {
        if (node != null) {
            stack.push(node);
            // 向左走
            node = node.left;
        } else if (stack.isEmpty()) {
            return;
        } else {
            node = stack.pop();
            // 访问node节点
            if (visitor.visit(node.element)) return;
            // 让右节点进行中序遍历
            node = node.right;
        }
    }
}

后序遍历 - 非递归

// 非递归后序遍历
public void postorder(Visitor<E> visitor) {
    if (visitor == null || root == null) return;
    // 记录上一次弹出访问的节点
    Node<E> prev = null;
    Stack<Node<E>> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        Node<E> top = stack.peek();
        if (top.isLeaf() || (prev != null && prev.parent == top)) {
            prev = stack.pop();
            // 访问节点
            if (visitor.visit(prev.element)) return;
        } else {
            if (top.right != null) {
                stack.push(top.right);
            }
            if (top.left != null) {
                stack.push(top.left);
            }
        }
    }
}