二叉树：每个节点最多含有两个子节点

二叉树的种类

  • 一般的二叉树
  • 满二叉树
  • 完全二叉树

满二叉树

如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。
image.png

完全二叉树

在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^h -1 个节点。
注：完全二叉树可以理解为满二叉树从最底层的最右子节点开始逐个去除一定数量的节点，剩下的就是一棵完全二叉树

image.png

二叉搜索树

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

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

下面这两棵树都是搜索树
image.png

平衡二叉搜索树

平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
如图：
image.png
最后一棵 不是平衡二叉树，因为它的左右两个子树的高度差的绝对值超过了1。
C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树，所以map、set的增删操作时间时间复杂度是logn，而unordered_map、unordered_set，unordered_map、unordered_map底层实现是哈希表。

二叉树的存储方式

  • 链式存储：使用指针
  • 顺序存储：使用数组

链式存储如图：
image.png
顺序存储的方式如图：
image.png
对于顺序存储的来说：
如果父节点的数组下表是i（下标从0开始），那么它的左孩子就是i 2 + 1，右孩子就是 i 2 + 2。

二叉树的遍历方式

  • 深度优先遍历：
    • 前序遍历：根左右
    • 中序遍历：左根右
    • 后序遍历：左右根
  • 广度优先遍历：
    • 层次遍历

image.png
深度优先遍历的实现可以使用递归法或者使用栈的非递归法
广度优先遍历一般使用队列来实现

二叉树的定义

链式存储二叉树的定义方式：

  1. struct TreeNode {
  2.     int val;
  3.     TreeNode *left;
  4.     TreeNode *right;
  5.     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  6. };

二叉树的定义 和链表是差不多的，相对于链表 ，二叉树的节点里多了一个指针， 有两个指针，指向左右孩子.

二叉树的深度和高度

这里强调一波概念：

  • 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
  • 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。

image.png
关于根节点的深度究竟是1 还是 0，不同的地方有不一样的标准，leetcode的题目中都是以节点为一度，即根节点深度是1。但维基百科上定义用边为一度，即根节点的深度是0，我们暂时以leetcode为准（毕竟要在这上面刷题）。

因为求深度可以从上到下去查 所以需要前序遍历（中左右），而高度只能从下到上去查，所以只能后序遍历（左右中）
在104.二叉树的最大深度(opens new window)中，如果真正求取二叉树的最大深度，代码应该写成如下：（前序遍历）

class Solution {
public:
    int result; //记录最大深度
    void getDepth(TreeNode* node, int depth) {
        result = depth > result ? depth : result; // 中

        if (node->left == NULL && node->right == NULL) return ;

        if (node->left) { // 左
            depth++;    // 深度+1
            getDepth(node->left, depth);
            depth--;    // 回溯，深度-1
        }
        if (node->right) { // 右
            depth++;    // 深度+1
            getDepth(node->right, depth);
            depth--;    // 回溯，深度-1
        }
        return ;
    }
    int maxDepth(TreeNode* root) {
        result = 0;
        if (root == 0) return result;
        getDepth(root, 1);
        return result;
    }
};

代码简化：

class Solution {
public:
    int result;
    void getDepth(TreeNode* node, int depth) {
        result = depth > result ? depth : result; // 中
        if (node->left == NULL && node->right == NULL) return ;
        if (node->left) { // 左
            getDepth(node->left, depth + 1);
        }
        if (node->right) { // 右
            getDepth(node->right, depth + 1);
        }
        return ;
    }
    int maxDepth(TreeNode* root) {
        result = 0;
        if (root == 0) return result;
        getDepth(root, 1);
        return result;
    }
};