二叉树转双向链表

 1 void ConvertToList(TreeNode*& root) {  
 2   TreeNode* left;  
 3   TreeNode* right;  
 4   if (root) {  
 5     left = root->left_;  
 6     right = root->right_;  
 7     TreeNode* left_most_right = left;  
 8     while (left_most_right && left_most_right->right_) {  
 9       left_most_right = left_most_right->right_;  
10     }  
11     root->left_ = left_most_right;  
12     if (left) {  
13       ConvertToList(left);  
14     }  
15     if (left_most_right) {  
16       left_most_right->right_ = root;  
17     }  
18     TreeNode* right_most_left = right;  
19     while (right_most_left && right_most_left->left_) {  
20       right_most_left = right_most_left->left_;  
21     }  
22     root->right_ = right_most_left;  
23     if (right) {  
24       ConvertToList(right);  
25     }  
26     if (right_most_left) {  
27       right_most_left->left_ = root;  
28     }  
29   }  
30 }

 1 void BiTreeToLinklist(BiTree &T)  // change tree to linklist
 2 {
 3     if(T != NULL) // 双向链表化
 4     {
 5         BiTreeToLinklist(T->lchild);
 6         T->lchild = pre;
 7         pre->rchild = T;
 8         pre = T;
 9         BiTreeToLinklist(T->rchild);
10     }
11 }