二叉树

1.二叉树的理论基础

1.1 二叉树的种类

  • 满二叉树

    • 满二叉树的底部一定是从左到右连续且排满的
    • 节点数量 = $2^k - 1$

  • 完全二叉树：

    • 完全二叉树的底部一定是从左到右连续的

  • 二叉搜索树：

    • 左子树的所有节点都小于中间节点，右子树的所有节点都大于中间节点，且所有子结点也满足该性质
    • 对结构没有要求，只要求节点上的元素有一定顺序

  • 平衡二叉搜索树：

    • 左子树和右子树的高度差的绝对值不能大于1（平衡因子不能大于1）

    • 对所有子节点也满足该性质

      map,set,multimap,multiset底层都是
      红黑树（一种自平衡二叉搜索树）

    所以map和set的底层都是有序的，因为他们的底层都是平衡二叉搜索树(红黑树) ，要按元素值来排序的

    我们要有意识的去了解自己平时所用的语言，用的某些容器，底层实现是什么样的，这样我们才能清晰地了解他们用的元素是不是有序的，时间复杂度是什么，为什么？

1.2 二叉树的存储方式：

  1. 链式存储

    1
    2
    3
    4
    5
    class TreeNode{
      TreeNode* leftchild;
      TreeNode* rightchild;
      int Value;
    };

  2. 线性存储

    | 值 | a | b | c | d | e | f | g |
    | ———— | —— | —— | —— | —— | —— | —— | —— |
    | 数组下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |

    • 左孩子数组下标：$2*i+ 1$ ，例如b的左节点为d(3)
    • 右孩子数组下标：$2*i+2$ ，b的右节点为e(4)

1.3 二叉树遍历：

提到二叉树的遍历，很多人都会想到前序，中序，后序，层数遍历，但是其实，二叉树的遍历是与图论中的深度优先遍历和广度优先遍历是一致的。

  • 深度优先遍历：一般都是以递归的方式实现的，前序中序后序都是通过递归实现的 (前、中、后序遍历)
  • 广度优先遍历：是一层层的去遍历(图论是一圈一圈) (层序遍历)

​ 我们在讲遍历方式的时候，一般会有递归法和迭代法

​ 深度优先搜索一般都是用递归实现、其实用递归实现，也同样可以用栈模拟递归过程，也就是迭代思维，所以二叉树的问题，对于每一种能用递归法解决的问题，都可以用迭代法解决。

1.4 二叉树的定义

参考上方的链式存储