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

树是n(n>=0)个元素的集合,n=0时,称为空树,树只有一个特殊的没有前驱的元素,称为树的根root,树中除了根结点外,其余元素只能有一个前驱,可以有零个和多个后继,子树也有自己的根

结点:树中的数据元素

结点的度degree:结点拥有的子树的数目称为度,记作d(v)。树的度是树内各结点的度最大值

叶子结点:结点的度为零

分支结点:结点的度不为0

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

孩子结点:结点的子树的根结点称为该结点的孩子

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

兄弟结点:具有相同双亲结点的结点

祖先结点:从根结点到该结点所经分支上所有的结点,A,B,D,都是G的祖先结点

树

结点的层次(level):根结点为第一层,根的孩子结点为第二层,依次类推,记作l(v)

树的深度(高度depth):树的层次的最大值,上图的树深度为4

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

树分为有序树和无序树,有序树有顺序,不能交换,无序树没有顺序,不能发生交换

路径:树中的k个结点n1,n2…nk,满足ni是n(i+1)的双亲,称为n1到nk的一条路径,就是一条线串下来,前一个都是后一个的(前驱)结点

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

森林:m(m>=0)棵不相交的数的集合,对结点而言,其子树的集合可就是森林

二叉树

二叉树:每个结点最多2棵子树,有序树,左右子树不能交换次序,即使某个结点只有一棵树,也要确定他是左子树还是右子树

左斜树,所有结点都只有左子树,右子树,所有结点都只有右子树

满二叉树

一棵二叉树的所有分支结点都存在左子树和右子树,且所有叶子结点只存在最下面一层,同样深度的二叉树中,满二叉树结点最多,k为深度,则结点总数为2**k-1

完全二叉树

若二叉树的深度为k,二叉树的层数从1到k-1层的结点数都达到了最大数,在第k层的所有结点都集中在最左边,就是完全二叉树,k为深度,则结点的最大值为2**k-1,当达到最大值的时候就是满二叉树

二叉树性质

在二叉树的第i层上至多有2**(i-1)个结点

深度为k的二叉树,至多有2**k-1个结点

对任何一棵二叉树T,如果其终端结点数为n0,度数为2的结点为n2,则有n0=n2+1,换句话说就是,叶子结点数-1=度数为2的结点数

高度为k的二叉树,至少有k个结点

含有n个结点的二叉树高度至多为n,最小为math.ceil(log2(n+1))

具有n个结点的完全二叉树的深度为int(log2n)+1或者math.ceil(log2(n+1))

 

 

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

联系我们

400-080-6560

在线咨询

工作时间:周一至周五,9:30-18:30,节假日同时也值班

QR code