二叉树各种操作的C语言实现（-）

    这里主要是二叉树的各种C语言实现，二叉树的许多的实现，都是要借助前面的队列和栈的实现，例如各种遍历的非递归的实现，层次遍历等等。
首先是定义的树的数据结构：

typedef struct BiTNode
{
  TElemType data;
  struct BiTNode *lchild;
  struct BiTNode *rchild;
}BiTNode,BiTree,*BiTree_1;

下面是树的一些基本的操作，包括，树的建立，树的深度，树的各种遍历的递归和非递归实现;

Status InitBiTree(BiTree **T)
{//构造空二叉树

  (*T)=NULL;
  return OK;
}

void DestroyBiTree(BiTree **T)
{//销毁二叉树

  if(*T)
  {
    if((*T)->lchild)
      DestroyBiTree(&((*T)->lchild));
    if((*T)->rchild)
      DestroyBiTree(&((*T)->rchild));
    free(*T);
    (*T)=NULL;
  }
}

void CreateBiTree(BiTree **T)
{// 按先序次序输入二叉树中节点的值，构造二叉链表示的二叉树T

  TElemType ch;
#ifdef CHAR
  scanf("%c",&ch);
#endif
#ifdef INT
  scanf("%d",&ch);
#endif
  if(ch=='#')
    (*T) = 0;
  else
  {
    (*T)=(BiTree *)malloc(sizeof(struct BiTNode));
    if(!(*T))
      exit(OVERFLOW);
    (*T)->data = ch;
    CreateBiTree(&((*T)->lchild));//构造左子树
    CreateBiTree(&((*T)->rchild));//构造右子树

  }
}

Status BiTreeEmpty(BiTree *T)
{ //判断二叉树是否为空

  if(T)
    return FALSE;
  else
    return TRUE;
}

#define ClearBiTree DestroyBiTree
int BiTreeDepth(BiTree *T)
{//返回T的深度

  int i,j;
  if(!T)
    return 0;
  if(T->lchild)
    i=BiTreeDepth(T->lchild);
  else
    i=0;
  if(T->rchild)
    j= BiTreeDepth(T->rchild);
    else
      j = 0;
  return i>j?i+1:j+1;
}

TElemType Root(BiTree *T)
{// 返回T的根

  if(BiTreeEmpty(T))
    return Nil;
  else
    return T->data;
}

TElemType Value(BiTree *p)
{//p指向T的某个节点，返回p所指向的节点的值

  return (p->data);
}

void Assign(BiTree *p,TElemType value)
{ //给p所值的节点赋值 value

  p->data = value;
}

typedef BiTree_1 QElemType;
#include "Queue.h"
#include "Queue.c"
TElemType Parent(BiTree *T,TElemType e)
{ // 若e是T 的非根节点，则返回它的双亲，否则返回空

  LinkQueue *q;
  QElemType a;
  q = (LinkQueue *)malloc(sizeof(struct QNode));
  if(T)
  {
    InitQueue(&q);
    EnQueue(q,(T));
  }
  while(!QueueEmpty(q))
  {
    DeQueue(q,&a);
    if(a->lchild && a->lchild->data == e || a->rchild && a->rchild->data==e)
      return a->data;
    else
    {
      if(a->lchild)
        EnQueue(q,a->lchild);
      if(a->rchild)
        EnQueue(q,a->rchild);
    }
  }
  free(q);
}

BiTree *Point(BiTree *T,TElemType s)
{ // 返回二叉树T中指向元素值为S的节点的指针

  LinkQueue *q;
  BiTree *a;
  q = (LinkQueue *)malloc(sizeof(struct QNode));
   a = (BiTree *)malloc(sizeof(struct BiTNode));
  if(T)
  {
    InitQueue(&q);
    EnQueue(q,T);
    while(!QueueEmpty(q))
    {
      DeQueue(q,&a);
      if(a->data==s)
        return a;
      if(a->lchild)
        EnQueue(q,a->lchild);
      if(a->rchild)
        EnQueue(q,a->rchild);
    }
  }
  free(q);
   free(a);
  return NULL;
}

TElemType LeftChild(BiTree *T,TElemType e)
{//返回e的左孩子，若e无左孩子，则返回空

  BiTree *a;
  if(T)
  {
    a = Point(T,e);
    if(a && a->lchild)
      return a->lchild->data;
  }
  return Nil;
}

TElemType RightChild(BiTree *T,TElemType e)
{//返回e的右孩子，若e无左孩子，则返回空

  BiTree *a;
  if(T)
  {
    a = Point(T,e);
    if(a && a->rchild)
      return a->rchild->data;
  }
  return Nil;
}

TElemType LeftSibling(BiTree *T,TElemType e)
{//返回e的左兄弟，若e是T的左孩子或无左孩子，则返回空

  TElemType a;
  BiTree *p;
  if(T)
  {
    a = Parent(T,e);
    p= Point(T,a);
    if(p->lchild && p->rchild && p->rchild->data ==e)
      return p->lchild->data;
  }
  return Nil;
}

TElemType RightSibling(BiTree *T,TElemType e)
{//返回e的右兄弟，若e是T的左孩子或无左孩子，则返回空

  TElemType a;
  BiTree *p;
  if(T)
  {
    a= Parent(T,e);
    p = Point(T,a);
    if(p->lchild && p->rchild && p->lchild->data ==e)
      return p->rchild->data;
  }
  return Nil;
}

Status InsertChild(BiTree *p,int LR,BiTree *c)
{// 根据LR为0或1，插入c为T中p所指节点的左或右孩子，p所指节点的原有左或右子树，则成为c的右子树

  if(p)
  {
    if(LR == 0)
    {
      c->rchild = p->lchild;
      p->lchild = c;
    }
  else
  {
    c->rchild = p->rchild;
    p->rchild =c;
  }
  return OK;
}
return ERROR;
}

Status DeleteChild(BiTree *p,int LR)
{//根据LR为0或1，删除T中p所指向的左或右子树

  if(p)
  {
    if(LR == 0)
      ClearBiTree(&(p->lchild));
    else
      ClearBiTree(&(p->rchild));
    return OK;
  }
  return ERROR;
}