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

树是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)
zhangmengzhangmeng
上一篇 2018-04-16 09:12
下一篇 2018-04-16 09:14

相关推荐

  • 树 非线性结构,每个元素可有多个前驱和后继 树是n(n>=0)个元素的集合,n=0时,称为空树,树只有一个特殊的没有前驱的元素,称为树的根root,树中除了根结点外,其余元素只能有一个前驱,可以有零个和多个后继,子树也有自己的根 结点:树中的数据元素 结点的度degree:结点拥有的子树的数目称为度,记作d(v)。树的度是树内各结点的度最大值 叶子结点…

    2018-04-16
  • Centtos7搭建ftp服务

    Centtos7搭建ftp服务 下载安装软件包 yum -y install vsftpd   开启启用ftp服务 systemctl start vsftpd    #设置立即启用该服务 systemctl status vsftpd   #查看该服务当前运行状态 systemctl enable vsftpd   #设置开机自动启用该服务 systemc…

    Python笔记 2018-07-07
  • Python第十二周学习总结

    Git的使用

    2018-05-27
  • 递归函数

    递归函数 def foo(b,b1=3):print(“foo1 called “,b,b1)def foo2(c):foo3(c)print(“foo2 called”,c)def foo3(d):print(“foo3 called”)def mian():print(“…

    2018-04-16
  • 面向对象,魔术方法

    面向对象 一面向对象 什么是面向对象: 一种认识世界、分析世界的方法论。将万事万物抽象为类。 类class: 类是抽象的概念,是万事万物的抽象,是一类事物的共同集合的集合。 用计算机语言来描述类,就是属性和方法的集合。 对象instance,object: 对象是类的具象,是一个实体。 每个个体都是抽象类的不同实体。 哲学 一切皆对象 对象是数据和操作的封装…

    Python笔记 2018-05-14
  • Python 部分知识点总结(一)

    此篇博客只是记录第三周未掌握或不熟悉的知识点,用来加深印象。

    Python笔记 2018-03-26