记住密码

您所在的位置:首页 > 技术 > 应用案例

函数递归在树形结构数据遍历中的应用

信息时间:2012-11-05 信息来源:紫金桥软件技术有限公司

            我们在使用树形结构数据时,常常需要遍历整棵树或某一支下的所有结点,用于查找、打印等功能。因为树形结构不同于数组、链表等简单数据结构,它像树枝一样每个根结点可以具有多个子结点,无限延展,因此需要专门的算法去遍历。树形结构的遍历有很多种方法,下面我们以紫金桥监控组态软件(以下简称为“RealInfo)为例,简单讲解函数递归在这种遍历方法中的应用。

           RealInfo中,“树形控件”是表示树状结构数据的组件,“自由报表”是表示表格数据的组件,这两种组件自身都提供了一些常用方法。我们现在实现这样的功能:将树形控件中的指定分支数据打印在自由报表中。可以利用窗口自定义函数的递归功能。

           树形控件中的数据显示方式如下图所示:

     

     

           每个结点以结点编码为唯一标识,每个结点可以显示一个字符串作为结点文本(详见RealInfo联机帮助)。

           本例中,我们将树形结构数据打印在自由报表上,其效果如下图所示:

     

     

           每个根结点打印完成后,遇到子结点时打印位置自动向右、向下移动一个单元格;遇到兄弟结点时打印位置向下移动一个单元格。

           现在我们开始分析算法。我们知道,树的遍历是指沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问。这样,我们把遍历过程想象成为一次单程旅行,出发点是树的根结点,然后按先自左向右、然后自上而下的顺序,先后经过每个结点,最后走到最下方的叶子结点处。

    我们可以采用这样的遍历方式:

    1)        当所在结点具有子结点时,那么按自左向右原则,接着访问它的第一个子结点,直到所在结点没有子结点为止。

    2)        当所在结点没有子结点,但具有兄弟结点时,那么按自上向下原则依次访问它的兄弟结点。

    3)        当所在结点没有子结点,而且没有兄弟结点时,那么按自上向下原则访问它父结点的兄弟结点。

    分析这个过程并观察树形结构,我们会发现,每个父结点可以拥有n(n>=0)个子结点,若将这n个子结点看作父结点,则每个父结点仍然具有n个子结点。由此看来,每一支数据乃至整棵树都可以看作是有限个父-子结构的组合。在树的遍历过程中,总是不断的重复“父→子”这一访问方式,因此我们可以提取这一方式形成一个函数,并利用函数递归来完成整个

企业导航

    紫金桥软件技术有限公司

    联系人:张欢

    电话:0459-8151391

    传真:0459-8151391-804

    企业网址:http://www.realinfo.com.cn

    邮箱:dq@realinfo.com.cn

    地址:黑龙江省大庆市高新区服务外包产业园C-1座817室

Copyright2006 www.xbgk.com Corporation,All Rights Reserved 客服电话:029-84589271 15719286749 备案号:陕ICP备10010438号-5
关注我们,随时随地获得最新资讯