二叉树
二叉树基本知识 -------------------------------------------------------------------------- 满二叉树： 如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上， 则这棵二叉树为满二叉树。 除了叶子节点外，其他节点都有两个子节点 且 每一层都是铺满的； 深度为k（k从1开始），有2^k-1个节点的二叉树。 完全二叉树 完全二叉树的定义如下： 在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值， 并且最下面一层的节点都集中在该层最左边的若干位置。 若最底层为第 h 层（h从根节点开始，从1开始计数），则该层包含 1~ 2^(h-1) 个节点。 二叉搜索树
前面介绍的树，都没有数值的，而二叉搜索树是有数值的了，二叉搜索树是一个有序树
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树
平衡二叉搜索树 平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质： 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1， 并且左右两个子树都是一棵平衡二叉树
平衡二叉搜索树是指一种特殊的二叉搜索树，
其中任何节点的左子树和右子树的高度差不超过1，确保了树的平衡性。
这种树的发明者是 G. M. Adelson-Velsky 和 Evgenii Landis，
因此也被称为 AVL 树。在 AVL 树中，查找、插入和删除操作的时间复杂度都是 O(log n)，
这是因为树的高度始终保持在对数级别。
为了维持这种平衡，AVL 树在插入或删除节点后可能需要进行树旋转以重新平衡。
平衡二叉搜索树的每个节点都有一个平衡因子，
即左子树高度与右子树高度之差，平衡因子的值只能是 -1、0 或 1。
在原文中，虽然没有直接提及平衡二叉搜索树，但根据上下文，
可以理解为一种高度平衡的二叉搜索树，与满二叉树和完全二叉树是不同的概念。
|
二叉树可以链式存储，也可以顺序存储
那么链式存储方式就用指针， 顺序存储的方式就是用数组。
顾名思义就是顺序存储的元素在内存是连续分布的，而链式存储
则是通过指针把分布在各个地址的节点串联一起。
链式存储
每个节点有三个元素：
数据
左指针
右指针
其中叶子节点的左指针，右指针为空
顺序存储
用数组存储元素，父子节点之间的位置关系，对应数组的索引关系
如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。
|
二叉树主要有两种遍历方式： 深度优先遍历：先往深走，遇到叶子节点再往回走。 广度优先遍历：一层一层的去遍历。 这两种遍历是 图论 中最基本的两种遍历方式 那么从深度优先遍历和广度优先遍历进一步拓展，才有如下遍历方式： 深度优先遍历 前序遍历（递归法，迭代法） 中序遍历（递归法，迭代法） 后序遍历（递归法，迭代法） 前序遍历是指在二叉树的深度优先遍历中，按照“根节点-左子树-右子树”的顺序访问每个节点的过程。 在前序遍历中，首先访问根节点，然后递归地进行左子树的前序遍历，最后递归地进行右子树的前序遍历。 这种遍历方式可以采用递归方法或迭代方法实现，其中迭代方法通常使用栈来辅助实现。 前序遍历是深度优先遍历的一种，与中序遍历和后序遍历共同构成了深度优先遍历的三种主要遍历顺序。 在前序遍历中，中间节点（即根节点）的位置在访问顺序的最前面，这也是“前序”名称的由来。 中序遍历是指在二叉树的深度优先遍历中，按照左子树-根节点-右子树的顺序访问每个节点的过程。 在中序遍历中，首先遍历当前节点的左子树，然后访问当前节点，最后遍历当前节点的右子树。 这种遍历方式可以确保在访问父节点之前，其所有左子树的节点都被访问； 在访问父节点之后，其所有右子树的节点才会被访问。 中序遍历可以通过递归或迭代的方法实现，其中迭代方法通常使用栈来辅助实现。 
前序遍历：中左右，4312567 中序遍历：左中右，1234657 后序遍历：左右中，1236754 广度优先遍历：层次遍历（迭代法） 前序遍历：A B D E G H C F
A
/ \
B C
/ \ \
D E F
/ \
G H
在这个例子中，二叉树的根节点是A，深度为4（从根节点到最远叶子节点的最长路径上的节点数）。
前序遍历这个二叉树的步骤是：
访问根节点A。
递归地前序遍历左子树（以B为根）。
访问B。
递归地前序遍历B的左子树（以D为根）。
访问D（此时D是叶子节点，没有子树）。
递归地前序遍历B的右子树（以E为根）。
访问E。
递归地前序遍历E的左子树（以G为根）。
访问G（此时G是叶子节点，没有子树）。
递归地前序遍历E的右子树（以H为根）。
访问H（此时H是叶子节点，没有子树）。
递归地前序遍历右子树（以C为根）。
访问C。
递归地前序遍历C的右子树（以F为根）。
访问F（此时F是叶子节点，没有子树）。
因此，前序遍历的结果序列是：A B D E G H C F。
这个过程展示了如何递归地应用前序遍历算法来访问二叉树中的所有节点。
前序遍历：A B D I J E G H C F
A
/ \
B C
/ \ \
D E F
/ | | \
I J G H
访问根节点A。
递归地前序遍历左子树（以B为根）。
访问B。
递归地前序遍历B的左子树（以D为根）。
访问D。
递归地前序遍历D的左子树（以I为根）。
访问I（此时I是叶子节点，没有子树）。
递归地前序遍历D的右子树（以J为根）。
访问J（此时J是叶子节点，没有子树）。
递归地前序遍历B的右子树（以E为根）。
访问E。
递归地前序遍历E的左子树（以G为根）。
访问G（此时G是叶子节点，没有子树）。
递归地前序遍历E的右子树（以H为根）。
访问H（此时H是叶子节点，没有子树）。
递归地前序遍历右子树（以C为根）。
访问C。
递归地前序遍历C的右子树（以F为根）。
访问F（此时F是叶子节点，没有子树）。
因此，根据这个新的二叉树结构，前序遍历的结果序列是：A B D I J E G H C F。
|
|
|
|
|
堆（Heap）
堆（Heap）是一种特殊的完全二叉树结构，它满足以下性质： 每个节点的值都不大于或不小于其子节点的值， 具体取决于堆的类型——最大堆（Max Heap）或最小堆（Min Heap）。 在最大堆中，父节点的值总是大于或等于任何一个子节点的值； 在最小堆中，父节点的值总是小于或等于任何一个子节点的值。
|
|
|
|
|
|
|
|
|
参考