树:
概念:
由n个节点组成的有限集,有一个根节点;其他节点只有一个前驱节点,但可以有多个后继节点。(一对多)
叶子节点(终端结点):只有前驱结点没有后继结点
非叶子节点(分支节点):既有一个前驱结点又有一个以上的后继结点。
度:子节点的个数称之为度
树的度:树中各节点度的最大值
深度:从根节点到最底层节点的层数、
所以除了叶子节点,其余结点度可以作为根节点。
例子:
该树的叶子节点为DFGIJ。结点A的度为3,E的度为1,D的度为0。该树的度为3。深度为4.
二叉树
概念:
任意一个节点的子节点个数不能超过2个(树的度为2)的树。
分为满二叉树和完全二叉树;
满二叉树:在不增加树的层数的前提下,无法再增加一个节点的二叉树
特性:满二叉树第K层有2^(k-1)个节点,K层满二叉树总共有2^k-1个节点
完全二叉树:只是删除了满二叉树最底层最右边的连续若干个节点,形成了完全二叉树(可继续增加结点,直到加成满二叉树为止)
其两者关系为:满二叉树 ==> 完全二叉树 完全二叉树 =/=> 满二叉树
例子:
二叉树的遍历:
方法
前序遍历:根 左 右
中序遍历:左 根 右
后续遍历:左 右 根
层序遍历:逐层向下遍历
二叉树的遍历特性:
已知前序遍历序列和中序遍历序列,可以唯一确定一棵二叉树;
已知后序遍历序列和中序遍历序列,可以唯一确定一棵二叉树;
例子:
以上树为例:
若前序遍历则顺序为:ABCDEFG
若中序遍历则顺序为:CBDAFEG
若后序遍历则顺序为:CDBFGEA
若底层遍历则顺序为:ABECDFG