當前位置:自動化網>紫金橋軟件技術有限公司門戶>應用案例>函數遞歸在樹形結構數據遍歷中的應用

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

          發布時間:2012-11-05 10:20   類型:專業論文   人瀏覽

           

                我們在使用樹形結構數據時,常常需要遍歷整棵樹或某一支下的所有結點,用于查找、打印等功能。因為樹形結構不同于數組、鏈表等簡單數據結構,它像樹枝一樣每個根結點可以具有多個子結點,無限延展,因此需要專門的算法去遍歷。樹形結構的遍歷有很多種方法,下面我們以紫金橋監控組態軟件(以下簡稱為“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(StringstrFatherNodeKey,IntnCol,IntnRow,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]);      //打印本結點

                       #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為例,講述了一種通過函數遞歸調用來實現樹形結構數據遍歷的方法,其中遞歸函數體實現了打印指定結點的子結點功能。本方法適用于少量樹形結構數據的遍歷,當數據量過大時需要作進一步優化。

          本文地址:http://m.xznet110.com/apply/d_1nrutga2l2c9o_1.html

          拷貝地址

          版權聲明:版權歸中國自動化網所有,轉載請注明出處!

          留言反饋
          • 評價:

          • 關于:

          • 聯系人:

          • 聯系電話:

          • 聯系郵箱:

          • 需求意向:

          • 驗證碼:

            看不清楚?

          X
          下載企業APP

          成為企業會員免費生成APP!

          主站蜘蛛池模板: 嘟嘟嘟www在线观看免费高清 | 亚洲成色在线综合网站| 精品人妻一区二区三区四区| 国产a级一级久久毛片| 成年女人色费视频免费| 翁与小莹浴室欢爱51章| avove尤物| 亚洲最大福利视频| 国外AV无码精品国产精品| 欧美日韩亚洲国产一区二区综合| 野花社区在线播放| 一区二区不卡久久精品| 久久免费观看视频| 亚洲乱码一二三四区麻豆| 伊人久久无码中文字幕| 国产91青青成人a在线| 国产精品www| 国产高清在线a视频大全| 男女一进一出猛进式抽搐视频| 成人禁在线观看| 99er在线视频| 四虎国产成人永久精品免费| 国产夫妻在线视频| 大学生秘书胯下吞吐| 小泽玛利亚一区二区| 最近最新视频中文字幕4| 波多野吉衣免费一区| 精品国产精品国产| 色综合久久久久久久| 91在线丨亚洲| 91在线一区二区| 野花香高清在线观看视频播放免费| 精品午夜福利1000在线观看| 露暴的楠楠健身房单车| 福利体验区试看5次专区| 糟蹋顶弄挣扎哀求np| 欧美金发白嫩在线播放| 毛片免费在线观看网址| 波多野结衣中文字幕电影播放| 晚上看b站直播软件| 最近2019中文字幕免费看最新 |