函數遞歸在樹形結構數據遍歷中的應用

我們在使用樹形結構數據時，常常需要遍歷整棵樹或某一支下的所有結點，用于查找、打印等功能。因為樹形結構不同于數組、鏈表等簡單數據結構，它像樹枝一樣每個根結點可以具有多個子結點，無限延展，因此需要專門的算法去遍歷。樹形結構的遍歷有很多種方法，下面我們以紫金橋監控組態軟件(以下簡稱為“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為例，講述了一種通過函數遞歸調用來實現樹形結構數據遍歷的方法，其中遞歸函數體實現了打印指定結點的子結點功能。本方法適用于少量樹形結構數據的遍歷，當數據量過大時需要作進一步優化。