二叉树的结构
二叉树是树状结构，包含节点(🟠)和分支（左分支/ ，右分支 \）。节点的左分支部分为节点的左子树，节点的右分支部分为节点的右子树
每个树只有一个根节点，每个节点的分叉都小于或等于两支，这棵树是自上而下的，根节点在最上方。
没有任何分支的节点就是叶子节点。
D,E,F,G为叶子节点。
A为整棵树的根节点，左框为A的左子树，右框为A的右子树，A为B和C的父节点，B和C为A的子节点。B为A的左孩子，C为A的右孩子。B和C是兄弟节点，F是B的左侄节点，G是B的右侄节点，B是F和G的叔父节点。
所有的节点定义都是相对于树来说的，也就是说，只针对于A的左子树来说，B为这棵树的根节点，左框为B的左子树，右框为B的右子树，B为D和E的父节点，D和E为A的子节点。D为B的左孩子，E为B的右孩子。
二叉树的分类
1.结构上分类：
- 满二叉树(完美二叉树)：
二叉树的叶子节点只能在最后一层，且其他层的节点都有两个分支。
- 完全二叉树：
跟满二叉树的联系，它是对应的满二叉树在最后一层从右向左依次删除节点产生的
2.功能上分类：
- 二叉搜索树(二叉排序树，二叉查找树):
特殊的二叉树，每个节点的左孩子的值都小于该节点，右孩子的值都大于该节点。
-
平衡二叉树(AVL树)
特殊的二叉搜索树，每个节点的左右子树的高度差绝对值小于等于1
-
红黑树
二叉树的遍历
- 前序遍历：先遍历根节点，然后左子树，最后右子树。
- 中序遍历：先遍历左子树，然后根节点，最后右子树。
- 后序遍历：先遍历左子树，然后右子树，最后根节点。
note:要谨记二叉树左子树和右子树的定义，都是相对于根节点来说的。这里的遍历规则是说根节点的左子树也是这样的遍历规则，对于根节点的左子树来说，抛开根节点，是一个独立的树。
为什么要有前中后序遍历呢？
- 前序遍历可以用于复制或打印二叉树的结构，因为它可以保持二叉树的形状不变。前序遍历也可以用于实现表达式树，因为它可以按照运算符的优先级来计算表达式的值。
- 中序遍历可以用于对二叉搜索树进行排序，因为它可以按照从小到大的顺序输出二叉搜索树中的元素。中序遍历也可以用于实现中缀表达式，因为它可以按照数学上的习惯来输出表达式。
- 后序遍历可以用于释放或删除二叉树的内存空间，因为它可以保证在删除一个节点之前，已经删除了它的所有子节点。后序遍历也可以用于实现后缀表达式，因为它可以按照逆波兰记法来输出表达式
二叉树的数据结构
//二叉树结点的定义：
#define ElementType int
struct TreeNode {
ElementType value;
TreeNode* left;
TreeNode* right;
};
//二叉树的定义：
struct Tree {
TreeNode* root;
}
note:因为二叉树用法的不同，数据结构形式也会发生改变，比如多个父指针(需要经常访问父指针)