[树](1)树

树型结构是一类重要的非线性数据结构,其中以树和二叉树最为常用,直观看来,树是以分支关系定义的层次结构,树结构在客观世界中广泛存在,如人类社会的族谱和各种社会组织机构都可以用树来形象表示

树在计算机领域中也得到广泛应用,如在编译程序中,可用树形象表示,树在计算机领域中也得到广泛应用,如在编译程序中,可用树来表示源程序的语法结构,又如在数据库系统中,树形结构也是信息的重要组织形式之一

这里我们重点理解二叉树的存储结构及其各种操作,并研究树和森林与二叉树的转换关系。

定义简述:树是由结点或顶点和边组成的(可能是非线性的)且不存在任何环的一种数据结构,没有结点的树称为空(NULL或empty)树,一棵非空的树包括一个根结点,还很可能有多个附加结点,所有的结点构成一个多级分层的结构

树的定义和基本术语

树(Tree)是n(n>=0)个结点的有限集,在任意一颗非空树中:

  1. 有且仅有一个特定的称为根(Root)的结点
  2. 当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,...,Tm,其中每一个集合本身又是一棵树,并且称为根的子树(SubTree)

img

其中(a)是只有一个结点的树,而(b)是拥有十三个个结点的树、其中A是根、其余结点分成3个互不相交的子集:

  • T1={B,E,F,K,L}
  • T2={C,G}
  • T3={D,H.I,J,M}

T1、T2和T3都是根A的子树、且本身也是一棵树,例如T1,其根为B,其余结点分为两个互不相交的子集:

  • T11={E,K,L}
  • T12={F}

T11和T12都是B的子树,而T11中E是根,{K}和{L}是E的两棵互不相交的子树,其本身又是只有一个根结点的树

上述树的结构定义加上树的一组基本操作就构成了抽象数据类型树的定义:

    ADT Tree{
        数据对象D:D是具有相同特性的数据元素的集合
        数据关系R:若D为空集,则称之为空树
            若D仅含一个数据元素,则R为空集,否则R={H},H是如下二元关系:
        (1)在D中存在惟一的称为根的数据元素root,它的关系H下无前驱
          
        (2)任意D={root}!=空集,则存在D={root}的一个划分:D1,D2,...,Dm(m>0),对
        任意j!=k(1<=j,k<=m)有Dj属于Dk等于空集,且对任意的i(1<=i<=m)惟一存在数
        据元素Xi属于Di,有<root,xi>属于H
        
      (3)对应于D={root}的划分,H={<root,x1>},...,<root,xm>有惟一划分H1,H2...Hm
        (m>0),对任意j!=k(1<=j,k<=m)有Hj并Hk=空集,且对任意i(1<=i<=m),Hi是Di上的二
        元关系,(Di,{Hi})是一颗符合本定义的树,称为根root的子树
        
        基本操作P:
           InitTree(&T)
               操作结果:构造空树T
           
           DestroyTree(&T)
               初始条件:树T存在
               操作结果:销毁树T
           
           CreateTree(&T,definition)
               初始条件:definition给出树的定义
               操作结果:按definition构造树T

           ClearTree(&T)
               初始条件:树T存在
               操作结果:将树T清为空树

           TreeKmpt(T)
               初始条件:树T存在
               操作结果:若T为空树,则返回TRUE,否则返回FALSE

           TreeDepth(T)
               初始条件:树T存在
               操作结果:返回T的深度
           
           Root(T)
               初始条件:树T存在
               操作结果:返回T的根

           Value(T,cur_e)
               初始条件:树T存在,cur,e是T中某个结点
               操作结果:返回cur_e的值

           Assign(T,cur_e,value)
               初始条件:树T存在,cur_e是T中某个结点
               操作结果:结点cur_e赋值为value

           Parent(T,cur_e)
               初始条件:树T存在,cur_e是T中某个结点
               操作结果:若cur_e是T的非根结点,则返回它的双亲,否则函数值为NULL

           LeftChild(T,cur_e)
               初始条件:树T存在,cur_e是T中某个结点
               操作结果:若cur_e是T的非叶子结点,则返回它的左孩子,否则返回NULL

           RightSibling(T,cur_e)
               初始条件:树T存在,cur_e是T中某个结点
               操作结果:若cur_e是T的非叶子结点,则返回它的右孩子,否则返回NULL

           InsertChild(&T,&p,i,c)
               初始条件:树T存在,p指向T中某个结点,1<=i<=p所指结点的度+1,非空树c
               与T不相交
               操作结果:插入c为T中p指结点的第i棵子树

           DeleteChild(&T,&p,i)
               初始条件:树T存在,p指向T中某个结点,1<=i<=p指结点的度
               操作结果:删除T中p所指结点的第i棵子树

           TraverseTree(T,Visit())
               初始条件:树T存在,Visit是对结点操作的应用函数
               操作结果:按某次序对T的每个结点调用函数visit()一次且至多一次
               一旦visit()失败,则操作失败
    }ADT Tree

