|
我們在使用樹形結(jié)構(gòu)數(shù)據(jù)時，常常需要遍歷整棵樹或某一支下的所有結(jié)點，用于查找、打印等功能。因為樹形結(jié)構(gòu)不同于數(shù)組、鏈表等簡單數(shù)據(jù)結(jié)構(gòu)，它像樹枝一樣每個根結(jié)點可以具有多個子結(jié)點，無限延展，因此需要專門的算法去遍歷。樹形結(jié)構(gòu)的遍歷有很多種方法，下面我們以紫金橋監(jiān)控組態(tài)軟件(以下簡稱為“RealInfo”)為例，簡單講解函數(shù)遞歸在這種遍歷方法中的應(yīng)用。
在RealInfo中，“樹形控件”是表示樹狀結(jié)構(gòu)數(shù)據(jù)的組件，“自由報表”是表示表格數(shù)據(jù)的組件，這兩種組件自身都提供了一些常用方法。我們現(xiàn)在實現(xiàn)這樣的功能：將樹形控件中的指定分支數(shù)據(jù)打印在自由報表中�？梢岳么翱谧远x函數(shù)的遞歸功能。
樹形控件中的數(shù)據(jù)顯示方式如下圖所示：
每個結(jié)點以結(jié)點編碼為唯一標識，每個結(jié)點可以顯示一個字符串作為結(jié)點文本（詳見RealInfo聯(lián)機幫助）。
本例中，我們將樹形結(jié)構(gòu)數(shù)據(jù)打印在自由報表上，其效果如下圖所示：
每個根結(jié)點打印完成后，遇到子結(jié)點時打印位置自動向右、向下移動一個單元格；遇到兄弟結(jié)點時打印位置向下移動一個單元格。
現(xiàn)在我們開始分析算法。我們知道，樹的遍歷是指沿著某條搜索路線，依次對樹中每個結(jié)點均做一次且僅做一次訪問。這樣，我們把遍歷過程想象成為一次單程旅行，出發(fā)點是樹的根結(jié)點，然后按先自左向右、然后自上而下的順序，先后經(jīng)過每個結(jié)點，最后走到最下方的葉子結(jié)點處。
我們可以采用這樣的遍歷方式：
1) 當所在結(jié)點具有子結(jié)點時，那么按自左向右原則，接著訪問它的第一個子結(jié)點，直到所在結(jié)點沒有子結(jié)點為止。
2) 當所在結(jié)點沒有子結(jié)點，但具有兄弟結(jié)點時，那么按自上向下原則依次訪問它的兄弟結(jié)點。
3) 當所在結(jié)點沒有子結(jié)點，而且沒有兄弟結(jié)點時，那么按自上向下原則訪問它父結(jié)點的兄弟結(jié)點。
分析這個過程并觀察樹形結(jié)構(gòu)，我們會發(fā)現(xiàn)，每個父結(jié)點可以擁有n(n>=0)個子結(jié)點，若將這n個子結(jié)點看作父結(jié)點，則每個父結(jié)點仍然具有n個子結(jié)點。由此看來，每一支數(shù)據(jù)乃至整棵樹都可以看作是有限個父-子結(jié)構(gòu)的組合。在樹的遍歷過程中，總是不斷的重復(fù)“父→子”這一訪問方式，因此我們可以提取這一方式形成一個函數(shù)，并利用函數(shù)遞歸來完成整個遍歷。
這個函數(shù)用于根據(jù)輸入的父結(jié)點編碼和起始打印位置將其所有子結(jié)點打印出來。算法如下：
函數(shù)首先判斷輸入結(jié)點是否具有子結(jié)點，如果沒有則返回，如果有則取得子結(jié)點列表，然后循環(huán)打印每個子結(jié)點并遞歸調(diào)用自身函數(shù)打印其子結(jié)點，當一個結(jié)點a的子結(jié)點打印完畢并返回后按相同規(guī)則依次打印的a結(jié)點的兄弟結(jié)點，直到所有兄弟結(jié)點打印完畢為止。
工程制作過程如下：
1) 新建窗口，創(chuàng)建樹形控件，起名為“tree”；創(chuàng)建自由報表起名為“report”；創(chuàng)建一個按鈕。
2) 創(chuàng)建窗口函數(shù)（用于得到指定結(jié)點的子結(jié)點編碼數(shù)組）：
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) 創(chuàng)建窗口函數(shù)(用于遞歸打印指定結(jié)點的子結(jié)點，不打印自身結(jié)點)：
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()<nCol then
#report.AddCol(1);
endif
for i=0 to nCount
if #report.RowCount()<nRow+nRowOffset then
#report.AddRow(1);
endif
strNodeText = #tree.GetNodeTxt(strArrChildNodeKeys[i]); //打印本結(jié)點
#report.SetTxt(nCol,nRow+nRowOffset,strNodeText);
nRowOffset = nRowOffset + 1;
nRowOffset = func_PrintToReport(strArrChildNodeKeys[i]
,nCol+1,nRow,nRowOffset); //遞歸
next
endif
return nRowOffset;
4) 創(chuàng)建窗口函數(shù)（用于打印初始結(jié)點自身，并啟動遞歸函數(shù)）：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) 運行并查看效果。運行時，不選擇樹結(jié)點，點擊按鈕后報表中打印出整棵樹，因為根結(jié)點文本為空，所以報表第一列為空。選中任意一個樹結(jié)點后，報表中打印出本分支所有結(jié)點，包含本結(jié)點。
效果圖如下：
本文以RealInfo為例，講述了一種通過函數(shù)遞歸調(diào)用來實現(xiàn)樹形結(jié)構(gòu)數(shù)據(jù)遍歷的方法，其中遞歸函數(shù)體實現(xiàn)了打印指定結(jié)點的子結(jié)點功能。本方法適用于少量樹形結(jié)構(gòu)數(shù)據(jù)的遍歷，當數(shù)據(jù)量過大時需要作進一步優(yōu)化。
|
