2.12 Go二叉树数据结构的应用
树的定义和基本术语
树的定义：
树是n(n>=0)个节点的有限集合T
一颗非空树需要满足的两个条件：
-
有且仅有一个根节点(
root) -
当
n>1时，其余节点可分为m(m>=0)个互不相交的有限集合T1，T2，……，Tm，其中每一个集合本身又都是一棵树，并且称为根的子树（Subtree）
特点:
树的定义是递归的，树是一种递归数据结构。
树的其他基本术语：
-
节点的度：树中每个节点具有的子树数，或后继节点数称为该节点的度。--->和链表类似，拥有前驱节点和后继节点
-
树的度：树中所有节点的度的最大值称为树的度。
-
分支节点：度大于
0的节点称为分支节点或非终端节点。 -
叶子节点：度为
0的节点称为叶子节点或终端节点。 -
儿子节点：一个节点的后继称为该节点的儿子节点。
-
父亲节点：一个节点称为其后继节点的父亲节点。
-
子孙节点：一个节点的所有子树中的节点称为该节点的子孙节点。
-
祖先节点：从根节点到达一个节点的路径上，通过的所有节点称为该节点的祖先节点。
-
兄弟节点：具有同一父亲的节点相互称为兄弟节点。
-
节点的层数：树是一种层次结构，根节点为第一层，其儿子节点为第二层，以此类推可以得到每个节点的层数。
-
树的深度：树中节点的最大层数称为树的深度或高度。
-
森林：
0个或多个不相交的树的集合称为森林。
二叉树简介
二叉树的特点：
-
二叉树中每个节点最多有两棵子树。称为左子树和右子树
-
左子树和右子树是有顺序的，有左右之分，次序不能随意颠倒；
-
即使某个节点只有一个子树，也要区分左右子树。
特殊的二叉树：
斜树
满二叉树
完全二叉树
斜树
-
所有的节点只有左子树则称为左斜树
-
所有节点只有右子树则称为右斜树
满二叉树
-
一棵二叉树中，所有的分支结点都存在左子树和右子树
-
所有的叶子结点都在同一层上
满二叉树的特点：
-
叶子只能出现在最下一层
-
非叶子结点度一定是
2 -
在同样深度的二叉树中，满二叉树的结点个数最多，叶子树最多
完全二叉树
-
一棵二叉树中，除最后一层外，若其余各层都是满的
-
最后一层要么是满的，要么在右边缺少若干个连续的节点
-
完全二叉树不一定是满二叉树--->不一定非要左右子树完全
完全二叉树的特点：
-
叶子结点只能出现在最下一层（满二叉树继承而来）。
-
最下层叶子结点一定集中在左部连续位置。
-
倒数第二层，如有叶子节点，一定出现在右部连续位置。
-
同样结点树的二叉树，完全二叉树的深度最小。
二叉树的连接存储结构
二叉树的存储方法：
-
顺序存储--->底层数据结构是数组
-
链接存储--->底层数据结构是链表
-
线索树存储--->底层数据结构是链表