[Day12]程序菜鸟自学C++资料结构演算法 – 树Tree

前言：相信大家对於「树」都不陌生，资料结构中的树其实是模拟现实生活中的树干、树枝和叶子，相当於树状结构的资料集，这时的资料已经不像之前的阵列、链结串列一样是线性的资料结构，而是阶层性的非线性资料结构。

名词介绍：

• 根节点或树根(Root)：位於树状结构的最顶端，上方没有其他节点。例如：A

• 父节点(Parent)、子节点(Children)：若A节点的下方还有B节点，则就可称A节点为B节点的父节点；反之，B节点为A节点的子节点。

• 叶节点(Leaf)：没有子节点的节点称为叶节点。例如：G、H、E、F

• 祖先节点(Ancenstors)：指某节点到跟节点之间所经过的所有节点。例如：G的祖先节点为D、B

• 非终端节点(Noterminal)：除了叶节点之外的其他节点，都可称为非终端节点。例如：A、B、C、D

• 兄弟节点(Siblings)：指有共同的父节点。例如：G和H为兄弟节点

• 分支度(Degree)：指每个节点所拥有的子节点树。例如A的分支度为2

• 阶层(Level)：若树根是一，其子节点是二，则可依序推算出树的阶层树。例如：A的阶层是一，B、C的阶层是二，以此类推。

• 树深(Depth)：又称为树高(Height)，指树的最大阶层数。

• 子树(Subtree)：每一个子集合也是一棵树，而这些树称为根节点的子树。

树的定义：树的节点个數是一或多个有限集合，必存在一个根节点且各节点之间不能有回圈产生或不连结的子树。

二元树(Binary Tree)：

二元树的定义：二元树为资料结构中最广泛运用的树状结构，其特点为树中的每个节点最多只能有两个子节点(分支度<=2)。二元树的节点个數是一个有限集合，或是没有节点的空集合。二元树的节点可以分成兩个没有交集的子树，称为「左子树」（Left Subtree）和「右子树」（Right Subtree）。

歪斜树（Skewed Tree）：当一颗树只有左边节点或右边节点时，就可以称做歪斜树。

完满二元树（Full Binary Tree）：如果二元树的树高是h且二元树的节点數是 ，满足此条件的树则可称为完满二元树。

完整二元树(Complete binary tree)：如果二元树的深度为h，所含的节点數小於 ，但其节点的编号方式如同深度为的完满二元树一般，从左到右，由上到下的顺序一一对应结合，则可称为完整二元树。

严格二元树：二元树的每个非终端节点均有非空的左右子树，则可称为严格二元树。

本日小结：今天介绍了树状结构和二元树，这次虽然没有实作但却有大量的名词解释，先把树状结构的名词记熟再学习二元树会比较轻松喔！二元树虽然很多中类很复杂，但本质上就算是一种二分法，在生活中我们常常面临许多选择，当决策的方式越来越少，事情也就看似简单了一点，明天就要开始实作二元树的处存方式o(^∀^*)o