把二叉樹轉換成雙向鏈表

記得這是一道微軟的面試題，想了很長時間不知道怎麼做，近期看別人的博客，找到了算法，自己實現了一下，下面是算法的敘述：

1. If left subtree exists, process the left subtree
…..1.a) Recursively convert the left subtree to DLL.
…..1.b) Then find inorder predecessor of root in left subtree (inorder predecessor is rightmost node in left subtree).
…..1.c) Make inorder predecessor as previous of root and root as next of inorder predecessor.
2. If right subtree exists, process the right subtree (Below 3 steps are similar to left subtree).
…..2.a) Recursively convert the right subtree to DLL.
…..2.b) Then find inorder successor of root in right subtree (inorder successor is leftmost node in right subtree).
…..2.c) Make inorder successor as next of root and root as previous of inorder successor.
3. Find the leftmost node and return it (the leftmost node is always head of converted DLL).

下面給出代碼：

[cpp]
#include<iostream>  
using namespace std; 
 
typedef struct tree_node_s { 
    int data; 
    struct tree_node_s *lchild; 
    struct tree_node_s *rchild; 
}tree_node_t; 
 
 
tree_node_t *changeToListUtil(tree_node_t *root) { 
    if (NULL == root) 
        return NULL; 
    if (root->lchild) { 
        tree_node_t *left = changeToListUtil(root->lchild); 
        while(left->rchild) { 
            left = left->rchild; 
        } 
        root->lchild = left; 
        left->rchild = root; 
    } 
    if (root->rchild) { 
        tree_node_t *right = changeToListUtil(root->rchild); 
        while (right->lchild) { 
            right = right->lchild; 
        } 
        root->rchild = right; 
        right->lchild = root; 
    } 
    return root; 
} 
 
tree_node_t *changeToList(tree_node_t *root) { 
    if (NULL == root) 
        return NULL; 
    root = changeToListUtil(root); 
    while (root->lchild) 
        root = root->lchild; 
    return root; 
} 
 
 
void printList(tree_node_t *head) { 
    while (head) { 
        cout << head->data << " "; 
        head = head->rchild; 
    } 
} 
 
tree_node_t *createNode(int data) { 
    tree_node_t *temp = (tree_node_t*)malloc(sizeof(tree_node_t)); 
    temp->data = data; 
    temp->lchild = NULL; 
    temp->rchild = NULL; 
    return temp; 
} 
 
int main(int argc, char *argv[]) { 
    tree_node_t *root     = createNode(10); 
    root->lchild          = createNode(12); 
    root->rchild          = createNode(15); 
    root->lchild->lchild  = createNode(25); 
    root->lchild->rchild  = createNode(30); 
    root->rchild->lchild  = createNode(36); 
 
    tree_node_t *head = changeToList(root); 
    printList(head); 
    cin.get(); 
    return 0; 
} 

#include<iostream>
using namespace std;

typedef struct tree_node_s {
 int data;
 struct tree_node_s *lchild;
 struct tree_node_s *rchild;
}tree_node_t;

tree_node_t *changeToListUtil(tree_node_t *root) {
 if (NULL == root)
  return NULL;
 if (root->lchild) {
  tree_node_t *left = changeToListUtil(root->lchild);
  while(left->rchild) {
   left = left->rchild;
  }
  root->lchild = left;
  left->rchild = root;
 }
 if (root->rchild) {
  tree_node_t *right = changeToListUtil(root->rchild);
  while (right->lchild) {
   right = right->lchild;
  }
  root->rchild = right;
  right->lchild = root;
 }
 return root;
}

tree_node_t *changeToList(tree_node_t *root) {
 if (NULL == root)
  return NULL;
 root = changeToListUtil(root);
 while (root->lchild)
  root = root->lchild;
 return root;
}

void printList(tree_node_t *head) {
 while (head) {
  cout << head->data << " ";
  head = head->rchild;
 }
}

tree_node_t *createNode(int data) {
 tree_node_t *temp = (tree_node_t*)malloc(sizeof(tree_node_t));
 temp->data = data;
 temp->lchild = NULL;
 temp->rchild = NULL;
 return temp;
}

int main(int argc, char *argv[]) {
 tree_node_t *root     = createNode(10);
    root->lchild          = createNode(12);
    root->rchild          = createNode(15);
    root->lchild->lchild  = createNode(25);
    root->lchild->rchild  = createNode(30);
    root->rchild->lchild  = createNode(36);

 tree_node_t *head = changeToList(root);
 printList(head);
 cin.get();
 return 0;
}