數據結構中樹的遍歷課程設計與實現

田曉輝

（渭南師范學院網絡安全與信息化學院， 陜西渭南 714099）

1 樹形結構

1.1 樹的定義[1]

一棵有根樹T，簡稱為樹，可定義為n(n≥0)個結點的有限集合。當n=0時，T稱為空樹；否則，T是非空樹，記作：

1.2 樹的存儲結構

樹的主要存儲結構有以下三種[2]：

[1]雙親表示法：

用一組連續的空間來存儲樹中的結點，在保存每個結點的同時附設一個指示器來指示其雙親結點在表中的位置。

[2]孩子表示法

把每個結點的孩子結點排列起來，構成一個單鏈表，稱為孩子鏈表。n個結點共有n 個孩子鏈表（葉子結點的孩子鏈表為空表），而 n 個結點的數據和 n個孩子鏈表的頭指針又組成一個順序表。

[3]孩子兄弟表示法

這種表示法又稱為樹的二叉表示法，或者二叉鏈表表示法，即以二叉鏈表作為樹的存儲結構。鏈表中每個結點設有兩個鏈域，分別指向該結點的第一個孩子結點和下一個兄弟（右兄弟）結點。

2 課程設計

2.1 問題描述

給出某操作系統的目錄和文件信息，編程將其以樹狀結構顯示。輸入的信息有兩種，第一種為目錄信息。目錄下面可以存放文件或子目錄，即目錄結點可能存在孩子結點，若存在，其孩子結點信息要求在該目錄信息的下一行給出，孩子結點信息要求用圓括號“（）”括起。目錄的輸入格式為：[目錄名稱]大小。第二種是文件信息。輸入格式為：文件名稱 大小。目錄名或文件名為長度小于等于10的字符串，且目錄名或文件名不能包含‘（’，‘）’和‘*’。目錄的“大小”都表示為 1，文件的“大小”輸入值為文件的實際大小。

編程實現如下輸出，要求是有層次結構的樹，每層結點（目錄結點或文件結點）都要比上一層結點多縮進多個空格。同層目錄或文件結點在同一列顯示。計算所有目錄的大小(為其子目錄大小+子文件大小+1)，并在目錄名和文件后面顯示各自大小。

2.2 算法思想

本文對目錄樹采用孩子兄弟鏈表法結合雙親法的存儲結構，根據輸入的目錄和文件信息，先創建樹，再把孩子兄弟存儲結構的樹以顯式的樹狀結構輸出，每個結點要按其所在層次作相應的縮進。其中，創建樹采用層序遍歷算法實現，輸出樹采用先序遍歷算法實現。若某結點的第一個孩子結點有右孩子結點（兄弟結點），則需要按其所在層次進行縮進后輸出連接符|和多個空格；否則只輸出多個空格；計算某目錄的大小時，為該目錄結點的左子樹（以其第一個孩子為根的樹）所有結點的“大小”的和再加該目錄的“大小”。

3 實現

3.1 樹的存儲結構

在輸出樹結構時，由于先輸出的是同一層結點的第一個結點及其對應的子樹，再輸出同一層結點的第二個結點及其對應的子樹，所以，使用孩子兄弟鏈表存儲結構時，用先序遍歷算法遍歷該結構，剛好可以實現上面的輸出順序的要求；其次，由于每一個目錄結點（雙親結點）下面可能存在子目錄或文件結點（孩子結點），在縮進處理上，輸出子目錄或文件結點信息時，要比其雙親的目錄結點信息縮進更多，為了便于處理縮進，在孩子兄弟存儲結構中增加了parent 域，得到了改進后的孩子兄弟存儲結構[3]。

3.2 關鍵算法的設計

（1）創建樹的改進孩子兄弟存儲結構：

首先讀入根目錄名稱和大小，創建根結點，將根結點的三個指針域置空；

讀入下一行目錄或文件信息并創建結點。創建新結點，該結點是根結點的第一孩子結點，建立其和根結點的鏈接。然后循環做如下的操作：若本行后面還有文件或目錄信息，建立新結點，建立其和雙親結點的鏈接，建立其和前一兄弟結點的鏈接。將該結點的“大小”值加到根結點的“大小”中去。重復該過程，直到本行信息讀取結束。

重復上面的過程，直到整體輸入結束。

(2)輸出樹：

設當前指針（位置）為根目錄，先輸出根結點；

將當前指針改為根結點的第一孩子結點

循環做如下操作：

輸出當前指針對應的結點及其子樹；

將當前指針移向當前指針的下一兄弟結點；

直至當前指針為空。

4 測試

運行程序時，輸入異常的測試數據時，提示“Input Error!”。輸入正確的測試數據：

得到如下圖1所示結果。

圖1 樹型結構

[1]殷人昆.數據結構C語言描述[M].北京:機械工業出版社,2011.6:108-109

[2]耿國華.數據結構(用 C語言描述)[M].北京:高等教育出版社.2016:181-183

[3]何欽銘,陳根才.數據結構課程設計[M].杭州:浙江大學出版社,2015.8:24-41