數(shù)據(jù)結(jié)構(gòu)（Python Java）（微課版） 課件 5.3 樹(shù)、森林與二叉樹(shù)

數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)樹(shù)的存儲(chǔ)樹(shù)與二叉樹(shù)的轉(zhuǎn)換森林與二叉樹(shù)的轉(zhuǎn)換樹(shù)的遍歷5.3樹(shù)、森林與二叉樹(shù)樹(shù)的存儲(chǔ)結(jié)構(gòu)特點(diǎn)尋找父結(jié)點(diǎn)只需要O(1)時(shí)間可以從一個(gè)結(jié)點(diǎn)出發(fā)，到其父親，再到其祖父等，從而求出根查詢孩子和兄弟的信息困難雙親表示法樹(shù)的存儲(chǔ)結(jié)構(gòu)4特點(diǎn)孩子結(jié)點(diǎn)的數(shù)據(jù)域存放它們?cè)跀?shù)組中的序號(hào)便于實(shí)現(xiàn)有關(guān)孩子及其子孫的運(yùn)算不便于實(shí)現(xiàn)與雙親有關(guān)的運(yùn)算孩子鏈表表示法樹(shù)的存儲(chǔ)結(jié)構(gòu)雙親孩子鏈表示法樹(shù)的存儲(chǔ)結(jié)構(gòu)孩子兄弟表示法樹(shù)與二叉樹(shù)的轉(zhuǎn)換abcdefhgiba^c^d^e^f^^g^h^i^^abcdefghi^^^^^^^^^^二叉樹(shù)與樹(shù)的相互轉(zhuǎn)換ACBED樹(shù)ABCDE二叉樹(shù)A^^BC^D^^E^A^^BC^D^^E^樹(shù)轉(zhuǎn)二叉樹(shù)①加線：在兄弟之間加一連線。②抹線：對(duì)每個(gè)節(jié)點(diǎn)，除了其第一孩子外，去除其與其余孩子之間的關(guān)系。③調(diào)整：將節(jié)點(diǎn)按層次排列，形成二叉樹(shù)。樹(shù)轉(zhuǎn)換成的二叉樹(shù)其右子樹(shù)一定為空！二叉樹(shù)轉(zhuǎn)樹(shù)①加線：若p節(jié)點(diǎn)是雙親節(jié)點(diǎn)的左孩子，則將p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都與p的雙親用線連起來(lái)②抹線：抹掉原二叉樹(shù)中雙親與右孩子之間的連線③調(diào)整：將節(jié)點(diǎn)按層次排列，形成樹(shù)結(jié)構(gòu)森林轉(zhuǎn)二叉樹(shù)①將各棵樹(shù)分別轉(zhuǎn)換成二叉樹(shù)。②將每棵樹(shù)的根節(jié)點(diǎn)用線相連。③以第一棵樹(shù)根節(jié)點(diǎn)為二叉樹(shù)的根，調(diào)整層次，構(gòu)成二叉樹(shù)形結(jié)構(gòu)。二叉樹(shù)轉(zhuǎn)森林①抹線：將二叉樹(shù)中根節(jié)點(diǎn)與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹(shù)。②還原：將孤立的二叉樹(shù)分別還原成樹(shù)。先序遍歷(與對(duì)應(yīng)的二叉樹(shù)先序遍歷序列一致)若樹(shù)非空，則：訪問(wèn)根結(jié)點(diǎn)依次先序遍歷根的各個(gè)子樹(shù)后序遍歷(與對(duì)應(yīng)的二叉樹(shù)后序遍歷序列一致)若樹(shù)非空，則：依次后序遍歷根的各個(gè)子樹(shù)訪問(wèn)根結(jié)點(diǎn)層次遍歷若樹(shù)非空，訪問(wèn)根結(jié)點(diǎn)。若第1，…i(i≥1)層結(jié)點(diǎn)已被訪問(wèn)，且第i+1層結(jié)點(diǎn)尚未訪問(wèn)，則從左到右依次訪問(wèn)第i+1層。樹(shù)的遍歷樹(shù)的遍歷先序遍歷

A，B，E，F(xiàn)，C，D后序遍歷

E，F(xiàn)，B，C，D，A層次遍歷