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

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

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

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

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

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

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

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

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

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

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

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

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

这个函数用于根据输入的父结点编码和起始打印位置将其所有子结点打印出来。算法如下：

函数首先判断输入结点是否具有子结点，如果没有则返回，如果有则取得子结点列表，然后循环打印每个子结点并递归调用自身函数打印其子结点，当一个结点a的子结点打印完毕并返回后按相同规则依次打印的a结点的兄弟结点，直到所有兄弟结点打印完毕为止。

工程制作过程如下：

1) 新建窗口，创建树形控件，起名为“tree”；创建自由报表起名为“report”；创建一个按钮。

2) 创建窗口函数(用于得到指定结点的子结点编码数组)：

func_GetAllChildNodeKey(Tree& treeObj, String& strFatherNodeKey, String Array& strArrChildNodeKeys) As Int

代码如下：

int nChildNodeCount = 0;

string strNodeKeyTemp = "";

int i = 0;

strArrChildNodeKeys.Clear();

nChildNodeCount = #treeObj.GetNodeCount(strFatherNodeKey);

for i=0 to nChildNodeCount

if strFatherNodeKey=="" then

strNodeKeyTemp = IntToStr(i,10);

else

strNodeKeyTemp = strFatherNodeKey + "." + IntToStr(i,10);

endif

strArrChildNodeKeys.Add(strNodeKeyTemp);

next

return nChildNodeCount;

3) 创建窗口函数(用于递归打印指定结点的子结点，不打印自身结点)：

func_PrintToReport(String strFatherNodeKey, Int nCol, Int nRow, Int& nRowOffSet) As Int

代码如下：

string strArrChildNodeKeys[];

string strNodeText = "";

int nCount = 0;

int i = 0;

func_GetAllChildNodeKey(#tree,strFatherNodeKey,strArrChildNodeKeys);

nCount = strArrChildNodeKeys.GetCount();

if nCount>0 then

if #report.ColCount()

#report.AddCol(1);

endif

for i=0 to nCount

if #report.RowCount()

#report.AddRow(1);

endif

strNodeText = #tree.GetNodeTxt(strArrChildNodeKeys[i]); //打印本结点

#report.SetTxt(nCol,nRow+nRowOffset,strNodeText);

nRowOffset = nRowOffset + 1;

nRowOffset = func_PrintToReport(strArrChildNodeKeys[i]

,nCol+1,nRow,nRowOffset); //递归

next

endif

return nRowOffset;

4) 创建窗口函数(用于打印初始结点自身，并启动递归函数)：func_Print()

代码如下：

int nRowOffSet = 0;

#report.DelTailCol(#report.ColCount());

#report.DelTailRow(#report.RowCount());

#report.AddCol(1);

#report.AddRow(1);

#report.SetTxt(1,1,#tree.GetNodeTxt(#tree.GetCurSelNodeKey()));

func_PrintToReport(#tree.GetCurSelNodeKey(),2,2,nRowOffSet);

5) 在按钮中鼠标点击动作中输入：func_Print();

6) 运行并查看效果。运行时，不选择树结点，点击按钮后报表中打印出整棵树，因为根结点文本为空，所以报表第一列为空。选中任意一个树结点后，报表中打印出本分支所有结点，包含本结点。

效果图如下：

本文以RealInfo为例，讲述了一种通过函数递归调用来实现树形结构数据遍历的方法，其中递归函数体实现了打印指定结点的子结点功能。本方法适用于少量树形结构数据的遍历，当数据量过大时需要作进一步优化。