第4單元非線性結(jié)構(gòu)一-資料下載頁
2024-09-28 16:09本頁面
【導(dǎo)讀】1)存在唯一的元素沒有前趨,稱為根；3)所有元素，或有若干個互不相同的后繼，樹是一個或多個結(jié)點(diǎn)組成的有限集。0）個互不相交的集。書目錄目錄樹樹結(jié)構(gòu)。兄弟結(jié)點(diǎn)擁有同一父結(jié)點(diǎn)的結(jié)點(diǎn)之間互為。樹的度樹中結(jié)點(diǎn)的最大度數(shù)；上述樹的度為3。有序樹結(jié)點(diǎn)的各子樹看成從左至右有順序且。不能互換，則該樹為有序樹。高度從一結(jié)點(diǎn)到葉結(jié)點(diǎn)的最長路徑為該結(jié)點(diǎn)。刪除結(jié)點(diǎn)x的第i個子樹。樹中各個結(jié)點(diǎn)，且使每個結(jié)點(diǎn)只被訪問一次。普通樹的特殊情況；深度為4,則最多有24-1個結(jié)點(diǎn).y置為x的左孩子。若深度為k的二叉樹T中共有2k-1個。第i個結(jié)點(diǎn)存放在第i個位置；第i層的結(jié)點(diǎn)個數(shù)均為2i-1. 第k層從右邊連續(xù)缺若干個結(jié)點(diǎn)。設(shè)完全二叉樹的結(jié)點(diǎn)總數(shù)為n，深度為k，某結(jié)。2*i+1,否則,i為葉結(jié)點(diǎn).完全二叉樹也可以采用一維樹組作為存儲結(jié)構(gòu),且方法完全同滿二叉樹.
【正文】 (“%d \n”,rootdata)。 if (rootlc!=NULL) preorder_t(rootlc)。 if (rootrc!=NULL) preorder_t(rootrc)。 } } 前序遍歷序列為： A B C D E F A B C D E F 35 /41 樹類的存儲結(jié)構(gòu) ?雙親表示 : 數(shù)組實(shí)現(xiàn) ?孩子表示 : 鏈表實(shí)現(xiàn) ?孩子兄弟表示 : 二叉鏈表實(shí)現(xiàn) 36 /41 一 . 雙親表示法 1 2 3 4 5 6 7 8 9 序號 → 結(jié)點(diǎn) → 雙親 → 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 0 1 1 2 2 3 5 5 5 特點(diǎn)： 找雙親容易，找子結(jié)點(diǎn)難 存儲數(shù)據(jù)元素結(jié)點(diǎn)同時存儲雙親結(jié)點(diǎn)的位置 37 /41 二 . 孩子表示法 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 2 3 NULL 4 5 NULL 6 NULL NULL 7 8 9 NULL 特點(diǎn) : 便于實(shí)現(xiàn)對孩子的操作 ,不便于對父親 的操作 . NULL NULL NULL NULL 為每個結(jié)點(diǎn)的孩子建立一個鏈表 38 /41 三 .孩子兄弟表示法 1 2 3 4 5 6 7 8 9 1 2 NULL 3 7 4 5 6 8 9 左子女右兄弟表示 39 /41 樹、森林轉(zhuǎn)換 成 二叉樹 ? 一 . 樹轉(zhuǎn)換成二叉樹 – 加線 : 連接兄弟結(jié)點(diǎn)； – 抹線 :保留一個結(jié)點(diǎn)的最左子結(jié)點(diǎn) ,抹掉其余兄弟結(jié)點(diǎn)與上級結(jié)點(diǎn)連線； – 以根為軸 ， 順時針旋轉(zhuǎn) 加線 o o o o o o o o o o o o o o o o o o o o o 抹線 旋轉(zhuǎn) o o o o o o o 40 /41 二 . 森林轉(zhuǎn)換成二叉樹 ? 將森林中每棵樹的樹根連接起來； ? 將每棵樹轉(zhuǎn)換成對應(yīng)的二叉樹； ? 以第一棵樹的根為軸順時針旋轉(zhuǎn) o o o o o o o o o o 連線 o o o o o o o o o o 抹線 o o o o o o o o o o 旋轉(zhuǎn) o o o o o o o o o o 41 /41 作業(yè) 本單元 作業(yè)： 課本 88頁 11 題
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1