java - 二叉树

    本文主要是记录在学习 Java - 二叉树 过程中的一些知识点备忘！

一般二叉树、完全二叉树、满二叉树、线索二叉树、霍夫曼树、二叉排序树、平衡二叉树、红黑树、B 树

1、节点

节点是数据结构中的基础概念，是构成复杂数据结构的基本组成单位

2、树

树 Tree 是 n(>=0)个节点的有限集；n=0 时称为空树；在任意一棵非空树中：

• 有且仅有一个特定的称为根 Root 的节点
• 当 n>1 时，其余节点可分为 m(>0)个互不相交的有限集 T1、T2、……、Tn,其中每一个集合本身又是一棵树，并且称为根的子树

此外，树的定义还需要强调以下两点：

• n>0 时根节点是唯一的，不可能存在多个根节点，数据结构中的树只能有一个根节点
• m>0 时，子树的个数没有限制，但它们一定是互不相交的

树中节点的度：节点拥有的子树数目称为节点的度

树中节点关系：节点子树的根节点为该节点的孩子节点，相应地该节点称为孩子节点的双亲节点

同一个双亲节点的孩子节点之间互称兄弟节点

树中节点层次：从根开始定义起，根为第一层，根的孩子为第二层，以此类推

树的深度：树中节点的最大层次数称为树的深度或高度

3、二叉树