[학습 점적 - 데이터 구조 - 이 진 트 리] 이 진 트 리 를 더 블 링크 로 변환 합 니 다.

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define LEAF -1

typedef struct BTreenode{
     BTreenode* lchild;
     BTreenode* rchild;
     int value;       
        
}BTreenode,*Btree;

BTreenode* createTree(){
     BTreenode* T;
     int t;      
     scanf("%d",&t);
     if(t==LEAF){
          T = NULL;
     }else{
          T = (BTreenode *) malloc(sizeof(BTreenode));
          T->value = t;
          T->lchild = createTree();
          T->rchild = createTree();    
     }
     
     return T;
}

void doChange(BTreenode* root,BTreenode * &head,BTreenode* &tail){
     BTreenode * left,*right;
     if(root == NULL){
         head = tail = NULL;
         return;            
     }
     doChange(root->lchild,head,left);
     doChange(root->rchild,right,tail);
     if(left != NULL){
         left->rchild = root;
         root->lchild = left;        
     }else{
         head = root;      
     }
     if(right != NULL){
         root->rchild = right;
         right->lchild = root;         
     }else{
         tail = root;      
     }
     
     
}

BTreenode * TreeToLinkedList(BTreenode* root){
      BTreenode* head = NULL,*tail = NULL;
      doChange(root,head,tail);
      return head;    
}

void preOrder(BTreenode * root){
     if(root!=NULL){
         printf("%d ",root->value);               
     }
     if(root->lchild != NULL){
         preOrder(root->lchild);            
     }
     if(root->rchild !=NULL){
         preOrder(root->rchild);                            
     }
}

void traverse(BTreenode * head){
     printf("traverse: ");
     BTreenode * iter = head;
     while(iter != NULL){
         printf("%d ",iter->value);
         iter = iter->rchild;            
     }
     printf("
");
}

void reTraverse(BTreenode * root){
     printf("reTraverse: ");
     BTreenode * iter = root;
     while(iter!= NULL && iter->rchild != NULL){
         iter = iter->rchild;            
     }
     while(iter!=NULL){
         printf("%d ",iter->value);
         iter = iter->lchild;            
     }
     printf("
");
}
main(){
     BTreenode *root;
     root = createTree();
     preOrder(root);
     printf("
");
     root = TreeToLinkedList(root);
     traverse(root);
     reTraverse(root);
     system("pause");
     return 0; 
       
}

//TODO     2：                   ~~