加载中…
个人资料
_陌上花开7_
_陌上花开7_
  • 博客等级:
  • 博客积分:0
  • 博客访问:68,244
  • 关注人气:29
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

(2013-05-31 21:52:55)
标签:

孩子

双亲

结点

兄弟

分类: 数据结构

树的定义和基本术语:

在书中常常将数据元素称为结点

是n个结点的有限集合。当n=0时,称为空树;任意一棵非空树满足一下条件:

(1)有且仅有一个特定的称为的节点

(2)当n>1时,除根结点之外的其余结点被分为m(m>0)个互不相交的有限集合T1,T2,……Tm,其中每个集合又是一棵树,并称为这个根结点的子树。显然树的定义是递归的。

书的基本术语:

结点的度,树的度

某结点所拥有的子树的个数称为该结点的;树中各结点度的最大值称为该树的度

叶子结点,分支结点

度为0的结点称为叶子结点,也称为终端结点;度不为0的结点称为分支结点,也称为非终端结点

孩子结点,双亲结点,兄弟结点

某结点的子树的根结点称为该结点的孩子结点;反之,该结点称为其孩子结点的双亲结点;具有同一个双亲的孩子结点互称为兄弟结点

路径,路径长度

如果树的结点序列n1,n2,……nk,满足如下关系:结点n(i)是结点n(i+1)的双亲(1<=i<=k),则把n1,n2,……nk,称为一条由n1至nk的路径,路径上经过的边数称为路径的长度

祖先,子孙

如果从结点x到结点y有一条路径,那么x就称为y的祖先,y称为x的子孙。显然,以某结点为根的子树中的任一节点都是该结点的子孙。

结点的层数,树的深度(高度)

规定根结点的层数为1,对其余任何结点若某结点在第k层,则其孩子结点在第k+1层;树中所有结点的最大层数称为树的深度,也称为树的高度

层序编号

将树中结点按照从上层到下层,同层从左到右的次序依次给它们编以从1开始的连续自然数,树的这种编号方式称为层序编号。显然,通过层序编号可以将一棵树变成线性序列。

有序树,无序树

如果一棵树中结点的各子树从左到右是有次序的,即若交换了结点各子树的相对位置,则构成不同的树,称为这棵树为有序树,反之,就称为无序树

森林

m(m>=0)棵互不相交的树的集合构成森林。任何一棵树,删去根结点就变成了森林。
树的抽象数据类型定义

ADT Tree//树是有一个根节点和若干子树构成,树中结点具有相同的数据类型及层次关系

Data

Operation

 InitTree

   前置条件:树不存在

   输入:无

   功能:初始化一棵树

   输出:无

   后置条件:构造一棵树

DestroyTree

   前置条件:树已存在

   输入:无

   功能:销毁一棵树

   输出:无

   后置条件:释放该树占用的存储空间

PreOrder

   前置条件:树已存在

   输入:无

   功能:前序遍历树

   输出:树的前序遍历序列

   后置条件:树保持不变

PostOrder

   前置条件:树已存在

   输入:无

   功能:后序遍历树

   输出:树的后序遍历序列

   后置条件:树保持不变

LeverOrder

   前置条件:树已存在

   输入:无

   功能:层序遍历树

   输出:树的层序遍历序列

   后置条件:树保持不变

endADT

树的遍历操作

树中最基本的操作是遍历(traverse)。树的遍历是指从根节点出发,按照某种次序访问树中的所有结点,是的每个结点都被访问一次且仅被访问一次。

1、前序遍历

定义:若树为空,则空操作返回;否则

(1)访问根节点

(2)按照从左到右的顺序前序遍历根节点的每一子树。

2、后序遍历

定义:若树为空,则空操作返回;否则

(1)按照从左到右的顺序前序遍历根节点的每一子树。

(2)访问根节点

3、层序遍历

树的层序遍历也称为树的广度遍历,其操作定义为从树的第一层(即根节点)开始,自上而下逐层遍历,在同一层中,按从左到右的顺序对结点逐个访问。

树的存储结构

2.1、双亲表示法  //实质上是一个静态链表

结构:data + parent

data为数据域,存储树中结点的数据信息;

parent为指针域即游标,存储该结点的双亲在数组中的下标。C++模板机制:

template<ckass DataType>

struct PNode  //数组元素的类型

{

    DataType data;//树中结点的数据信息

int parent;   //该节点的双亲在数组中的下标,根节点一般用-1来表示

};

2、2孩子表示法   //是指是基于链表的存储方法

2.2.1、多重链表表示法

①指针域的个数等于该节点的度

data+degree+child1+child2+……childd

data为数据域,存放该结点的数据信息;

degree为度域,存放该结点的度;

child1~childd为指针域,指向该结点的孩子结点。

②指针域的个数等于树的度

data+degree+child1+child2+……childd

其中data为数据域,存放该结点的数据

 child1~childd为指针域,指向该结点的孩子结点。对于①节约空间,但操作不方便,所以很少用;对于②操作容易实现,但浪费存储空间。

2.2.2、孩子链表表示法

孩子结点child+next

表头结点data+firstchild

2.3双亲表示法

双亲孩子表示法是将双亲表示法和孩子表示法相结合的存储方法。仍将各个结点的孩子结点分别组成单链表,同时用一维数组顺序存储树中的各节点,数组元素除了包括结点的数据信息和该结点的孩子链表的头指针之外,还增设一个域存储结点的双亲结点在数组中的下标。

2.4孩子兄弟表示法

firstchild+data+rightsib

其中data为数据源,存储该结点的数据信息;

firstchild为指针域,存储该结点的第一个孩子结点的存储地址

rightsib为指针域,存储该节点的右xiongdi9结点的存储地址。


 

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
后一篇:二叉树
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

    后一篇 >二叉树
      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有