二叉搜索树和双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

二叉树可以转换为双向链表，对于一个节点来说右左右两个指针，对于右n个节点的二叉树来说一共有2n个指针，对于n个节点的双向链表存在的指针的数量是中间的2(n-1)加上头尾指针也是2*n个，所以一定可以通过某种方式将二叉树转化为双向链表。转换为双向链表的可以增加访问速度，二叉树的前中后遍历一般采用递归的方式进行，如果树比较庞大尤其是深度比较大的时候耗费的空间比较多。如果每次访问都按照递归方式调用是非常不合理的，简单的排序二叉树 {2,1,3}，其中1，3分别是2的左右节点，这个二叉树的中序遍历是 1,2,3。如果将节点1的right指针指向后继节点2，2的right指针指向后继节点3，三个节点的left指针指向前驱节点就可以转换成双向链表了,以后中序遍历的时候就可以直接访问这个双向链表就可以了，所以在原来树的结构上再增加两个方向指针，代替上面的两个指针指向的前驱和后继，许多书上将类似的操作成为 二叉树的线索化。

二叉搜索树的特点是左边小于中间小于右边，得到排序的双向链表就是将中序遍历线索化，一个非常简单的实现方式就是将中序遍历中的节点依次放在全局数组中，然后遍历数组，然后将数组的相邻元素用right指针连接后面的，用left指针连接前面的就能达到目的,代码如下。

$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);
    }
}