二叉树

二叉树

树的结点（node）：包含一个数据元素及若干指向子树的分支；

孩子结点（child
node）：结点的子树的根称为该结点的孩子；

双亲结点：B
结点是A 结点的孩子，则A结点是B 结点的双亲；

兄弟结点：同一双亲的孩子结点；
堂兄结点：同一层上结点；

祖先结点:
从根到该结点的所经分支上的所有结点

子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙

结点层：根结点的层定义为1；根的孩子为第二层结点，依此类推；

树的深度：树中最大的结点层

结点的度：结点子树的个数

树的度：
树中最大的结点度。

叶子结点：也叫终端结点，是度为 0
的结点；

分枝结点：度不为0的结点；

有序树：子树有序的树，如：家族树；

无序树：不考虑子树的顺序；

满二叉树

​

1. 叶子只能出现在最下一层。
2. 非叶子结点度一定是2.
3. 在同样深度的二叉树中，满二叉树的结点个数最多，叶子树最多。

完全二叉树

1. 叶子结点只能出现在最下一层（满二叉树继承而来）
2. 最下层叶子结点一定集中在左 部连续位置。
3. 倒数第二层，如有叶子节点，一定出现在右部连续位置。
4. 同样结点树的二叉树，完全二叉树的深度最小（满二叉树也是对的）。

BST

二叉查找树 ，树上每个结点都满足：

其左子树上所有结点数据均小于根结点；

右子树所有结点数据域均大于根结点数据域。

ALV

平衡二叉树，在二叉平衡查找树基础上增加了 “平衡”

左子树和右子树的高度绝对差不超过 1

右旋操作

左旋操作

LR型

RL型

遍历

前序遍历

先访问根结点，再先序遍历左子树，最后再先序遍历右子树即根—左—右

后序遍历

先后序遍历左子树，然后再后序遍历右子树，最后再访问根结点即左—右—根

中序遍历

左—根—右

B
D C A E H G K F

还原二叉树知道前序（第一个）或后序（最后一个） 确定根节点，必须知道中序才能确定左子树或右子树