數(shù)據(jù)結(jié)構(gòu)第一回合：樹

         不管是數(shù)據(jù)結(jié)構(gòu)導(dǎo)論中還是軟考中，樹都是一個很重要的部分，相對來講數(shù)據(jù)結(jié)構(gòu)導(dǎo)論比軟考中要講的相對詳細，下面我就結(jié)合例題對這部分進行一下整合：

          總的來說，結(jié)構(gòu)如下：

         概述部分都是一些基本概念和性質(zhì)的闡釋，森林和二叉樹都特殊形式的樹，判定樹和哈弗曼樹本質(zhì)作為樹的同時，也可以作為樹的應(yīng)用，運用樹（包括二叉樹）的基本知識描述和解決一些實際的問題  。下面就依次來看：

一、二叉樹

       1. 【概況】

           二叉樹有滿，完全、非完全三種情況。所謂滿二叉樹就是一個子結(jié)點都不差，所有的位置該有的都有，如圖：

         這樣一個都不缺的是滿的，假設(shè)現(xiàn)在該二叉樹中缺少了4這一個子結(jié)點，那么就是完全二叉樹，而如果2、4存在，7或者5的位置空了，那么就由一個完全變成不完全了。

完全二叉樹和非完全二叉樹的區(qū)別就是：有缺失的那一層，子結(jié)點的存在是否連續(xù)。

       【例題分析】（出自《數(shù)據(jù)結(jié)構(gòu)導(dǎo)論》125頁 填空第4題）

         已知完全二叉樹的第7層有20個結(jié)點，則整個完全二叉樹的葉子結(jié)點個數(shù)是______.

        [解析] ：因為是一個完全二叉樹，所以在樹的最后一層一定有缺失，也就是說結(jié)點的個數(shù)小于2 的（n-1）次方個。而第6層一 定是滿的，一共有32 個結(jié)點。而根據(jù)題意該

                        樹一共有7層，而且根據(jù)完全二叉樹的性質(zhì)，這20個結(jié)點是第6層的10結(jié)點中的子結(jié)點數(shù)。而第六層剩下的22個結(jié)點都是葉子結(jié)點。

                        所以，該樹的葉子結(jié)點一共有20+22=42個。

 2、樹和二叉樹之間的轉(zhuǎn)換

         在這里咱們用圖說話，這里說的明白。

         1）先將樹上所有的兄弟進行連接，得到原圖右邊的圖：

         2）再保留每一層的兄弟結(jié)點中的第一個作為該層的左子樹結(jié)點，斷開C、D與根結(jié)點的連線，直接將B、C、D作為一條線，以B為中心順時針向旋轉(zhuǎn)45度角，這樣就得到下面的圖：

       其實可以這樣歸結(jié)：當(dāng)所有的兄弟結(jié)點進行連線以后，每一層的所有兄弟結(jié)點中左邊的第一個都作為所有兄弟結(jié)點的父結(jié)點，其他的兄弟結(jié)點保持隊形，以該結(jié)點為中心進行旋轉(zhuǎn)，這樣就得出最終的二叉樹。

二、森林

         森林可以看作實實在在的樹的虛擬化，也是多棵樹組成的。這里知識點主要是和二叉樹之間的轉(zhuǎn)換

         森林和二叉樹之間的轉(zhuǎn)換實際上是對樹和二叉樹之間轉(zhuǎn)換的一種擴展，當(dāng)將各個樹轉(zhuǎn)換為各自對應(yīng)的二叉樹后，將所有的根結(jié)點作為兄弟進行連接，而實現(xiàn)二叉樹到森林的轉(zhuǎn)換就是一個逆過程，這里就不再贅述。

         這本數(shù)據(jù)結(jié)構(gòu)第一遍看的挺亂，聽難的，翻開一看不是圖就是字母，頓時感覺全世界都被這兩個東西充斥了。但終究“眼是狗熊，手是英雄”，所以在學(xué)習(xí)的同時我總結(jié)了數(shù)據(jù)結(jié)構(gòu)的一點學(xué)習(xí)技巧：

      1.實例化

            “此實例化非彼實例化”，這里主要是融入生活，用生活中常見的熟悉的事物來代替或者是幫助理解這些抽象的，空曠的理論結(jié)構(gòu)。

      2.手腦并用            

              這門課中很多知識點都需要另外的思路圖來輔助理解，比如樹、圖、或者指針的指向。這就要求我們手腦并用，用紙上的圖來幫我們理解和解決。

      3.沉心

             面對那些龐雜的專業(yè)名詞，豐富的樹圖都不要畏懼，免得自己心沉。為了不讓自己心沉就必須沉心，要是能鬧明白這兩個詞，那你就"沉心"了:靜下心仔細想想好好理理，其實問題都不是問題。

          這門數(shù)據(jù)結(jié)構(gòu)就是一個紙貓，因為它連老虎也不算，大家加油！

生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機掃描二維碼進行捐贈