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

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

(0)
上一篇 2018-04-16 10:21
下一篇 2018-04-16 10:28

相关推荐

  • 二叉树的遍历和堆排序

    二叉树的遍历和堆排序

    Python笔记 2018-05-16
  • 高阶函数

    高阶函数 Frist class object 函数在python中是一等公民 函数也是对象,可调用的对象 函数可以作为普通变量,参数,返回值等等 数学概念y=g(f(x)) 在数学和计算机科学中,高阶函数应当是至少满足下面一个条件的函数 接受一个或者多个函数作为参数 输出一个函数 计数器: def counter(base):def inc(step=1)…

    Python笔记 2018-04-23
  • Python内建函数

    内建函数 标识id() 返回对象的唯一标识,CPython返回内存地址 哈希hash() 返回一个对象的hash值 类型type() 返回对象的类型 类型转换 int()、float()、bin()、hex()、oct()、bool()、list()、tuple()、dict()、set()、complex()、bytes()、bytearray() 输入i…

    2018-04-08
  • Python函数

    函数 数学函数 Python函数 若干语句块、函数名称、参数列表构成,组织代码的最小单元 完成一定的功能 作用 结构化编程对代码的最基本的封装,一般按照功能组织一段代码 复用,减少冗余代码 简洁美观,可读易懂 函数分类 内建函数,max()、reversed() 库函数,math.ceil() 函数定义、调用 def语句定义函数 def 函数名(参数列表):…

    2018-04-16
  • Python的内置数据结构

    字符串、列表、元组

    Python笔记 2018-03-31