C语言二叉树常见操作详解【前序,中序,后序,层次遍历及非递归查

遍历实现

void level_tree(bintree t){
  seqqueue q;
  bintree temp;
  q.front = q.rear = 0;
  if(!t){
    printf("the tree is emptyn");
    return ;
  }
  enter(&q,t);
  while(q.front != q.rear){
    t=del(&q);
    printf("%c ",t->data);
    if(t->lchild){
      enter(&q,t->lchild);
    }
    if(t->rchild){
      enter(&q,t->rchild);
    }
  }
}

//递归调用，不存点，想的时候只关注于一个点，因为还会回来的，不要跟踪程序运行，否则容易多加循环
void createtree(bintree *t){
  datatype c;
  if((c=getchar()) == '#')
    *t = NULL;
  else{
    *t = (bintree)malloc(sizeof(BinNode));
    (*t)->data = c;
    createtree(&(*t)->lchild);
    createtree(&(*t)->rchild);
  }
}

bintree search_tree(bintree t,datatype x){
  if(!t){
    return NULL;
  }
  if(t->data == x){
    return t;
  }else{
    if(!search_tree(t->lchild,x)){
      return search_tree(t->rchild,x);
    }
    return t;
  }
}

int count_tree(bintree t){
  if(t){
    return (count_tree(t->lchild)+count_tree(t->rchild)+1);
  }
  return 0;
}

int is_equal(bintree t1,bintree t2){
  if(!t1 && !t2){   //都为空就相等
    return 1;
  }
  if(t1 && t2 && t1->data == t2->data){   //有一个为空或数据不同就不判断了
    if(is_equal(t1->lchild,t2->lchild))
      if(is_equal(t1->rchild,t2->rchild)){
        return 1;
      }
  }
  return 0;
}

int hight_tree(bintree t){
  int h,left,right;
  if(!t){
    return 0;
  }
  left = hight_tree(t->lchild);
  right = hight_tree(t->rchild);
  h = (left>right?left:right)+1;
  return h;
}