計算機的競爭度逐年加大，報考學生越來越多，對於打算報考2022考研計算機的考生們來說複習是難點，大家複習也需要講究方法，掌握一定的技巧。下面小編整理了2022考研計算機數據結構：樹，供大家參考。
樹
層次：根為第一層，最大層為樹的高度，深度為根到該節點的路徑長度;高度為葉節點到該節點最大路徑
二叉樹性質：
1，二叉樹第i層上的結點數最多為2i-1(i≥1)。
2，深度為k的二叉樹至多有2^k-1個結點(k≥1)
3，在任意-棵二叉樹中，若終端結點的個數為n0，度為2的結點數為n2，則no=n2+1
4，具有n個結點的完全二叉樹的深度為：log2[n](向下)+1或log2[n+1](向上)
二叉樹存儲形式：
1，順序存儲：第i個結點的孩子是2i,2i+1(完全二叉樹適用，如果該樹不是完全二叉樹，需要添加空節點構成完全二叉樹)
2，二叉鍊表結構：左右指針，中間數據|left|data|right|
二叉樹遍歷：
遍歷是樹進行其他運算的基礎，前+中，中+後，層次+中(因為前後可以推出根結點，而中可以推左右)使用遞歸思想來推樹的結構能夠快些
如：前+中
前：GDAFEMHZ中：ADEFGHMZ
步驟：根據前知道root是G，根據中知道左子樹是ADEF,右子樹是HMZ
分析leftTree,由前知道root是D，soleftTreeis:A,andrightTreeis:EF
分析leftTreeA,結束，分析rightTree,From前知道root是F，From中知leftTreeisE
分析rigthTreeHMZ,From前知rootisM,From中知leftTreeisH,andrightTreeisZ
遍歷結束，樹的層次遍歷為GDMAFHZE
如：中+後
中：ADEFGHMZ後：AEFDHZMG
步驟：From後，知道root是G，From中知leftTreeisADEF,rightTreeisHMZ;
分析leftTree:From後知rootisD,From中leftTreeisA,rightTreeisEF;
分析rightTreeEF;From後知：rootisF,From中leftTreeisE;
分析rightTreeHMZ;From後知rootisM，From中leftTreeisH，rightTreeisZ;
遍歷結束，層次遍歷為：GDMAFHZE
線索二叉樹：左右標籤為0，表示左右指針指向左右孩子節點，若為1，指向其左指向前驅，右指向後繼(方便前，中，後遍歷)
樹轉二叉樹：二叉樹左子樹為樹的子節點，右子樹為兄弟，單個樹即只有左側，同樣森林可以是左右子樹的二叉樹
同理二叉樹轉回森林和樹：類似
樹
層次：根為第一層，最大層為樹的高度，深度為根到該節點的路徑長度;高度為葉節點到該節點最大路徑
二叉樹性質：
1，二叉樹第i層上的結點數最多為2i-1(i≥1)。
2，深度為k的二叉樹至多有2^k-1個結點(k≥1)
3，在任意-棵二叉樹中，若終端結點的個數為n0，度為2的結點數為n2，則no=n2+1
4，具有n個結點的完全二叉樹的深度為：log2[n](向下)+1或log2[n+1](向上)
二叉樹存儲形式：
1，順序存儲：第i個結點的孩子是2i,2i+1(完全二叉樹適用，如果該樹不是完全二叉樹，需要添加空節點構成完全二叉樹)
2，二叉鍊表結構：左右指針，中間數據|left|data|right|
二叉樹遍歷：
遍歷是樹進行其他運算的基礎，前+中，中+後，層次+中(因為前後可以推出根結點，而中可以推左右)使用遞歸思想來推樹的結構能夠快些
如：前+中
前：GDAFEMHZ中：ADEFGHMZ
步驟：根據前知道root是G，根據中知道左子樹是ADEF,右子樹是HMZ
分析leftTree,由前知道root是D，soleftTreeis:A,andrightTreeis:EF
分析leftTreeA,結束，分析rightTree,From前知道root是F，From中知leftTreeisE
分析rigthTreeHMZ,From前知rootisM,From中知leftTreeisH,andrightTreeisZ
遍歷結束，樹的層次遍歷為GDMAFHZE
如：中+後
中：ADEFGHMZ後：AEFDHZMG
步驟：From後，知道root是G，From中知leftTreeisADEF,rightTreeisHMZ;
分析leftTree:From後知rootisD,From中leftTreeisA,rightTreeisEF;
分析rightTreeEF;From後知：rootisF,From中leftTreeisE;
分析rightTreeHMZ;From後知rootisM，From中leftTreeisH，rightTreeisZ;
遍歷結束，層次遍歷為：GDMAFHZE
線索二叉樹：左右標籤為0，表示左右指針指向左右孩子節點，若為1，指向其左指向前驅，右指向後繼(方便前，中，後遍歷)
樹轉二叉樹：二叉樹左子樹為樹的子節點，右子樹為兄弟，單個樹即只有左側，同樣森林可以是左右子樹的二叉樹
同理二叉樹轉回森林和樹：類似
收藏