树

树

非线性结构，每个元素都可以有多个前驱和后继

树是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]