數(shù)據(jù)結(jié)構(gòu)總復(fù)習(xí)(1)(編輯修改稿)
2025-02-16 06:35 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 i+1n， 則結(jié)點(diǎn) i無(wú)右孩子；如果 2i+1?n，則其右孩子是 2i+1 ?二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) ?順序存儲(chǔ)結(jié)構(gòu) ?實(shí)現(xiàn)：按滿(mǎn)二叉樹(shù)的結(jié)點(diǎn)層次編號(hào)，依次存放二叉樹(shù)中的數(shù)據(jù)元素 ?特點(diǎn)： ? 結(jié)點(diǎn)間關(guān)系蘊(yùn)含在其存儲(chǔ)位置中 ? 浪費(fèi)空間，適于存滿(mǎn)二叉樹(shù)和完全二叉樹(shù) a b c d e f g a b c d e 0 0 0 0 f g 1 2 3 4 5 6 7 8 9 10 11 ? P126 有 n個(gè)結(jié)點(diǎn)的二叉鏈表中有 n+1個(gè)空鏈域 ?鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) ?二叉鏈表 typedef struct node { datatype data。 struct node *lchild, *rchild。 }JD。 lchild data rchild A B C D E F G 在 n個(gè)結(jié)點(diǎn)的二叉鏈表中，有 n+1個(gè)空指針域 A B C D E F G ^ ^ ^ ^ ^ ^ ^ ^ ?三叉鏈表 typedef struct node { datatype data。 struct node *lchild, *rchild, *parent。 }JD。 lchild data parent rchild A B C D E F G A B C D E F G ^ ^ ^ ^ ^ ^ ^ ^ ^ ? 二叉樹(shù)的遍歷 ?樹(shù)的遍歷 ?遍歷 —— 按一定規(guī)律走遍樹(shù)的各個(gè)頂點(diǎn)，且使每一頂點(diǎn)僅被訪(fǎng)問(wèn)一次，即找一個(gè)完整而有規(guī)律的走法，以得到樹(shù)中所有結(jié)點(diǎn)的一個(gè)線(xiàn)性排列 ?常用方法 ?先根（序）遍歷：先訪(fǎng)問(wèn)樹(shù)的根結(jié)點(diǎn)，然后依次先根遍歷根的每棵子樹(shù) ?后根（序）遍歷：先依次后根遍歷每棵子樹(shù)，然后訪(fǎng)問(wèn)根結(jié)點(diǎn) ?按層次遍歷：先訪(fǎng)問(wèn)第一層上的結(jié)點(diǎn)，然后依次遍歷第二層， …… 第 n層的結(jié)點(diǎn) ?二叉樹(shù)的遍歷 ?方法 ?先序遍歷：先訪(fǎng)問(wèn)根結(jié)點(diǎn) ,然后分別先序遍歷左子樹(shù)、右子樹(shù) ?中序遍歷：先中序遍歷左子樹(shù)，然后訪(fǎng)問(wèn)根結(jié)點(diǎn)，最后中序遍歷右子樹(shù) ?后序遍歷：先后序遍歷左、右子樹(shù)，然后訪(fǎng)問(wèn)根結(jié)點(diǎn) ?按層次遍歷：從上到下、從左到右訪(fǎng)問(wèn)各結(jié)點(diǎn) D L R LDR、 LRD、 DLR RDL、 RLD、 DRL A D B C D L R A D L R D L R B D C D L R 先序遍歷序列： A B D C 先序遍歷 : A D B C L D R B L D R L D R A D C L D R 中序遍歷序列： B D A C 中序遍歷 : A D B C L R D L R D L R D A D C L R D 后序遍歷序列： D B C A 后序遍歷 : B + / a * b e f c d 先序遍歷 ： 中序遍歷： 后序遍歷： 層次遍歷 ： + a * b c d / e f + a * b c d / e f + a * b c d / e f + a * b c d / e f ? 樹(shù)的存儲(chǔ)結(jié)構(gòu) ?樹(shù)的存儲(chǔ)結(jié)構(gòu) ?雙親表示法 ?實(shí)現(xiàn)：定義結(jié)構(gòu)數(shù)組存放樹(shù)的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)含兩個(gè)域： ? 數(shù)據(jù)域：存放結(jié)點(diǎn)本身信息 ? 雙親域：指示本結(jié)點(diǎn)的雙親結(jié)點(diǎn)在數(shù)組中位置 ?特點(diǎn)：找雙親容易，找孩子難 typedef struct node { datatype data。 int parent。 }PTNode。 typedef struct { PTNode nodes[M]。 int r, n。 }Ptree。 a b c d e f h g i a c d e f g h i b 0 1 2 2 3 5 5 5 1 0 9 6 0 1 2 3 4 5 7 8 9 data parent 0號(hào)單元不用或 存結(jié)點(diǎn)個(gè)數(shù) 如何找孩子結(jié)點(diǎn) ?孩子表示法 ?多重鏈表：每個(gè)結(jié)點(diǎn)有多個(gè)指針域，分別指向其子樹(shù)的根
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1