二叉树
树
树：一对多(即父节点对应多个子节点)。
度：父节点对应的子节点总数。
层次:以根节点为1，依次往下递增。
深度：树的最大层次。
森林:树的集合。
Ps:树中的每个节点是不是也可以看做一棵树？
二叉树
二叉树:度为2的树(即左/右子节点)。
分类:满二叉树、完全二叉树、平衡二叉树。
满二叉树
满二叉树很好理解，是一个类似金字塔的结构。
可以这么说，满二叉树的每一层次都不允许有空节点。
完全二叉树
完全二叉树可以分为两部分(最底层和上层(非最底层))。
上层是一个满二叉树。
最底层从左到右中间不允许存在空节点。
平衡二叉树
左/右子树的深度相差不超过1即为平衡二叉树。
为什么需要平衡二叉树？
二叉树通常作用二叉查找树和二叉堆(如堆排序)。
在一些极端情况下，二叉树会退化为链表，导致查询性能退化。
平衡二叉树的意义就是新增节点时，平衡树的结构，使左/右子树的深度接近，优化查询性能。
常用实现:红黑树、AVL、Treap、伸展树、SBT。
二叉树的遍历
先序遍历
根节点 -> 左子树 -> 右子树
1 以A为根节点( => A)
2 遍历左子树 (B)
2.1 以B为根节点( => B)
2.2 遍历左子树 (D)
2.2.1 以D为根节点( => D)
2.3 遍历右子树 (E)
2.3.1 以E为根节点( => E)3 遍历右子树 (C)
3.1 以C为根节点( => C)
3.2 遍历左子树 (F)
3.2.1 以F为根节点( => F)
3.3 遍历右子树 (G)
3.3.1 以G为根节点( => G)
先序遍历: A, B, D, E, C, F, G
PS: 在有序的二叉树中，先序遍历顺可作为二叉树的构造顺序
中序遍历
左子树 -> 根节点 -> 右子树
1 遍历左子树 (B)
1.1 遍历左子树 (D)
1.1.1 以D为根节点( => D)
1.2 以B为根节点( => B)
1.3 遍历右子树 (E)
1.3.1 以E为根节点( => E)2 以A为根节点( => A)
3 遍历右子树 (C)
3.1 遍历左子树 (F)
3.1.1 以F为根节点( => F)
3.2 以C为根节点( => C)
3.3 遍历右子树 (G)
3.3.1 以G为根节点( => G)
中序遍历: D, B, E, A, F, C, G
后序遍历
左子树 -> 右子树 -> 根节点
1 遍历左子树 (B)
1.1 遍历左子树 (D)
1.1.1 以D为根节点( => D)
1.2 遍历右子树 (E)
1.2.1 以E为根节点( => E)
1.3 以B为根节点( => B)2 遍历右子树 (C)
3.1 遍历左子树 (F)
3.1.1 以F为根节点( => F)
3.2 遍历右子树 (G)
3.2.1 以G为根节点( => G)
3.3 以C为根节点( => C)3 以A为根节点( => A)
后序遍历: D, E, B, F, G, C, A
Java实现简单二叉树
树节点
class BinaryTree<T> {
static class TreeNode<T> {
/** 数据 */
T data;
/** 父节点 */
TreeNode<T> parent;
/** 左子树 */
TreeNode<T> left;
/** 右子树 */
TreeNode<T> right;
}
TreeNode<T> root;
}
