注意: 所有問題的代碼都是參考v_JULY_v或您自己編寫的，答案中的分析就是您的想法.

1. 將二叉搜索樹轉(zhuǎn)換為排序的雙向鏈表

標(biāo)題:

輸入二進制搜索樹，然后將二進制搜索樹轉(zhuǎn)換為排序的雙向鏈表.

要求不能創(chuàng)建任何新節(jié)點，只能調(diào)整指針.

10

/ /

6 14

/ / / /

4 8 12 16

轉(zhuǎn)換為雙向鏈接列表

4 = 6 = 8 = 10 = 12 = 14 = 16.

首先，我們定義的二叉搜索樹節(jié)點的數(shù)據(jù)結(jié)構(gòu)如下:

struct BSTreeNode

{

int m_nValue; //節(jié)點的值

BSTreeNode * m_pLeft; //節(jié)點的左子節(jié)點

BSTreeNode * m_pRight; //節(jié)點的右子節(jié)點

};

答案:

在此問題中，我們通過在每次訪問當(dāng)前樹節(jié)點之前記錄最后訪問的節(jié)點來進行修改（因為該節(jié)點是循環(huán)列表中當(dāng)前訪問節(jié)點的前任節(jié)點），以修改二分搜索樹的結(jié)構(gòu)實現(xiàn)兩個結(jié)構(gòu)之間的轉(zhuǎn)換.

在分析此問題期間二叉排序樹查找 算法，我再次深刻理解了樹遍歷的順序. 在預(yù)遍歷過程中，由于當(dāng)前訪問的節(jié)點由其左，右子節(jié)點優(yōu)先二叉排序樹查找 算法，因此訪問該節(jié)點時，無法修改左，右子樹中的指針. 在中階遍歷過程中，由于在訪問當(dāng)前節(jié)點之前已訪問了其左子樹的所有節(jié)點，因此可以修改其左子樹的結(jié)構(gòu)，而不會影響樹的正確中階遍歷行為，但這是仍然無法修改其右側(cè)子樹中節(jié)點的結(jié)構(gòu). 同樣，在后遍歷過程中，由于訪問節(jié)點時已訪問左右子樹，因此修改左右子樹的結(jié)構(gòu)不會影響后續(xù)的樹遍歷行為.

代碼:

本文來自本站，轉(zhuǎn)載請注明本文網(wǎng)址：
http://www.pc-fly.com/a/jisuanjixue/article-257642-1.html