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

树是n(n>=0)个元素

n = 0时,称为空树

树只有一个特殊的没有前驱的元素,称为树的根root

树中除了根结点,其余元素只能有一个前驱,可以有0个或者多个后继

递归定义

Tn(n>=0)个元素的集合,n=0时,称为空树

有且只有一个特殊元素根,剩余元素都可以被划分为m个互不相交的集合T1,T2,T3,….Tm,而每个树集合都是树,称为树的subtree

子树也有自己的根

树的概念

结点:树中的数据元素

结点的度degree:结点拥有的子树数目称为度,记做d(v)

叶子结点:结点的度为0,称为叶子结点leaf,终端结点,末端结点

分支结点:结点的度不为0,称为非终端结点或者分支结点

分支:结点之间的关系

内部结点:除根结点外的分支结点,当然也不包括叶子结点

树的度是数内各结点的最大值,D结点最大为3,数的度数就是3

孩子结点:结点的子树的根借点成为了该结点的孩子

双亲结点:一个结点是它个子树的根结点的双亲

祖先结点:从结点到该结点所经分支上的所有的结点

子孙结点:结点的所有的子树上的结点都称为该结点的子孙

结点的层次:根结点为第一层,根的孩子为第二层,一次类推

树的深度:树的层次的最大值,

堂兄弟:双亲在同一层的结点

有序树:结点子树是有顺序的,不能交换

无序树:结点的子树是有无序的,可以交换

路径:树中的k个结点n1n2……..mk,满足nini+1)的双亲,成为n1nk的一条路径,就是一条线串下来的,前一个都是后一个的父结点

路径长度=路径上的结点数-1,也就是分支数

森林:mm>=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*nn)/(n+1)

(7)设有i个枝点,I为所有枝点的道路长度总和,J为叶的道路长度总和J=I+2i [4]

 

本文来自投稿,不代表Linux运维部落立场,如若转载,请注明出处:http://www.178linux.com/96274

(0)
上一篇 2018-04-16 09:12
下一篇 2018-04-16 09:14

相关推荐