3.3 如何從頂部開始逐層打印二叉樹結(jié)點(diǎn)數(shù)據(jù)

難度系數(shù)：★★★☆☆

被考查系數(shù)：★★★★☆

題目描述：

給定一棵二叉樹，要求逐層打印二叉樹結(jié)點(diǎn)的數(shù)據(jù)，例如有如下二叉樹：

對(duì)這棵二叉樹層序遍歷的結(jié)果為1，2，3，4，5，6，7。

分析與解答：

為了實(shí)現(xiàn)對(duì)二叉樹的層序遍歷，就要求在遍歷一個(gè)結(jié)點(diǎn)的同時(shí)記錄下它的孩子結(jié)點(diǎn)的信息，然后按照這個(gè)記錄的順序來訪問結(jié)點(diǎn)的數(shù)據(jù)，在實(shí)現(xiàn)的時(shí)候可以采用隊(duì)列來存儲(chǔ)當(dāng)前遍歷到的結(jié)點(diǎn)的孩子結(jié)點(diǎn)，從而實(shí)現(xiàn)二叉樹的層序遍歷，遍歷過程如下圖所示。

在上圖中，圖（1）首先把根結(jié)點(diǎn)1放到隊(duì)列里面，然后開始遍歷。圖（2）隊(duì)列首元素（結(jié)點(diǎn)1）出隊(duì)列，同時(shí)它的孩子結(jié)點(diǎn)2和結(jié)點(diǎn)3進(jìn)隊(duì)列；圖（3）接著出隊(duì)列的結(jié)點(diǎn)為2，同時(shí)把它的孩子結(jié)點(diǎn)4和結(jié)點(diǎn)5放到隊(duì)列里，依此類推就可以實(shí)現(xiàn)對(duì)二叉樹的層序遍歷。

實(shí)現(xiàn)代碼如下：

測(cè)試數(shù)據(jù)采用了3.2節(jié)所構(gòu)造的數(shù)，程序的運(yùn)行結(jié)果為

算法性能分析：

在二叉樹的層序遍歷過程中，對(duì)樹中的各個(gè)結(jié)點(diǎn)只進(jìn)行了一次訪問，因此，時(shí)間復(fù)雜度為O(n)，此外，這種方法還使用了隊(duì)列來保存遍歷的中間結(jié)點(diǎn)，所使用隊(duì)列的大小取決于二叉樹中每一層中結(jié)點(diǎn)個(gè)數(shù)的最大值。具有N個(gè)結(jié)點(diǎn)的完全二叉樹的深度為h=log2n+1。而深度為h的這一層最多的結(jié)點(diǎn)個(gè)數(shù)為2^h-1=n/2。也就是說隊(duì)列中可能的最多的結(jié)點(diǎn)個(gè)數(shù)為n/2。因此，這種算法的空間復(fù)雜度為O(n)。

引申：用空間復(fù)雜度為O(1)的算法來實(shí)現(xiàn)層序遍歷。

上面介紹的算法的空間復(fù)雜度為O(n)，顯然不滿足要求。通常情況下，提高空間復(fù)雜度都是要以犧牲時(shí)間復(fù)雜度作為代價(jià)的。對(duì)于本題而言，主要的算法思路為：不使用隊(duì)列來存儲(chǔ)每一層遍歷到的結(jié)點(diǎn)，而是每次都會(huì)從根結(jié)點(diǎn)開始遍歷。把遍歷二叉樹的第k層的結(jié)點(diǎn)，轉(zhuǎn)換為遍歷二叉樹根結(jié)點(diǎn)的左右子樹的第k-1層結(jié)點(diǎn)。算法如下：

通過上述算法，可以首先求解出二叉樹的高度h，然后調(diào)用上面的函數(shù)h次就可以打印出每一層的結(jié)點(diǎn)。