如何将二叉搜索树转换为一个双向链表（非递归实现）

面试的时候经常会问一些关于二叉树和链表的问题, 这里将自己写的一个二叉树和双向链表的转换贴在这儿。

题目：

输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点，只调整指针的指向。
   
  10
  / \
 6 14
 / \ / \
4 8 12 16
   
 转换成双向链表
4=6=8=10=12=14=16。

 首先我们定义的二元查找树 节点的数据结构如下：

struct TreeNode
{
  int m_nValue;        // value of node
  TreeNode  *left;   // left child of node
  TreeNode  *right; // right child of node
};

分析：

从题目我们可以知道，转换之后的链表实际上是对的原来的二叉排序树的一个中序周游的结果，这样我们就自然而然的能够得出方式： 中序周游树， 并在这个过程之中将指针重置。

下面是该算法的非递归的实现：

//栈，非递归周游的时候需要用到栈。
class Stack
{
private:
    int top;  //栈顶指针
    int size; //栈的大小
    TreeNode **elem; //用指针数组保存栈类的元素。
public:
    Stack(int s = 10) {
        elem = new TreeNode*[s]; //
        size = s;
        top = 0;
    }
    // value of node
    bool isEmpty() {
        return top == 0;
    }
    bool isFull() {
        return top >= size;
    }
    // 增加栈的大小
    void enlarge(int newSize)
    {
        if(newSize <= size ) return;  //如何新的size比原来栈大小还小，直接返回。
        TreeNode **temp = new TreeNode*[newSize];
        for(int i=0; i<top; i++) {
            temp[i] = elem[i];
        }
        delete elem; // 需要将原来的保存栈内元素的空间释放。
        elem = temp;
        size = newSize;
    }

    void push(TreeNode *node)
    {
        if(isFull()) enlarge(size<<1);
        elem[top++] = node;
    }

    TreeNode* pop()
    {
        if(isEmpty()) return NULL;
        TreeNode *temp = elem[--top];
        elem[top] = NULL;
        return temp;
    }

    TreeNode* topValue()
    {
        if(isEmpty()) return NULL;
        return elem[top-1];
    }

    ~Stack()
    {
        delete elem;
    }
};

下面是采用非递归中序周游方法实现转换：

TreeNode * transfer(TreeNode * root)
{
    // left will be used as previous pointer (point to a little one);
    // right will be used as post pointer (point to a large one);
    if (!root) return NULL;
    Stack *s = new Stack();
    TreeNode *curr, *head, *tail;
    curr = root;
    head = NULL, tail=NULL;
    while(true) {
        while(curr) {
            s->push(curr);
            curr = curr->left;
        }

        if(s->isEmpty()) break;
        curr = s->pop();
        //visit(curr);
        //将curr节点加入到双向链表末尾
        if ( head==NULL) { //curr是链表中的第一个节点。
            head = curr;
            tail = curr;
        } else {
            tail->right = curr;
            curr->left = tail;
            tail = curr;  //注意此处不能够修改tail->right指针的值，到目前为止，
                          //当前节点的右子树还未被访问。

        }

        while(!curr->right) {
            if(s->isEmpty()) break;
            curr = s->pop();
            //visit(curr);
            //
            if ( head==NULL) {
                head = curr;
                tail = curr;
            } else {
                tail->right = curr;
                curr->left = tail;
                tail = curr;
            }
        }
        if (curr->right) curr = curr->right;
        else break;
    }

    head->left = NULL;
    tail->right = NULL;
    delete s;
    return head;
}

下面是测试代码：
测试中使用的树为：

     10
   /    \
  5      14
 / \    /  \
4   8  12  16
   /        \
  7          17
 /            \
6             18

void visit(TreeNode *node)
{
    if (node) {
        printf("%d ", node->value);
    }
}

void travelDoubleList(TreeNode* head)
{
    if(head == NULL) return;

    TreeNode *curr;
    printf("Travel from head to tail: \n");

    curr = head;
    visit(curr);
    while(curr->right) {
        curr = curr->right;
        visit(curr);
    }
    printf("\n");

    printf("Travel from tail to head: \n");
    visit(curr);
    while(curr->left) {
        curr = curr->left;
        visit(curr);
    }
    printf("\n");
}

void printTree(TreeNode *node)
{
    if(node){
        printTree(node->left);
        visit(node);
        printTree(node->right);
    }
}

int main(void )
{
    TreeNode *root, *head;
    TreeNode *p[11];
    int value[11] = {10, 5, 14, 4, 8, 12, 16, 7, 17, 6, 18};
    for(int i=0; i<11; i++) {
        p[i] = new TreeNode();
        p[i]->left = NULL;
        p[i]->right = NULL;
        p[i]->value = value[i];
    }
    root = p[0];
    p[0]->left = p[1];
    p[0]->right = p[2];

    p[1]->left = p[3];
    p[1]->right = p[4];
    p[2]->left = p[5];
    p[2]->right = p[6];

    p[4]->left = p[7];
    p[6]->right = p[8];

    p[7]->left = p[9];
    p[8]->right = p[10];

    printf("The binary search tree: \n");
    printTree(root);
    printf("\n\n");

    head = transfer(root);
    travelDoubleList(head);

    for(int i=0; i<11; i++){
        delete p[i];
    }

    system("pause");
    return 0;
}

最后的输出结果：

The binary search tree:
4 5 6 7 8 10 12 14 16 17 18

Travel from head to tail:
4 5 6 7 8 10 12 14 16 17 18
Travel from tail to head:
18 17 16 14 12 10 8 7 6 5 4

附上源代码：
 tree2.zip