輸入一棵二叉搜索樹，將該二叉搜索樹轉(zhuǎn)換成一個(gè)排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只能調(diào)整樹中結(jié)點(diǎn)指針的指向。

二叉樹可以轉(zhuǎn)換為雙向鏈表，對(duì)于一個(gè)節(jié)點(diǎn)來(lái)說(shuō)右左右兩個(gè)指針，對(duì)于右n個(gè)節(jié)點(diǎn)的二叉樹來(lái)說(shuō)一共有2n個(gè)指針，對(duì)于n個(gè)節(jié)點(diǎn)的雙向鏈表存在的指針的數(shù)量是中間的2(n-1)加上頭尾指針也是2*n個(gè)，所以一定可以通過(guò)某種方式將二叉樹轉(zhuǎn)化為雙向鏈表。轉(zhuǎn)換為雙向鏈表的可以增加訪問速度，二叉樹的前中后遍歷一般采用遞歸的方式進(jìn)行，如果樹比較龐大尤其是深度比較大的時(shí)候耗費(fèi)的空間比較多。如果每次訪問都按照遞歸方式調(diào)用是非常不合理的，簡(jiǎn)單的排序二叉樹 {2,1,3}，其中1，3分別是2的左右節(jié)點(diǎn)，這個(gè)二叉樹的中序遍歷是 1,2,3。如果將節(jié)點(diǎn)1的right指針指向后繼節(jié)點(diǎn)2，2的right指針指向后繼節(jié)點(diǎn)3，三個(gè)節(jié)點(diǎn)的left指針指向前驅(qū)節(jié)點(diǎn)就可以轉(zhuǎn)換成雙向鏈表了,以后中序遍歷的時(shí)候就可以直接訪問這個(gè)雙向鏈表就可以了，所以在原來(lái)樹的結(jié)構(gòu)上再增加兩個(gè)方向指針，代替上面的兩個(gè)指針指向的前驅(qū)和后繼，許多書上將類似的操作成為 二叉樹的線索化。

二叉搜索樹的特點(diǎn)是左邊小于中間小于右邊，得到排序的雙向鏈表就是將中序遍歷線索化，一個(gè)非常簡(jiǎn)單的實(shí)現(xiàn)方式就是將中序遍歷中的節(jié)點(diǎn)依次放在全局?jǐn)?shù)組中，然后遍歷數(shù)組，然后將數(shù)組的相鄰元素用right指針連接后面的，用left指針連接前面的就能達(dá)到目的,代碼如下。

$nodes = array();
function Convert($pRootOfTree)
{
    // write code here
    GLOBAL $nodes;
    $nodes = array();
    inorder($pRootOfTree);
    for($i = 0;$i<count($nodes)-1;$i++){
        $nodes[$i]->right = $nodes[$i+1];
        $nodes[$i+1]->left = $nodes[$i];
    }
    return $nodes[0];
}
function inorder($Root){
    GLOBAL $nodes;
    if($Root==null){
        return;
    }else{
        inorder($Root->left);
        $nodes[] = $Root;
        inorder($Root->right);
    }
}