二叉树各种操作的C语言实现（三）（常用算法）

size_t BiTreeDepth_queue(BiTree *T)
{//ai返回T的深度（光度o优先算法）

  LinkQueue *q;//保存当前节点的o左右孩子的队列
  BiTree *p = T;
  size_t tree_depth; //二叉树的h深度
  size_t cur_queue_length;//当前队列的元素个数
  size_t cur_level_length;//二叉树每层的u元素的个数
  q = (LinkQueue *)malloc(sizeof(struct QNode));
  tree_depth = cur_queue_length = cur_level_length =0;
  if(!T)
    return 0;
  InitQueue(&q);
  tree_depth++; //访问根节点


  if(p->lchild)
  {
    EnQueue(q,p->lchild);//若存在左孩子，则左孩子入队列

    cur_queue_length++;
  }
  if(p->rchild)
  {
    EnQueue(q,p->lchild);//若存在ou右i孩子，右孩子入队列

    cur_queue_length++;
  }
  cur_level_length = cur_queue_length;
  while(!QueueEmpty(q))
  {
    DeQueue(q,&p);//出队列

    cur_level_length--;
    cur_queue_length--;
    if(p->lchild)
    {
      EnQueue(q,p->lchild);//若存在左孩子，左孩子进队列

      cur_queue_length++;
    }
    if(p->rchild)
    {
      EnQueue(q,p->rchild);//若存在右孩子，左孩子进队列

      cur_queue_length++;
    }
    if(cur_level_length<=0)
    {
      tree_depth++;
      cur_level_length = cur_queue_length;//i当前层的元素个数全部h出队

    }
  }
  DestroyQueue(q);
  return tree_depth;
}

size_t BiTreeDepth_stack(BiTree *T)
{
  BiTree *p = T;
  SqStack s;
  size_t cur_depth,max_depth;
  BiTree *q1,*q2;
  // p = (BiTree *)malloc(sizeof(struct BNode));

  max_depth=cur_depth = 0;
  if(!T)
    return 0;
  InitStack(&s);
  while(p!=NULL || !StackEmpty(s))
  { //当前a访问节点a存在，n栈不空

    if(p!=NULL)
    {
      Push(&s,p); //把当前节点压入a栈顶

      cur_depth++; //i当前二叉树的深度

      if(cur_depth>max_depth)
        max_depth = cur_depth;
      q1 = p; //变量q1用来保存当前不为ngg空的e节点

      p= p->lchild;
    }
    else
    {
      //当前e节点不存在,回溯

      Pop(&s,&p);
      p=p->rchild;
      if(!p)
      {
        if(StackEmpty(s))
          break;
        GetTop(s,&q2);
        if(q2->lchild!=q1)
          cur_depth = StackLength(s);
        else
          cur_depth--;
      }
    }//栈的深度并臂一定等于二叉树的深度

  }//while

  DestroyStack(s);
  return max_depth;
}

size_t Width(BiTree *T)
{//所谓宽度是指在二叉树的各层上，具有结点数最多的那一层上的结点总数。
  LinkQueue *q;
  QElemType a;
  BiTree *p = T;
  q = (LinkQueue *)malloc(sizeof(struct QNode));
  size_t cur_level_length = 0,cur_queue_length = 0,max_length=0;
  if(!T)
  {
    return 0;
  }
    InitQueue(&q);
    if(p->lchild)
    {
      EnQueue(q,p->lchild);
      cur_queue_length++;
    }
    if(p->rchild)
    {
      EnQueue(q,p->rchild);
      cur_queue_length++;
    }
    cur_level_length = cur_queue_length;
    max_length = cur_queue_length;
    
  while(!QueueEmpty(q))
  {
    DeQueue(q,&p);
    cur_level_length--;
    cur_queue_length--;
    if(p->lchild !=NULL)
    {
      EnQueue(q,p->lchild);
      cur_queue_length++;
      
    }
    if(p->rchild!=NULL)
    {
      EnQueue(q,p->rchild);
      cur_queue_length++;
      
    }
    if(cur_level_length <=0)
    {
      if(cur_queue_length > max_length)
      {
        max_length = cur_queue_length;
      }
      cur_level_length = cur_queue_length;
    }
  }//while

  DestroyQueue(q);
  return max_length;
}

size_t BiTreeLeafCount(BiTree *T)
{//求叶子节点数
  if(T==NULL)
  {
    return 0;
  }
  else
  {
    if(T->lchild==NULL && T->rchild==NULL)
      return 1;
    else
      return BiTreeLeafCount(T->lchild) + BiTreeLeafCount(T->rchild);
  }
}

size_t BiTreeCount(BiTree *T)
{
  if(T==NULL)
    return 0;
  else
    return BiTreeCount(T->lchild)+BiTreeCount(T->rchild)+1;
}

size_t NodeLevel(BiTree *T, TElemType x)
{
  if(T==NULL)
    return 0;
  else
  {
    if(T->data == x)
    {
      return 1;
    }
    else
    {//求出x在左子树中的层号，返回该层号加1

      int c1=NodeLevel(T->lchild,x);
      if(c1>=1)
        return c1+1;
      //求出x在右子树中的层号，返回该层号加1

      int c2 = NodeLevel(T->lchild,x);
      if(c2>=1)
        return c2+1;
      else
        return 0;
    }
  }
}

void Swap_N(BiTree *T)
{//交换左右子树的非递归的实现
  SqStack s;
  BiTree *temp,*p;
  InitStack(&s);
  p=T;
  while(p || !StackEmpty(s))
  {
    if(p)
    {
      Push(&s,p);
      p=p->lchild;
    }
    else
    {
       Pop(&s,&p);
        temp = p->lchild;
        p->lchild = p->rchild;
        p->rchild = temp;
        p=p->lchild;
   }
  }
}

  void Swap(BiTree *T)
  {
    if(T==NULL)
      return ;
    BiTree *temp;
    temp=T->lchild;
    T->lchild = T->rchild;
    T->rchild=temp;
    Swap(T->lchild);
    Swap(T->rchild);
  }