数据结构与算法(二叉树实验)

#include <stdio.h>  

#include <stdlib.h>  

#include <string.h>  
  
struct tree_node;  
struct tree_node{  
    struct tree_node *lc;  
    struct tree_node *rc;  
    int id;  
    int index;  
};  
typedef struct tree_node treenode;  

void pre_create_tree(treenode **T){  //递归法  
    
    int datatemp;  
  
    fflush(stdin);  
    scanf("%d", &datatemp);  
  
    if(datatemp==-1){  
        *T=NULL;  
    }  
    else{  
        if((*T=(treenode*)malloc(sizeof(treenode)))==NULL){  
            exit(0);  
        }  
        else{  
            (*T)->id=datatemp;  
            (*T)->lc = (*T)->rc = NULL;  
            pre_create_tree(&(*T)->lc);  
            pre_create_tree(&(*T)->rc);  
        }  
    }  
}  
  
void pre_visit_tree(treenode *T, int *n){  //递归法  
    
    if(T!=NULL){  
        (*n)++;  
        printf("%d ", T->id);  
        pre_visit_tree(T->lc, n);  
        pre_visit_tree(T->rc, n);  
    }  
    else{  
        return;  
    }  
}  
  
typedef struct info{  
    treenode *node;  
    int have_id1;  
    int have_id2;  
}info;  
  
void level_visit_tree(treenode *T, int n, int id1, int id2){  
    info *myinfo, *tt, *temp;  
    treenode *ptemp, *nodetemp;// **temp;  
    
    int k=1, levelcnt=0, cnt, levelcnttemp, prelevelcnt=1;    
    int index=0;  
    
    //levelcnt:当前层元素个数,levelcnttemp:下一层元素个数 
    
    //初始化循环记录  
   
   myinfo = (info*)malloc(sizeof(info)*n);  //记录用数组  
    
    myinfo->node = T;  
    if(T->lc!=NULL)  
        levelcnt++;  
    if(T->rc!=NULL)  
        levelcnt++;  
    temp = myinfo;  
    tt = temp+1;  
    printf("%d ", temp->node->id);  
    T->index = index++;  
    while(levelcnt){   
        //本层没有元素,可以结束循环了  
       
       for(cnt=0, levelcnttemp=0; cnt<levelcnt; ){  //tt:从数组myinfo中指向本层元素,遍历本层元素,有cnt计数,不用怕访问到其它层的元素  
            
            if(temp->node->lc!=NULL){  //打印本层元素的孩子,有则输出孩子值,没有就输出#  
                
                printf("%d ", temp->node->lc->id);  
                (tt+cnt)->node = temp->node->lc;  
                temp->node->lc->index = index++;  
                if((tt+cnt)->node->lc!=NULL)  
                    levelcnttemp++;  
                if((tt+cnt)->node->rc!=NULL)  
                    levelcnttemp++;  
                cnt++;  
            }  
            else  
                printf("# ");  
            if(temp->node->rc!=NULL){  
                printf("%d ", temp->node->rc->id);  
                (tt+cnt)->node = temp->node->rc;  
                temp->node->rc->index = index++;  
                if((tt+cnt)->node->lc!=NULL)  
                    levelcnttemp++;  
                if((tt+cnt)->node->rc!=NULL)  
                    levelcnttemp++;  
                cnt++;  
            }  
            else  
                printf("# ");  
            temp++;  
        }  
        //k=k+levelcnt; 
        
        //k木有用  
        
        tt = tt+cnt;  
        levelcnt=levelcnttemp;  
    }  
    printf("\n");  
  
    for(k=n-1; k>=0; k--){  
        nodetemp = (myinfo+k)->node;  
        (myinfo+k)->have_id1 = 0;  
        (myinfo+k)->have_id2 = 0;  
        if(nodetemp->lc==NULL&&nodetemp->rc==NULL){  
            //这个结点是叶子结点，肯定不是他们两的祖先  
            
            (myinfo+k)->have_id1 = 0;  
            (myinfo+k)->have_id2 = 0;  
        }  
        else{  
            if(nodetemp->lc!=NULL){  
                if((myinfo+nodetemp->lc->index)->have_id1||nodetemp->lc->id==id1)  
                    (myinfo+k)->have_id1 = 1;  
                if((myinfo+nodetemp->lc->index)->have_id2||nodetemp->lc->id==id2){  
                    (myinfo+k)->have_id2 = 1;  
                }  
            }  
            if(nodetemp->rc!=NULL){  
                if((myinfo+nodetemp->rc->index)->have_id1||nodetemp->rc->id==id1)  
                    (myinfo+k)->have_id1 = 1;  
                if((myinfo+nodetemp->rc->index)->have_id2||nodetemp->rc->id==id2){  
                    (myinfo+k)->have_id2 = 1;  
                }  
            }  
        }  
        if((myinfo+k)->have_id1&&(myinfo+k)->have_id2){  
            printf("共同祖先:%d", (myinfo+k)->node->id);  
            break;  
        }  
    }  
    if(k<0)  
        printf("没有共同祖先");  
}  
  
int main(){  
    treenode *mytree;  
    int n=0;  
    int id1, id2;  
      
    printf("输入需要查找公共祖先的id:"); scanf("%d %d", &id1, &id2);
	printf("建树（满二叉先序）");  
    pre_create_tree(&mytree);  
    pre_visit_tree(mytree, &n);  printf("\n");  
    level_visit_tree(mytree, n, id1, id2); printf("\n");  
  
//    system("pause");  

    return 0;  
}