【刷题日记】二叉树-二叉树理论基础

二叉树的种类

满二叉树

完全二叉树

优先级队列其实是一个堆，堆就是一棵完全二叉树，同时保证父子节点的顺序关系。

二叉搜索树

二叉搜索树是有数值的，二叉搜索树是一个有序树。

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 它的左、右子树也分别为二叉排序树

平衡二叉搜索树（AVL 树）

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

C++ 中 map、set、multimap、multiset 的底层实现都是平衡二叉搜索树，所以 map、set 的增删操作时间时间复杂度是 O(logn)。

unordered_map、unordered_set 底层实现是哈希表。

二叉树的存储

链式存储

类似链表

顺序存储

数组存储

二叉树的遍历

二叉树主要有两种遍历方式：

• 深度优先遍历：先往深走，遇到叶子节点再往回走。

• 广度优先遍历：一层一层的去遍历。

这两种遍历是图论中最基本的两种遍历方式。

前中后序遍历的逻辑其实都是可以借助栈使用递归的方式来实现的。

广度优先遍历的实现一般使用队列来实现，这也是队列先进先出的特点所决定的，因为需要先进先出的结构，才能一层一层的来遍历二叉树。

深度优先遍历

• 前序遍历（递归法，迭代法）：中左右

• 中序遍历（递归法，迭代法）：左中右

• 后序遍历（递归法，迭代法）：左右中

广度优先遍历

层次遍历（迭代法）

二叉树的链式定义

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};