树
非线性结构，每个元素都可以有多个前驱和后继
树是n(n>=0)个元素
n = 0时，称为空树
树只有一个特殊的没有前驱的元素，称为树的根root
树中除了根结点，其余元素只能有一个前驱，可以有0个或者多个后继
递归定义
树T是n(n>=0)个元素的集合，n=0时，称为空树
有且只有一个特殊元素根，剩余元素都可以被划分为m个互不相交的集合T1,T2,T3,….Tm，而每个树集合都是树，称为树的subtree
子树也有自己的根
树的概念
结点：树中的数据元素
结点的度degree：结点拥有的子树数目称为度，记做d(v)
叶子结点：结点的度为0，称为叶子结点leaf，终端结点，末端结点
分支结点：结点的度不为0，称为非终端结点或者分支结点
分支：结点之间的关系
内部结点：除根结点外的分支结点，当然也不包括叶子结点
树的度是数内各结点的最大值，D结点最大为3，数的度数就是3
孩子结点：结点的子树的根借点成为了该结点的孩子
双亲结点：一个结点是它个子树的根结点的双亲
祖先结点：从结点到该结点所经分支上的所有的结点
子孙结点：结点的所有的子树上的结点都称为该结点的子孙
结点的层次：根结点为第一层，根的孩子为第二层，一次类推
树的深度：树的层次的最大值，
堂兄弟：双亲在同一层的结点
有序树：结点子树是有顺序的，不能交换
无序树：结点的子树是有无序的，可以交换
路径：树中的k个结点n1，n2……..mk，满足ni是n（i+1）的双亲，成为n1到nk的一条路径，就是一条线串下来的，前一个都是后一个的父结点
路径长度=路径上的结点数-1，也就是分支数
森林：m（m>=0）棵不相交的树的集合
对于结点而言，其子树的集合就是森林
树的特点
唯一的根
子树不相交
除了根以外，每个元素只能有一个前驱，可以有0个或者多个后继
根节点没有双亲结点，叶子结点没有孩子结点
二叉树
二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，
二叉树的子树有左右之分，次序不能颠倒。
左斜树：所有结点都只有左子树
右斜树：所有结点都只有右子树
满二叉树：所有的分支结点都存在左子树和右子树
完全二叉树: 除叶子层都达到最大个数，叶子层结点都靠左
性质
(1) 在非空二叉树中，第i层的结点总数不超过2**(i-1), i>=1；
(2) 深度为h的二叉树,最多有(2**h)-1 个结点(h>=1)，最少有h个结点；
(3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；
(4) 具有n个结点的完全二叉树的深度为 int(n**0.5)+1
(5) 有N个结点 的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：
I为结点编号 I>1
int(I/2) 父结点的编号；
2I 判断左儿子
<=N，左儿子编号为2I；
>N， 无左儿子；
2I+1 判断右儿子
<=N，右儿子为2I+1；
>N， 无右儿子。
(6)给定N个节点，能构成h(N)种不同的二叉树。h(N)为卡特兰数的第N项。h(n)=C(2*n，n)/(n+1)。
(7)设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i [4]
本文来自投稿，不代表Linux运维部落立场，如若转载，请注明出处：http://www.178linux.com/96274
