把二叉树转换成双向链表

记得这是一道微软的面试题，想了很长时间不知道怎么做，近期看别人的博客，找到了算法，自己实现了一下，下面是算法的叙述：

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

补充：软件开发 , C++ ,

上一个：POJ 2135 费用流基础
下一个：hdu 1172