數(shù)據(jù)結(jié)構(gòu)中樹(shù)的遍歷課程設(shè)計(jì)與實(shí)現(xiàn)

田曉輝

（渭南師范學(xué)院網(wǎng)絡(luò)安全與信息化學(xué)院， 陜西渭南 714099）

1 樹(shù)形結(jié)構(gòu)

1.1 樹(shù)的定義[1]

一棵有根樹(shù)T，簡(jiǎn)稱為樹(shù)，可定義為n(n≥0)個(gè)結(jié)點(diǎn)的有限集合。當(dāng)n=0時(shí)，T稱為空樹(shù)；否則，T是非空樹(shù)，記作：

1.2 樹(shù)的存儲(chǔ)結(jié)構(gòu)

樹(shù)的主要存儲(chǔ)結(jié)構(gòu)有以下三種[2]：

[1]雙親表示法：

用一組連續(xù)的空間來(lái)存儲(chǔ)樹(shù)中的結(jié)點(diǎn)，在保存每個(gè)結(jié)點(diǎn)的同時(shí)附設(shè)一個(gè)指示器來(lái)指示其雙親結(jié)點(diǎn)在表中的位置。

[2]孩子表示法

把每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)排列起來(lái)，構(gòu)成一個(gè)單鏈表，稱為孩子鏈表。n個(gè)結(jié)點(diǎn)共有n 個(gè)孩子鏈表（葉子結(jié)點(diǎn)的孩子鏈表為空表），而 n 個(gè)結(jié)點(diǎn)的數(shù)據(jù)和 n個(gè)孩子鏈表的頭指針又組成一個(gè)順序表。

[3]孩子兄弟表示法

這種表示法又稱為樹(shù)的二叉表示法，或者二叉鏈表表示法，即以二叉鏈表作為樹(shù)的存儲(chǔ)結(jié)構(gòu)。鏈表中每個(gè)結(jié)點(diǎn)設(shè)有兩個(gè)鏈域，分別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟（右兄弟）結(jié)點(diǎn)。

2 課程設(shè)計(jì)

2.1 問(wèn)題描述

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

編程實(shí)現(xiàn)如下輸出，要求是有層次結(jié)構(gòu)的樹(shù)，每層結(jié)點(diǎn)（目錄結(jié)點(diǎn)或文件結(jié)點(diǎn)）都要比上一層結(jié)點(diǎn)多縮進(jìn)多個(gè)空格。同層目錄或文件結(jié)點(diǎn)在同一列顯示。計(jì)算所有目錄的大小(為其子目錄大小+子文件大小+1)，并在目錄名和文件后面顯示各自大小。

2.2 算法思想

本文對(duì)目錄樹(shù)采用孩子兄弟鏈表法結(jié)合雙親法的存儲(chǔ)結(jié)構(gòu)，根據(jù)輸入的目錄和文件信息，先創(chuàng)建樹(shù)，再把孩子兄弟存儲(chǔ)結(jié)構(gòu)的樹(shù)以顯式的樹(shù)狀結(jié)構(gòu)輸出，每個(gè)結(jié)點(diǎn)要按其所在層次作相應(yīng)的縮進(jìn)。其中，創(chuàng)建樹(shù)采用層序遍歷算法實(shí)現(xiàn)，輸出樹(shù)采用先序遍歷算法實(shí)現(xiàn)。若某結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)有右孩子結(jié)點(diǎn)（兄弟結(jié)點(diǎn)），則需要按其所在層次進(jìn)行縮進(jìn)后輸出連接符|和多個(gè)空格；否則只輸出多個(gè)空格；計(jì)算某目錄的大小時(shí)，為該目錄結(jié)點(diǎn)的左子樹(shù)（以其第一個(gè)孩子為根的樹(shù)）所有結(jié)點(diǎn)的“大小”的和再加該目錄的“大小”。

3 實(shí)現(xiàn)

3.1 樹(shù)的存儲(chǔ)結(jié)構(gòu)

在輸出樹(shù)結(jié)構(gòu)時(shí)，由于先輸出的是同一層結(jié)點(diǎn)的第一個(gè)結(jié)點(diǎn)及其對(duì)應(yīng)的子樹(shù)，再輸出同一層結(jié)點(diǎn)的第二個(gè)結(jié)點(diǎn)及其對(duì)應(yīng)的子樹(shù)，所以，使用孩子兄弟鏈表存儲(chǔ)結(jié)構(gòu)時(shí)，用先序遍歷算法遍歷該結(jié)構(gòu)，剛好可以實(shí)現(xiàn)上面的輸出順序的要求；其次，由于每一個(gè)目錄結(jié)點(diǎn)（雙親結(jié)點(diǎn)）下面可能存在子目錄或文件結(jié)點(diǎn)（孩子結(jié)點(diǎn)），在縮進(jìn)處理上，輸出子目錄或文件結(jié)點(diǎn)信息時(shí)，要比其雙親的目錄結(jié)點(diǎn)信息縮進(jìn)更多，為了便于處理縮進(jìn)，在孩子兄弟存儲(chǔ)結(jié)構(gòu)中增加了parent 域，得到了改進(jìn)后的孩子兄弟存儲(chǔ)結(jié)構(gòu)[3]。

3.2 關(guān)鍵算法的設(shè)計(jì)

（1）創(chuàng)建樹(shù)的改進(jìn)孩子兄弟存儲(chǔ)結(jié)構(gòu)：

首先讀入根目錄名稱和大小，創(chuàng)建根結(jié)點(diǎn)，將根結(jié)點(diǎn)的三個(gè)指針域置空；

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

重復(fù)上面的過(guò)程，直到整體輸入結(jié)束。

(2)輸出樹(shù)：

設(shè)當(dāng)前指針（位置）為根目錄，先輸出根結(jié)點(diǎn)；

將當(dāng)前指針改為根結(jié)點(diǎn)的第一孩子結(jié)點(diǎn)

循環(huán)做如下操作：

輸出當(dāng)前指針對(duì)應(yīng)的結(jié)點(diǎn)及其子樹(shù)；

將當(dāng)前指針移向當(dāng)前指針的下一兄弟結(jié)點(diǎn)；

直至當(dāng)前指針為空。

4 測(cè)試

運(yùn)行程序時(shí)，輸入異常的測(cè)試數(shù)據(jù)時(shí)，提示“Input Error!”。輸入正確的測(cè)試數(shù)據(jù)：

得到如下圖1所示結(jié)果。

圖1 樹(shù)型結(jié)構(gòu)

[1]殷人昆.數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言描述[M].北京:機(jī)械工業(yè)出版社,2011.6:108-109

[2]耿國(guó)華.數(shù)據(jù)結(jié)構(gòu)(用 C語(yǔ)言描述)[M].北京:高等教育出版社.2016:181-183

[3]何欽銘,陳根才.數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)[M].杭州:浙江大學(xué)出版社,2015.8:24-41