二叉树基本分类

二叉树大概分为：

• 完全二叉树：除了最后一层外，其他每一层都被填满，且最后一层的节点从左到右连续地填入
• 满二叉树：除最后一层无任何子节点，每层的所有结点都有两个子结点
• 二叉搜索树/二叉排序树：每个节点的值大于左子树中所有节点的值，且小于右子树中所有节点的值
• 平衡二叉树：任意节点的左子树和右子树的高度差不超过1 如AVL树
• 多路搜素树：允许每个节点有多个子节点，用于高效地处理大量数据，如B树、B+树

#include <bits/stdc++.h>

// 单向链表
struct ListNode{
    int val;
    ListNode* next;
    ListNode(int x): val(x), next(nullptr){}
    ListNode(int x, ListNode* next): val(x), next(next){}
};

// 二叉树的基本结构，在其基础上加条件会衍生各种类型的二叉树
struct TreeNode{
    int val;
    TreeNode *left, *right;
    TreeNode(int x, TreeNode* left, TreeNode*right): val(x), left(left), right(right){}
};

// 红黑树/自平衡二叉搜索树，既是平衡二叉树 也是二叉搜索树
struct RBTreeNode{
    int val;
    bool isBlack;
    RBTreeNode *left, *right, *parent;
    RBTreeNode(int x): val(x), isBlack(true), left(nullptr), right(nullptr), parent(nullptr){}
};