http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=347#problem/C

这三道题的方法一样,只是调用的函数不同,我采用的方法是先逐层建表向表里面插入元素,然后遍历
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
   int data;
   struct node *lc,*rc;
}btnode;
btnode *q[100];//用指针数组逐个连接每层的结点
int i;
btnode *link_insert(){
 int j,a;
 btnode *p;
 p=(btnode *)malloc(sizeof(btnode));
 scanf("%d",&p->data);
 p->lc=p->rc=NULL;
 q[1]=p;
    for(i=2;scanf("%d",&a)&&a!=-1;i++){//判断是否满足结束条件
        p=(btnode *)malloc(sizeof(btnode));
        q[i]=p;
        p->data=a;
        p->lc=p->rc=NULL;
        for(j=1;j<i;j++){
            if(q[j]->lc==NULL&&q[j]->data!=0){
                q[j]->lc=p;
                break;
            }
            if(q[j]->rc==NULL&&q[j]->data!=0){
                q[j]->rc=p;
                break;
            }
        }
    }
    return q[1];
}
int depth(){//求数的深度
 int dp=1,k;
    for(k=1;dp*2<i-1;k++){
  if(dp*2>=i-1)
           break;
  else
   dp*=2;
 }
 return k;
}
void preorder(btnode *p){//先序遍历
    if(p!=NULL){
        if(p->data!=0)
            printf(" %d",p->data);
        preorder(p->lc);
        preorder(p->rc);
    }
}
void inorder(btnode *p){//中序遍历
    if(p!=NULL){
        inorder(p->lc);
            if(p->data!=0)
                printf(" %d",p->data);
        inorder(p->rc);
 }
}
void postorder(btnode *p){//后序遍历
    if(p!=NULL){
        postorder(p->lc);
        postorder(p->rc);
        if(p->data!=0)
            printf(" %d",p->data);
 }
}
int main(){
   int s,n;
   btnode *p;
   scanf("%d",&n);
   for(s=0;s<n;s++){
    p=link_insert();
    printf("%d",depth());
    preorder(p);或inorder(p);或postorder(p);
    printf("\n");
   }
   return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation