数据结构之总结与补充

封面画师：ツチヤ     封面ID：79168502

本文参考视频：小马哥教育(SEEMYGO) 2019年 恋上数据结构与算法（第一季）

源码仓库：mofan212/data-structure-and-algorithm (github.com)

辅助学习网址：数据结构和算法动态可视化

1. 完结总结

思维导图

2. 定义补充

zig 与 zag

在有些教程中：

把 右 旋转叫做 zig，旋转之后的状态叫做 zigged

把 左 旋转叫做 zag，旋转之后的状态叫做 zagged

两者合在一起又能组成一个新单词 zigzag，意为之字形的、Z 字形的。

满二叉树与完全二叉树

满二叉树：最后一层节点的度都为 0，其他节点的度都为 2（之前的定义也是对的）。

完全二叉树：对节点从上至下、左至右开始编号，其所有编号都能与相同高度的满二叉树中的编号对应。

下图给出的二叉树就不是完全二叉树，因为相同高度的满二叉树中 K位置 的编号应该是 12 ，而不是 11 。

3. 四则运算与表达式树

四则运算

四则运算的表达式可以分为3种：

1、前缀表达式（prefix expression），又称为波兰表达式

2、中缀表达式（infix expression）

3、后缀表达式（postfix expression），又称为逆波兰表达式

前缀表达式	中缀表达式	后缀表达式
+ 1 2	1 + 2	1 2 +
+ 2 * 3 4	2 + 3 * 4	2 3 4 * +
+ 9 * - 4 1 2	9 + (4 - 1) * 2	9 4 1 - 2 * +

中缀表达式与平时计算习惯一样，不再赘述。

对于 前缀表达式： 从右向左，获取一个运算符，然后使用这个运算符对其右边的两个数据进行运算，计算出运算结果后，将结果放到这个运算符的位置，删除进行运算后的数据与运算符；重复这个操作，直到表达式中的数据全部计算完。

对于 后缀表达式：从左向右，获取一个运算符，然后使用这个运算符对其左边的两个数据进行运算，计算出运算结果后，将结果放到这个运算符的位置，删除进行运算后的数据与运算符；重复这个操作，直到表达式中的数据全部计算完。

PS：以上操作为个人理解，如果存在错误，请联系博主修改！🙏

表达式树

如果将表达式的操作数作为 叶子节点，运算符作为 父节点 （假设只是四则运算），那么这些节点恰好可以组成一棵二叉树。

比如表达式： A / B + C * D - E

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

前序遍历： - + / A B * C D E ，得到的结果就是 前缀 表达式（波兰表达式）

中序遍历： A / B + C * D - E ，得到的结果就是 中缀 表达式

后序遍历： A B / C D * + E - ，得到的结果就是 后缀 表达式（逆波兰表达式）

4. 非递归遍历二叉树

在最开始编写遍历二叉树的方法时，前序、中序和后序遍历都用的递归进行编写：

// 前序
public void preorder(Visitor<E> visitor) {
    if (visitor == null) return;
    preorder(root, visitor);
}

private void preorder(Node<E> node, Visitor<E> visitor) {
    // 判断停止递归 并且 也可以判断停止打印
    if (node == null || visitor.stop) return;
    visitor.stop = visitor.visit(node.element);
    preorder(node.left, visitor);
    preorder(node.right, visitor);
}

// 中序
public void inorder(Visitor<E> visitor) {
    if (visitor == null) return;
    inorder(root, visitor);
}

private void inorder(Node<E> node, Visitor<E> visitor) {
    // 判断停止递归
    if (node == null || visitor.stop) return;
    inorder(node.left, visitor);
    // 判断停止打印
    if (visitor.stop) return;
    visitor.stop = visitor.visit(node.element);
    inorder(node.right, visitor);
}

// 后序
public void postorder(Visitor<E> visitor) {
    if (visitor == null) return;
    postorder(root, visitor);
}

private void postorder(Node<E> node, Visitor<E> visitor) {
    // 判断停止递归
    if (node == null || visitor.stop) return;
    postorder(node.left, visitor);
    postorder(node.right, visitor);
    // 如果上一步执行完后，visitor恰好为true，应该也不打印
    // 判断停止打印
    if (visitor.stop) return;
    visitor.stop = visitor.visit(node.element);
}

虽然使用递归编写很简单，但是也存在一些问题，每调用一次函数都要开辟一段栈空间（栈帧），简单来说就是会多消耗一些函数空间。所以应当想方设法减少函数调用，可以考虑能不能使用非递归来遍历二叉树。

4.1 前序遍历

假设现在有这样一棵二叉树：

对一棵二叉树进行前序遍历时，需要先遍历根节点，然后遍历左子节点，最后遍历右子节点。对上图给出的二叉树来说，从根节点出发，一路向左找，访问最后一个左子节点，等到左子节点都访问完了，然后又往回访问右子节点。

还需要注意一点，当访问根节点时，就可以拿到其右子节点，但是并没有立马访问。同样的，对于节点 4、2、1来说也是可以拿到其右子节点，也没有立马访问。除此之外还发现，最先能拿到的右子节点是最后访问的，最后能拿到的右子节点却是最先访问的。

根据前面的分析，可以使用 栈 来编写非递归前序遍历二叉树，这个栈里存储了所有的右子节点。

操作步骤

非递归前序遍历二叉树步骤如下：

1、获取根节点，并将根节点赋值给 node

2、初始化一个栈

3、执行一个死循环，在特定条件下退出循环，结束遍历

4、node 不为空时，执行以下操作：

• 访问（遍历） node 节点，如果 node 的右子节点不为 null，将右子节点入栈

• 访问（遍历）完 node 节点后，向左遍历，将 node 的左子节点赋值给 node

5、node 为空时，执行以下操作：

• 如果栈为空栈，退出循环，直接 return 结束遍历

• 如果栈不为空时，弹出栈顶元素，并将栈顶元素赋值给 node

6、重复 4、5 步骤，直到结束遍历

代码实现

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 为空，栈不为空
            // 处理右边
            node = stack.pop();
        }
    }
}

LeetCode 习题

144. 二叉树的前序遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        if (root == null) {
            return list;
        }
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            list.add(pop.val);
            if (pop.right != null) {
                stack.push(pop.right);
            }
            if (pop.left != null) {
                stack.push(pop.left);
            }
        }
        return list;
    }
}

4.2 中序遍历

假设现在有这样一棵二叉树：

对一棵二叉树进行中序遍历时，需要先遍历左子节点，然后遍历根节点，最后遍历右子节点。对于上图给出的二叉树来说，需要从根节点出发，但是并不进行访问，一路向左找，找到最后一个左子节点时，访问这个节点，然后向上遍历，访问这个节点的父节点、访问这个节点的兄弟节点（右节点），一路向上，直到遍历完。

从根节点出发，一路向左找，但都没有进行访问，直到最后一个左子节点时才开始访问，然后一路向上遍历。

根据前面的分析，可以使用 栈 来编写非递归中序遍历二叉树，那这个栈中存储些什么呢？☺️

存储根节点和右子节点，因为根节点和右子节点都属于先进行了遍历但没访问的节点？😳

其实只需要存储根节点（父节点）就可以了，因为有了根节点（父节点），获取这个根节点（父节点）的右子节点还不容易吗？😏

操作步骤

非递归中序遍历二叉树步骤如下：

1、获取根节点，并将根节点赋值给 node

2、初始化一个栈

3、执行一个死循环，在特定条件下退出循环，结束遍历

4、node 不为空时，执行以下操作：

• 将 node 入栈
• 向左寻找 node 的左子节点，将 node 的左子节点赋值给 node

5、node 为空时，执行以下操作：

• 如果栈为空栈了，退出循环，直接 return 结束遍历
• 如果栈不为空，弹出栈顶元素，并将栈顶元素赋值给 node，遍历 node
  • 遍历完 node 后，让 node 的右子节点进行中序遍历，将 node 的右子节点赋值给 node

6、重复 4、5 步骤，直到结束遍历

代码实现

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;
      }
   }
}

LeetCode 习题

94. 二叉树的中序遍历

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        if (root == null) {
            return list;
        }
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                TreeNode pop = stack.pop();
                list.add(pop.val);
                cur = pop.right;
            }
        }
        return list;
    }
}

4.3 后序遍历

假设现在有这样一棵二叉树：

在前面编写前序遍历和中序遍历时，发现这两种遍历方式很类似，但是对于后序遍历来说，就存在着大不一样了。

对一棵二叉树进行后序遍历时，需要先遍历左子节点，然后遍历右子节点，最后遍历根节点。对于上图给出的二叉树来说，需要从根节点出发，但也不进行访问，一路向左找，找到最后一个左子节点时，访问这个节点，然后访问这个节点的兄弟节点（右节点）、访问这个节点的父节点，一路向上，直到遍历完。

从根节点出发，一路向左找，但是也没有进行访问遍历，直到最后一个左子节点才开始访问，然后一路向上遍历。

根据前面的分析，也可以使用 栈 来编写非递归后序遍历二叉树，那问题又来了，栈里面存储些什么呢？😬

在前序遍历中，栈内存储的是右子节点；在中序遍历中，栈内存储的是根节点（父节点）。

根据规则，后序遍历中存储左子节点？

在想啥呢？搁着找规律呢？😡

后序遍历与中序遍历一样，都是从根节点出发，然后一路向下找到最后一个左子节点访问。只不过，后序遍历是先访问其兄弟节点，再访问父节点，然后一路向上，这么说或许没有“ 感觉 ”。

对于栈内元素存储可以这么做：最开始的时候，访问了根节点，然后就将根节点入栈，再然后依次将其右子节点、左子节点入栈，这时栈顶元素是根节点的左子节点。如果这个二叉树只有三个节点，并打算进行后序遍历时，出栈顺序恰好就是后序遍历的顺序。只不过只有三个节点属于特殊情况，在一般情况下将左子节点入栈后，需要“看一下 ”（只是“ 看一下 ”，没有出栈哦 😉）栈顶元素有没有子节点，如果有，又按照右子节点、左子节点的顺序入栈，重复以上操作，直到栈顶元素没有子节点。最后，只需要将栈内元素依次出栈，得到的结果就是后序遍历的结果。

操作步骤

非递归后序遍历二叉树步骤如下：

1、创建一个局部变量 prev，表示上一次弹出访问的节点。（如果不记录这个节点，对于给出的二叉树中，后序遍历节点 2 时就会发生错误）

2、初始化一个栈，并让根节点入栈

3、执行一个循环，判定条件是栈不为空栈时

4、获取栈顶元素，记为 top

5、如果 top 是叶子节点，或者 prev 不为空并且 prev 的父节点是 top 时，弹出栈顶元素，并将其赋值给 prev，然后对 prev 进行访问

6、不满足步骤 5 的情况时：

• 如果 top 的右子节点不为空，将右子节点入栈
• 如果 top 的左子节点不为空，将左子节点入栈

7、重复步骤 4、5、6，直到判定失败结束遍历

代码实现

非递归后序遍历代码如下：

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);
         }
      }
   }
}

LeetCode 习题

145. 二叉树的后序遍历

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
         List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            list.add(pop.val);
            if (pop.left != null) {
                stack.push(pop.left);
            }
            if (pop.right != null) {
                stack.push(pop.right);
            }
        }
        Collections.reverse(list);
        return list;
    }
}

4.4 另一种前序遍历

对于前序遍历，除了最开始说的那种方法外，还有另外一种方式：

1、将根节点入栈

2、循环执行以下操作，指导栈为空：

• 弹出栈顶节点 top，进行访问
• 如果 top 存在右子节点，将其右子节点入栈
• 如果 top 存在左子节点，将其左子节点入栈

代码实现

public void preorder2(Visitor<E> visitor) {
   if (visitor == null || root == null) return;
   Stack<Node<E>> stack = new Stack<>();
   stack.push(root);
   while (!stack.isEmpty()) {
      Node<E> node = stack.pop();
      // 访问node节点
      if (visitor.visit(node.element)) return;
      if (node.right != null) {
         stack.push(node.right);
      }
      if (node.left != null) {
         stack.push(node.left);
      }
   }
}

这种前序遍历和层序遍历很相似，只不过一个使用了栈，一个使用了队列，一个先入栈右子节点，一个先入队左子节点。

层序遍历代码如下：

public void levelOrder(Visitor<E> visitor) {
   if (root == null || visitor == null) return;
   
   Queue<Node<E>> queue = new LinkedList<>();
   queue.offer(root);
   
   while (!queue.isEmpty()) {
      Node<E> node = queue.poll();
      if (visitor.visit(node.element)) return;
      
      if (node.left != null) {
         queue.offer(node.left);
      }
      
      if (node.right != null) {
         queue.offer(node.right);
      }
   }
}

---

恋上数据结构与算法第一季完！  🎉 

感谢小码哥！  🎊