樹的知識點(diǎn)總結(jié)

樹的分類： ??????? 一般樹：任意一個節(jié)點(diǎn)的個數(shù)都不受限制；
??????? 二叉樹：任意一個子結(jié)點(diǎn)的個數(shù)和葉子節(jié)點(diǎn)的個數(shù)最多兩個，且節(jié)點(diǎn)和子節(jié)點(diǎn)位置不可更改； ??? ??????? 森林：n個互不相交的樹的集合；

二叉樹分類： ?????? 一般二叉樹：
?????? 滿二叉樹：在不增加層數(shù)的前提下，無法再增加一個節(jié)點(diǎn)的前提的二叉樹；
?????? 完全二叉樹：如果只刪除了滿二叉樹最底層右邊連續(xù)若干個節(jié)點(diǎn)，這樣形成的二叉樹就是完全二叉樹；
???? 一般樹的儲存： ?????? 雙親表示法：
????? 孩子表示法：
????? 雙親孩子表示法：
????? 二叉樹表示法： ???????????????一般樹的都可以轉(zhuǎn)換成二叉樹再進(jìn)行儲存，轉(zhuǎn)換方法：選擇原來樹的根節(jié)點(diǎn)作為二叉樹的根節(jié)點(diǎn)，轉(zhuǎn)換的二叉樹中任意一個節(jié)點(diǎn)的左指針域指向它的從左至右的第一個孩子，右指針域指向它的兄弟；
二叉樹儲存 ??????連續(xù)存儲（數(shù)組）： ????????????????一般二叉樹要用連續(xù)存儲的方式進(jìn)行儲存，必須將一般二叉樹轉(zhuǎn)化為完全二叉樹，原因：一般二叉樹是非線性的，而電腦的的內(nèi)存是線性的，所以要將非線性轉(zhuǎn)換位線性在電腦中進(jìn)行儲存。如果只再數(shù)組中儲存有效結(jié)點(diǎn)，那么無法將線性轉(zhuǎn)換為非線性（就無法知道二叉樹的實(shí)際結(jié)構(gòu)）。 ????? 鏈?zhǔn)酱鎯Γ??????????????? 一個數(shù)據(jù)兩個指針域
二叉樹的遍歷 ????? 先序遍歷： ???????????????先遍歷根結(jié)點(diǎn)再先序遍歷左子樹，再先序遍歷右子樹； ????? 中序便利： ????????????? 先中序遍歷左字?jǐn)?shù)，再遍歷根結(jié)點(diǎn)，再中序遍歷右子樹； ????? 后序遍歷： ????????????? 先后序遍歷左子樹，再后序遍歷右子樹，再遍歷根幾點(diǎn)；
?已知來兩種序列求原始二叉樹 ?????? 已知先和中可以知道原始二叉樹； ?????? 已知中和后可以知道原始 二叉樹；

還有結(jié)點(diǎn)，葉子結(jié)點(diǎn)，樹的深度，結(jié)點(diǎn)的讀以及樹的度等概念；