树的结构定义是一个递归的定义,即在树的定义中又用到树的概念,它道出树的固有特性,树还可有其他的表示形式,如:

嵌套集合(即是一些集合的集体,对于其中任何两个集合,或者不相交,或者一个包含另一个)的形式表示的

img

广义表表示法(根作为由子树森林组成的的表的名字写在表的左边):

(A(B(E(K,L),F),C(G),D(H,(M),I,J)))

凹入表示法(类似书的编目)

img

表示方法的多样化,正说明了树结构在日常生活中及计算机程序设计中的重要性,一般来说,分等级的分类方案都可用层次结构来表示,也就是说,都可导致一个树结构。

下面列出树结构中的一些基本术语:

  • 树的结点包含一个数据元素及若干指向其子树的分支
  • 结点拥有的子树数称为结点的度(Degree)
  • 度为0的结点称之为叶子(Leaf)终端结点
  • 度不为0的结点称为非终端结点分支结点
  • 除根结点之外,分支结点也称为内部结点
  • 树的度是树内各结点的度的最大值
  • 结点的子树的根称为改结点的孩子(Child)
  • 相应的,该结点称为孩子的双亲(Parent)
  • 同一个双亲的孩子之间互称兄弟(Sibling)
  • 结点的祖先是从根到该结点所经分支上的所有结点
  • 反之,以某结点为根的子树中的任一结点都称为该结点的子孙
  • 结点的层次(Level)从根开始定义,根为第一层,根的孩子为第二层,若某结点在第 L 层,则其子树的根就在第 L+1 层
  • 其双亲在同一层的结点互为堂兄弟
  • 树中结点的最大层次称为树的深度(Depth)或高度

img

img对照图

如果将树结点的各子树看成从左至右是有次序的(即不能互换),则称该树为有序树,否则称为无序树,在有序树中最左边的子树的根称为第一个孩子,最右边的称为最后一个孩子

无序树简叙:

  • 该树的根的所有左孩子的值都小于根值,而右孩子的值大于根值,其中任意节点的子节点之间没有顺序关系。

img

有序树简叙:

  • 左边的树兄弟节点左边的比右边的小;右边的树兄弟节点右边的比左边的小,总而言之,兄弟结点之间有顺序的称之为有序树

img

在有序树中最左边的子树的根称为第一个孩子,Tree A中第一个孩子为2,最右边的称为最后一个孩子,Tree A中最后一个孩子为6

森林(Forest)是m(m>=0)棵互不相交的树的集合,对树中每个结点而言,其子树的集合即为森林,由此,也可以森林和树相互递归的定义来描述树。

就逻辑结构而言,任何一棵树是一个二元组Tree=(root,F),其中:root是数据元素,称做树的根结点,F是m(m>=0)棵树的森林,F={T1,T2,...,Tm},其中Ti=(ri,Fi)称做根root的第i棵子树,当m!=0时,在树根和其子树森林之间存在下列关系:

RF={<root,ri>|i=1,2,...,m,m>0}

这个定义将有助于得到森林和树与二叉树之间转换的递归定义

树的应用广泛,在不同软件系统中,树的基本操作集不尽相同。

img在其他树那儿还有个树状数组

任重道远呀.....加油!

本文链接:

https://nullcode.fun/40.html
1 + 1 =
快来做第一个评论的人吧~