[計(jì)算機(jī)軟件及應(yīng)用]ch(編輯修改稿)
2024-11-12 23:09 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 ? ③ 先序遍歷右子樹。 二叉樹 ? （ 2）中序遍歷二叉樹 ? 若二叉樹非空，則依次進(jìn)行如下操作： ? ① 中序遍歷左子樹； ? ② 訪問(wèn)根結(jié)點(diǎn)； ? ③ 中序遍歷右子樹。 二叉樹 ? （ 3）后序遍歷二叉樹 ? 若二叉樹非空，則依次進(jìn)行如下操作： ? ① 后序遍歷左子樹； ? ② 后序遍歷右子樹； ? ③ 訪問(wèn)根結(jié)點(diǎn)。 二叉樹 ? 2. 二叉樹遍歷的非遞歸實(shí)現(xiàn) ? 對(duì)于非遞歸算法，引入棧模擬遞歸形式，初始時(shí)棧為空。 ? （ 1）先序遍歷的非遞歸實(shí)現(xiàn) ? 思路：訪問(wèn) btdata后，將 bt入棧，遍歷左子樹；遍歷完左子樹返回時(shí)，棧頂元素應(yīng)為 bt，出棧，再先序遍歷 bt的右子樹。 二叉樹 ? （ 2）中序遍歷非遞歸實(shí)現(xiàn) ? 思路：先將 bt入棧，遍歷左子樹；遍歷完左子樹返回時(shí)，棧頂元素應(yīng)為 bt，出棧，訪問(wèn) btdata，再中序遍歷 bt的右子樹。 ? （ 3）后序遍歷非遞歸實(shí)現(xiàn) ? 思路：可采用標(biāo)記法，結(jié)點(diǎn)入棧時(shí)，配一個(gè)標(biāo)志tag一同入棧（ 0：遍歷左子樹前的現(xiàn)場(chǎng)保護(hù)， 1：遍歷右子樹前的現(xiàn)場(chǎng)保護(hù)）。首先將 T和 tag（為 0）入棧，遍歷左子樹；返回后，修改棧頂 tag為 1，遍歷右子樹；最后訪問(wèn)根結(jié)點(diǎn)。 二叉樹 ? （ 4）層次遍歷二叉樹 ? 所謂二叉樹的層次遍歷，是指從二叉樹的第一層（根結(jié)點(diǎn)）開始，從上至下逐層遍歷，在同一層中，則按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問(wèn)。由層次遍歷的定義可以推知，在進(jìn)行層次遍歷時(shí)，對(duì)一層結(jié)點(diǎn)訪問(wèn)完后，再按照它們的訪問(wèn)次序?qū)Ω鱾€(gè)結(jié)點(diǎn)的左孩子和右孩子順序訪問(wèn)，這樣一層一層進(jìn)行，先遇到的結(jié)點(diǎn)先訪問(wèn)，這與隊(duì)列的操作原則比較吻合。 二叉樹 ? 因此，在進(jìn)行層次遍歷時(shí)，可設(shè)置一個(gè)隊(duì)列結(jié)構(gòu)，遍歷從二叉樹的根結(jié)點(diǎn)開始，首先將根結(jié)點(diǎn)指針入隊(duì)列，然后從隊(duì)頭取出一個(gè)元素，每取一個(gè)元素，執(zhí)行下面兩個(gè)操作： ? ① 訪問(wèn)該元素所指結(jié)點(diǎn)； ? ② 若該元素所指結(jié)點(diǎn)的左、右孩子結(jié)點(diǎn)非空，則將該元素所指結(jié)點(diǎn)的左孩子指針和右孩子指針順序入隊(duì)。 ? 此過(guò)程不斷進(jìn)行，當(dāng)隊(duì)列為空時(shí)，二叉樹的層次遍歷結(jié)束。 樹和森林 ? 樹的存儲(chǔ)結(jié)構(gòu) ? 1. 雙親表示法 ? 設(shè)以一組地址連續(xù)的空間存放樹的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)中除了存放結(jié)點(diǎn)的信息外，增設(shè)一個(gè)整型指針域，指示其雙親結(jié)點(diǎn)所在的位置序號(hào)。這樣的存儲(chǔ)結(jié)構(gòu)稱之為靜態(tài)鏈表結(jié)構(gòu)。這樣的靜態(tài)鏈表可反映出一棵樹中結(jié)點(diǎn)之間的邏輯關(guān)系，即可惟一地表示一棵樹，稱之為雙親表示法。 樹和森林 ? 2. 孩子表示法 ? 孩子表示法是把每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)鏈接形成單鏈表，n個(gè)結(jié)點(diǎn)有 n個(gè)孩子鏈表（葉子結(jié)點(diǎn)的孩子鏈表為空）。n個(gè)結(jié)點(diǎn)的信息和指向孩子鏈表的指針作為表頭結(jié)點(diǎn)組成一個(gè)表頭向量，采用順序存儲(chǔ)結(jié)構(gòu)。與雙親表示法相反，孩子表示法便于查找樹中某結(jié)點(diǎn)的孩子，由表中某結(jié)點(diǎn)的指針域 headptr即可得到該結(jié)點(diǎn)的孩子結(jié)點(diǎn)。 樹和森林 ? 3. 孩子兄弟表示法 ? 孩子兄弟表示法又稱二叉樹表示法，即以二叉鏈表作為樹的存儲(chǔ)結(jié)構(gòu)。鏈表中每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)相同，都有三個(gè)域：數(shù)據(jù)域存放樹中結(jié)點(diǎn)的信息，孩子域存放該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)（從左算起）的地址，兄弟域存放該結(jié)點(diǎn)的下一個(gè)兄弟結(jié)點(diǎn)（從左向右）的地址。 ? 樹、森林、二叉樹的轉(zhuǎn)換 ? 1. 樹轉(zhuǎn)換成二叉樹 樹和森林 ? 將一棵樹轉(zhuǎn)換為二叉樹的方法是： ? （ 1）樹中所有相鄰兄弟之間加一條連線。 ? （ 2）對(duì)樹中的每個(gè)結(jié)點(diǎn)，只保留它與第一個(gè)孩子 結(jié)點(diǎn)之間的連線，刪去它與其它孩子結(jié)點(diǎn)之 間的連線。 ? （ 3）以樹的根結(jié)點(diǎn)為軸心，將整棵樹順時(shí)針轉(zhuǎn)動(dòng)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1