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