• A+

在前面的数据存储结构都是线性的,也就是一对一连着的,到了树形结构就是一对多的结构了,就像是一颗树那样,它只有一根主干(根节点),主干上长有很多树枝,树枝上又有很多枝杈,枝杈上又有很多树叶(叶结点)

树

很明显的没有孩子的为叶节点,度的值为当前节点孩子的个数,深第为4,为树的层数,下面开始写写这种结构

 


一、先做准备运动

这个是存储树结点数据的结构,首先tree为表明它这个结点是属于哪一颗树的。因为我设计成结点是可以通过外面访问的,若要对它操作,我起码也要知道它是哪颗树的吧。data就是数据域了,用来保存数据的,数组childs是用来保存子节点的,构造函数Node必须指定它是属于哪棵树的,树都没有,怎么会有结点呢。ValueTo方法用来修改它的数据域的

 


二、预备运动

这里我像线性表那样设置了一个头结点,其实是为了方便操作,设定头结点有且只有一个子节点,这就是根节点,_length用来保存树的结点个数,还有两个构造函数,一个构造成空树,一个构造成只有一个根节点的树

 


三、创建树的根

这个方法是为了那些空树用来创建根节点的,在创建根节点前,首先要判断一下是否已经存在了根节点,然后就只需要创建根节点,赋值数据,再将它的引用赋值给头结点的子节点数组第一位,最后将长度设置为1

 


四、添加结点

为指定的结点添加结点,首先判断一下要添加的目标结点是不是本树的结点,如果不属于自己的结点,那就没有权利去操作它了,新建结点addNode,并赋值数据,先临时保存一下目标结点的所有子节点,然后确定扩展后子节点数组的长度,重构目标结点的子节点数组,然后依次赋值,将新加的结点放到最后面,再将长度+1

 

这个是通过索引来为目标结点添加子节点,首先需要判断索引的合法性,再用索引来找到目标结点,再用AddNodeTo()方法添加子节点

 


五、返回指定位置的结点

通过索引来获取到指定的结点,首先涉及到索引,就必须要检查索引的合法性,还要判断一下树是否为空,索引的大小是依照从上层往下层,每层从左往右递增,然后看图吧,涉及层操作,用队列把它变成线性的

树

 


六、删除目标位置的结点和其子结点

通过索引删除删除结点,首先的要检查索引的合法性,如果要删除1结点,也就是根节点,那么直接清空整棵树就好了,要删除一个结点,就必须找到它的父节点,删除掉对它的引用,通过GetNodeParentAndLocalByIndex方法,找到它的父节点和所在引用数组中的位置,先用临时结点数组保存子节点数组的引用,重构子节点数组的大小-1,除去对删除结点的引用。最后,结点长度-1

 


七、返回指定位置的父节点及其索引

首先,判断索引的合法性,是否为根节点,是否为空树,后面使用队列,参考GetNodeByIndex方法(一样的,哈哈)

 


八、层次遍历树,存储为数组

将树按层遍历转换成数组,同理用队列的方式,将所有结点入队,再每个出队,赋值给数组数组,用goIndex作为指标,再返回数据数组

 


九、获得树的高度

计算树的高度,首先检查树是否为空,再用队列用来保存每一层的结点,count变量是用来保存每层结点的个数,队列出入队都以层为单位。每一次出队,树的高度都加1

 


十、其他的方法

 


十一、测试

 


十二、结果

树

  • 我的微信
  • 扫一扫加我微信
  • weinxin
  • 微信我的
  • 我微信扫一扫加
  • weinxin
  • 版权声明:本站原创文章,于2017 年 2 月 24 日23:17:14,由 发表,共 1700 字。
  • 转载请注明:树 | 吃菜网

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: