【正文】 lchild rchild info 圖 二叉樹結(jié)點(diǎn) 二叉樹的概念（選讀） 二叉樹類結(jié)點(diǎn)類模板定義： templatetypename Tclass BinaryTree。 1 2 3 4 5 6 7 9 8 10 11 14 13 12 15 圖 滿二叉樹 1 2 3 4 5 6 7 9 8 10 圖 完全二叉樹 二叉樹的概念（選讀） 下面給出鏈?zhǔn)絻Υ娣绞降亩鏄洹? 解：結(jié)果見圖 ， 共 5種 。 二叉樹的基本性質(zhì)： 1．二叉樹的第 i層上最多有 2i1(i=1)個(gè)結(jié)點(diǎn)； 2．深度為 h的二叉樹中最多有 2h1個(gè)結(jié)點(diǎn)； 3．在任一棵二叉樹中，有 n0個(gè)葉子結(jié)點(diǎn)，有 n2個(gè)度為 2的 結(jié)點(diǎn)，則有 n0=n2+1。 這也是一個(gè)遞歸的定義 。 樹的術(shù)語： 二叉樹的概念（選讀） 二叉樹 （ Binary Tree） 是另一種獨(dú)立的樹形結(jié)構(gòu) 。 樹的深度 ,樹中結(jié)點(diǎn)的層次數(shù) 。 兄弟結(jié)點(diǎn) ， 同一雙親的結(jié)點(diǎn)互稱為兄弟 。 孩子結(jié)點(diǎn) ， 若結(jié)點(diǎn) x有子樹 ， 則子樹根結(jié)點(diǎn)即為 x的孩子結(jié)點(diǎn) 。 葉結(jié)點(diǎn) ， 度為 0的結(jié)點(diǎn) ，如 G， I， J， K， L，M， N， O結(jié)點(diǎn) 。 樹的概念： 二叉樹的概念（選讀） A B C D E F G I H J L K O N M ………… 0層 …… 1層 2層 3層 深度 圖 樹的示意圖 結(jié)點(diǎn) ， 包括數(shù)據(jù)項(xiàng)和多個(gè)指針項(xiàng) ， 指針項(xiàng)數(shù)目并不固定 ， 且無次序 。每棵子樹的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但可以有 0個(gè)或多個(gè)直接后繼。非空樹有一個(gè)特定的結(jié)點(diǎn)，它只有直接后繼，沒有直接前驅(qū)，稱之為根（ root）。 二叉樹的遍歷 二叉樹的概念 排序二叉樹 二叉樹的概念 （選讀） 樹（ Tree） 是由 n（ n≥0）個(gè)結(jié)點(diǎn)組成的有限集合。無鏈表頭結(jié)點(diǎn)方式。 【 例 】 鏈隊(duì)類模板。若想利用這個(gè)空間，必然加一個(gè)標(biāo)志來表示隊(duì)空 /隊(duì)滿，進(jìn)隊(duì)出隊(duì)都要判斷，使用上更不方便。 順序表隊(duì)列的缺點(diǎn)： 隊(duì)列 順序表隊(duì)列的改進(jìn)： 邏輯上的循環(huán)隊(duì)列 注意，空隊(duì)時(shí) rear=front，滿隊(duì)時(shí)必須空一個(gè)位置 隊(duì)列 循環(huán)隊(duì)列 浪費(fèi)一個(gè)位置好像太可惜，特別在該位置中存放一個(gè)很大的對象時(shí)。 a0 a1 a2 … an1 … front 元素移動方向 rear 圖 圖 ，隊(duì)尾 (rear)不斷向后移；而隨隊(duì)頭元素的出隊(duì)，則隊(duì)頭 (front)也不斷后移，即 位置在變 （如要位置不變， 移動元素 工作量也太大）。每次在隊(duì)尾加入新元素，加入稱為 進(jìn)隊(duì) ，刪除稱為 出隊(duì) 。它 只允許在表的一端插入，而在另一端刪除 。 }。 //取數(shù) void Compute(char Opr)。Num1,int amp。 void Cal(void)。 //使用鏈棧 Stackchar Ostack。 使用 ‘ z’字符表示結(jié)束 。 棧的應(yīng)用（選讀） 【 例 】 模擬簡單計(jì)算器 ， 該計(jì)算器只認(rèn) + * / 四個(gè)運(yùn)算符 ，輸入為整數(shù) 。繼續(xù)掃描，直到遇到＝號，掃描結(jié)束。 從左向右掃描算術(shù)表達(dá)式 ，遇到 操作數(shù) ， 壓入數(shù)棧 ；遇到 運(yùn)算符 ，則 與運(yùn)算符棧棧頂?shù)倪\(yùn)算符比較優(yōu)先級 ，若新的運(yùn)算符優(yōu)先級高，或運(yùn)算符棧空，則壓棧。數(shù)棧暫存操作數(shù)，運(yùn)算符棧暫存運(yùn)算符?，F(xiàn)考慮最簡單的 +、 、 *、 /四個(gè)運(yùn)算符和結(jié)束符＝組成的算術(shù)表達(dá)式，只有 兩個(gè)優(yōu)先級 ，先 */，后 +。 鏈棧內(nèi)存空間隨用隨開，不會溢出，但執(zhí)行復(fù)雜（不斷地動態(tài)分配），速度慢。 棧的應(yīng)用（選讀） 順序棧和鏈棧邏輯功能是一樣，盡管這里兩個(gè)棧模板的成員函數(shù)功能選擇稍有出入，因?yàn)?順序?？梢噪S機(jī)訪問其中的元素 ， 而鏈棧只能順序訪問， 但邏輯上完全可以做到一樣（物理結(jié)構(gòu)不同） 。 //清空棧 bool IsEmpty(){return top==NULL。 //彈出 T GetTop()。data)。} ~Stack()。 top …… ^ …… 鏈棧 棧 鏈棧類模板 (無頭結(jié)點(diǎn)鏈表 )： templatetypename Tclass Stack{ //鏈棧類模板 NodeT *top。 } friend class StackT。 public: Node(T data=0,NodeT *next=NULL){ info=data。 //下溢出 } 棧 【 例 】 鏈棧的 結(jié)點(diǎn) 類模板： templatetypename Tclass Node{ //鏈棧結(jié)點(diǎn)類模板 T info。 //注意先進(jìn)后出 coutendl。i++) coutb[i]39。 for(i=0。i++) b[i]=()。 for(i=0。 if(()) cout棧滿 endl。i10。 Stackint istack(10)。 }。} //判?？? bool IsFull() const{return top==maxSize1。 //取數(shù)據(jù) ， top不變 void MakeEmpty(){top= 1。 //壓棧 T Pop()。} void Push(const T amp。 //棧最大容納的元素個(gè)數(shù) public: Stack(int=20)。 //棧頂指針（下標(biāo)） T *elements。通常只有棧頂與操作有關(guān)。 a0 an2 …… a1 an1 bottom 進(jìn)棧 top top top top top 出棧 圖示為順序棧。進(jìn)棧時(shí)最先進(jìn)棧的 a0在最下面， an1在最上面。 ?？梢杂庙樞虮韺?shí)現(xiàn)，稱 順序 棧；也可以用鏈表實(shí)現(xiàn)，稱 鏈棧 。而出棧時(shí)順序相反，最后進(jìn)棧的最先出棧，而最先進(jìn)棧的最后出棧。 棧中沒有任何元素時(shí)，稱為空棧。 7. 3. 1 棧 7. 3. 3 隊(duì) 列 7. 3. 2 棧的應(yīng)用（選讀） 棧 棧的基本概念： 棧定義為只允許在表的一端進(jìn)行插入和刪除的線性表 。 p llink rlink rlink llink rlink 前驅(qū)結(jié)點(diǎn) llink 本結(jié)點(diǎn) 后繼結(jié)點(diǎn) 間接訪問符的使用 【 例 】 雙向鏈表類模板和結(jié)點(diǎn)類模板。 info0 infon1 .’.’.’.’.’.’ info1 head (a) 非空表 head (b)空表 雙向鏈表（選讀） 雙向鏈表的訪問： 假設(shè)指針 p指向雙向循環(huán)鏈表的某一個(gè)結(jié)點(diǎn)，那么， pllink指示 P所指結(jié)點(diǎn)的 前驅(qū)結(jié)點(diǎn) ， prlink指示 后繼結(jié)點(diǎn)。雙向鏈表的 結(jié)點(diǎn)有三個(gè)域 ： 左鏈接指針（ llink)， 數(shù)據(jù)域（ info)， 右鏈接指針域 (rlink)。如要找前驅(qū)，必須從表頭開始搜索?？紤]到函數(shù)的參數(shù)和返回值僅使用指向 Node的指針，定義復(fù)制構(gòu)造函數(shù)已經(jīng)沒有實(shí)際意義 單鏈表的復(fù)制構(gòu)造函數(shù)和復(fù)制運(yùn)算符是一個(gè)復(fù)雜的算法，與前文所編的復(fù)制構(gòu)造函數(shù)和復(fù)制運(yùn)算符構(gòu)造相去甚遠(yuǎn)了。 } link域值為 NULL。 node){ info=。 定義復(fù)制構(gòu)造函數(shù)與類的實(shí)際意義和使用方式有關(guān)，并非只是深復(fù)制和淺復(fù)制的問題 。 【 例 】 以學(xué)生類作為鏈表的數(shù)據(jù)類，完成學(xué)生檔案的管理。 清空該表 ， 再按升序生成鏈表并輸出 。 //刪除指定結(jié)點(diǎn) 單鏈表類型模板 單鏈表類型模板 【 例 】 由鍵盤輸入 16個(gè)整數(shù) ， 以這些整數(shù)作為結(jié)點(diǎn)數(shù)據(jù) ， 生成兩個(gè)鏈表 ， 一個(gè)向前生成 ， 一個(gè)向后生成 ， 輸出兩個(gè)表 。 //創(chuàng)建結(jié)點(diǎn) (孤立結(jié)點(diǎn) ) NodeT*DeleteNode(NodeT* p)。 //可用來 向后生成鏈表 void InsertOrder(NodeT *p)。 //打印鏈表 的數(shù)據(jù)域 void InsertFront(NodeT* p)。 //搜索 數(shù)據(jù)域與 data相同的結(jié)點(diǎn)，返回該結(jié)點(diǎn)的地址 int Length()。 //析構(gòu)函數(shù) void MakeEmpty()。 //鏈表頭指針和尾指針 public: List()。 //以 List為友元類， List可直接訪問 Node的私有函數(shù) }。 //在當(dāng)前 結(jié)點(diǎn)后插入 一個(gè)結(jié)點(diǎn) NodeT* RemoveAfter()。 data)。 //指針域，注意結(jié)點(diǎn)類格式，尖括號中是參數(shù)名表，類模板實(shí)例化為類 public: Node()。//前向引用聲明 templatetypename Tclass Node{ T info。 } 單鏈表類型模板 【 例 】 單鏈表類模板 。 delete q。 q=plink。 plink=q。 qinfo=x。 4. 在單鏈表的 p結(jié)點(diǎn)后插入 ： 注意只有一種情況。 //借助工作指針順序訪問鏈表各結(jié)點(diǎn)是鏈表最基礎(chǔ)的算法return p。amp。} 單鏈表基本算法 (按關(guān)鍵字 )查找： node *traversal(node *head,Datatype data){ node *p=headlink。 //新結(jié)點(diǎn)放在原鏈表前方 headlink=p。 pinfo=data。 //建立頭結(jié)點(diǎn) headlink=NULL。 Datatype data。 //鏈尾加空指針 ， 表示鏈結(jié)束 return head。 //新結(jié)點(diǎn)接到鏈尾 tail=p。 //每輸入一個(gè)數(shù)申請一個(gè)結(jié)點(diǎn) pinfo=data。 //建立鏈表頭結(jié)點(diǎn) tail=head。 Node*head,*tail,*p。 空表如下： head info0 Infon1 ^ info1 … head ^ 下面分別介紹 帶表頭結(jié)構(gòu) 的鏈表的生成鏈表算法、鏈表查找算法、插入一個(gè)結(jié)點(diǎn)的算法和刪除一個(gè)結(jié)點(diǎn)的算法。 單鏈表基本算法 帶表頭結(jié)構(gòu)的鏈表： 研究以上算法 ， 插在鏈表第一個(gè)結(jié)點(diǎn)之前與其他結(jié)點(diǎn)之前的算法有所不同 。 即： newnode→ link=head； //注意：鏈表操作次序非常重要 head=newnode； 單鏈表基本算法 infox infoi1 infoi p ｑ newnode 插在中間： 首先用工作指針 p找到指定結(jié)點(diǎn) ， 而讓指針 q指向緊跟其后的結(jié)點(diǎn) ， 令 infoi1所在結(jié)點(diǎn)的 link指針指向新結(jié)點(diǎn) ， 而后讓新結(jié)點(diǎn)的 link指向 infoi所在結(jié)點(diǎn) 。 單鏈表基本算法 newnode infox info0 info1 單鏈表基本算法 單鏈表的插入與刪除： 只要改變鏈中結(jié)點(diǎn)指針的值，無需移動表中的元素，就能實(shí)現(xiàn)插入和刪除操作。 在 C/C++中允許結(jié)構(gòu)（或?qū)ο螅┏蓡T是 結(jié)構(gòu)自身的指針類型 ，通過指針引用自身這種類型的結(jié)構(gòu)。 node *link。 單鏈表基本算法 結(jié)點(diǎn)定義如下： typedef int Datatype。 借助結(jié)點(diǎn)的指針域，可以從第一個(gè)結(jié)點(diǎn)開始順序遍歷鏈表所有結(jié)點(diǎn)。 一個(gè)結(jié)點(diǎn)包含兩個(gè)域 ， 一個(gè)域存放數(shù)據(jù)元素 info， 其數(shù)據(jù)類型由應(yīng)用問題決定；另一個(gè)存放指向該鏈表中下一個(gè)結(jié)點(diǎn)的指針 link。而線性表的 物理結(jié)構(gòu) 包括：順序表， 鏈表 。 鏈表與鏈表的基本操作 線性表 是最簡單，最常用的一種數(shù)據(jù)結(jié)構(gòu)。這樣的類對象，作為另一個(gè)類的成員對象使用時(shí)，就不會出任何問題。在需要時(shí)可以無條件地安全使用。 淺復(fù)制與深復(fù)制 探討： 最后進(jìn)一步討論類的封裝。也就是說， 動態(tài)內(nèi)存分配和深復(fù)制應(yīng)該放在一個(gè)適當(dāng)?shù)膶用嫔?，一個(gè)更單純的類定義中，如 string類。