C语言 二叉树的结构和遍历算法

/****************************************/
/*Description:Binary Tree (Recursion and None Recursion)*/
/*Email:[e-mail]*/
/*Author:yi_landry Harbin Normal University Computer Science*/
/*Date:2008-5-25*/
/*Copyright:HNU2008.cop*/
/*Environment:turbo c 2.01 English Version*/
/****************************************/

# include
# include
# define OVERFLOW 0
# define OK 1

/****************************************/
/*The node of binary tree*/
/****************************************/
typedef struct BiTNode{
 char data;
    int location;//record the location of the node in the tree
 struct BiTNode * lchild,* rchild;//the pointer of left and right child
}BiTNode,*BiTree;

/****************************************/
/*Initial the tree*/
/****************************************/
InitBiTree(BiTree  T)
{
  T = (BiTree)malloc(sizeof(struct BiTNode));
  if (!T) exit(OVERFLOW);
  printf("Initial the tree succefully!\n");
}

/****************************************/
/*Destroy tree and free the memory distributed at first*/
/****************************************/
DestroyBiTree(BiTree  T)
{
   free(T);
   printf("Destroy the tree successfully!\n");
}

/****************************************/
/*Create a bitree*/
/****************************************/
CreateBiTree(BiTree  T)
{
  if (!T)
  {
      T->data = NULL;
      T->lchild = NULL;
      T->rchild = NULL;
      printf("Create the tree successfully!\n");
  }
  else
  {
      printf("Failed to create the tree!\n");
  }
}

/****************************************/
/*Clear all the nodes in the tree*/
/****************************************/
ClearBiTree(BiTree  T)
{
  if (!T)
  free(T);
  printf("Clear the tree successfully!\n");
}

/****************************************/
/*Judge the tree is empty or not*/
/****************************************/
BiTreeEmpty(BiTree T)
{
  if(!T && T->data != NULL) printf("The tree is not empty!\n");
  else printf("The tree is empty!\n");
}

/****************************************/
/*Obtain the length of the tree*/
/****************************************/
BiTreeDepth(BiTree T)
{
  int depth=0,leftDepth=0,rightDepth = 0;
  if (!T)
  {
       depth = 0; 
  }
  else if (T->lchild == NULL && T->rchild == NULL)
  {
    depth == 1;
  }
  else
  {
       leftDepth = BiTreeDepth(T->lchild);
       rightDepth = BiTreeDepth(T->rchild);
       depth = leftDepth>rigthDepth?leftDepth:rightDepth;
  }
  printf("The depth of the tree is %d !\n",depth);
}

/****************************************/
/*Return the root of the tree*/
/****************************************/
Root(BiTree T)
{
  char data = T->data;
  printf("The root of the tree is %c!\n",data);
}

/****************************************/
/*Return the vlue of the node at some location*/
/****************************************/
Value(BiTree T,int location)
{   
     BiTNode * bitnode = findLocation(T,location);
     char data = bitnode->data;
     printf("The vlue of the node at the location %d is %c \n!",location,data);
}

/****************************************/
/*Find the node at some location*/
/****************************************/
BiTNode * findLocation(BiTree T,int location)//now we assume this function is correct,then we consider it again
{
  int leftloca=0,rightloca=0;
  BiNode * bi = T;
  if(location == 1)
  {
      return T;
  }
  else
  {
   leftloca  = findLocation(T->lchild);
   if (leftloca == location)
   {
     return T->lchild;
   }
   rightloca = findLocation(T->rchild);
   if (rightloca == location)
   {
     return T->rchild;
   }
  }
}

/****************************************/
/*Assign a value to the node at some location*/
/****************************************/
Assign(BiTree T,int location,int value)
{
  BiTNode * bitnode = findLocation(T,location);
  bitnode->data = value;
  printf("Assign the value to the node sucessfully!\n");
}

/****************************************/
/*Get the parent node of the node at some location*/
/****************************************/
Parent(BiTree T,int location)
{
   BiTNode * bitnode = findLocation(T,location);
   BiTNode * bi = ()//a function can traverse all node and everytime return a node
   if (bi->lichid ==bitnode || bi->rchild == bitnode)
   {
     printf("The parent of node is \n");
   }
}

/****************************************/
/*Get the leftchild node of the node at some location*/
/****************************************/
LeftChild(BiTree T,int location)
{
  BiTNode * bitnode = fidLocation(T,location);
  BiTNode * bitnode1 = bitnode->lchild;
  char data = bitnode->data;
  char data1  = bitnode1->data;
  printf("The leftchild of %c is %c!\n",data,data1);
}

/****************************************/
/*Get the rightchild node at the node at some location*/
/****************************************/
RightChild(BiTree T,int location)
{
  BiTNode * bitnode = findLocation(T,location);
  BiTNode * bitnode1 = bitnode->rchild;
  char data = bitnode->data;
  char data1 = bitnode1->data;
  printf("The rightchild of %c is %c!\n",data,data1);
}

/****************************************/
/*PreOrderTraverse the tree(Recursion)*/
/****************************************/
PreOrderTraverse_R(BiTree T)
{
  if (T)
  {
    if (visit(T->data))
     if (PreOrderTraverse_R(T->lchild))
      if (PreOrederTraverse_R(T->rchild))
        return OK;
  }
  else
  {
    return OK;
    printf("We can not traverse this tree!\n");
  }
}

 

/****************************************/
/*InOrderTraverse the tree(Recursion)*/
/****************************************/
InOrderTraverse_R(BiTree T)
{
  if (T)
  {
     if (InOrderTraverse_R(T->lchild))
      if (visit(T->data))
       if (InOrederTraverse_R(T->rchild))
        return OK;
  }
  else
  {
    return OK;
    printf("We can not traverse this tree!\n");
  }
}

/****************************************/
/*PostOrderTraverse the tree(Recursion)*/
/****************************************/
PostOrederTraverse_R(BiTree T)
{
  if (T)
  {
     if (PostOrderTraverse_R(T->lchild))
       if (PostOrederTraverse_R(T->rchild))
         if (visit(T->data))
        return OK;
  }
  else
  {
    return OK;
    printf("We can not traverse this tree!\n");
  }
}

/****************************************/
/*Print the tree */
/****************************************/
int visit(char data)
{
  printf("%c ",data);
  return ok;
}

void help()
{
  printf("      /*****************************************************************/\n");
  printf("      /*****************************************************************/\n");
  printf("      /*        The binary tree Operation Version 1.0                  */\n");
  printf("      /*             View the example information            1         */\n");
  printf("      /*       insert a node into the tree at the tail       2         */\n");
  printf("      /*        delete the head  number from the tree        3         */\n");
  printf("      /*          Find a number if or not in the tree        4         */\n");
  printf("      /*       Get the prior of some number from the tree    5         */\n");
  printf("      /*       Get the next  of some number from the tree    6         */\n");
  printf("      /*                Get the size of tree                 7         */\n");
  printf("      /*               Show the help information             8         */\n");
  printf("      /*             View current  tree information          9         */\n");
  printf("      /*                    Exit binary  tree                Q         */\n");
  printf("      /*****************************************************************/\n");
}

main()
{
  int inputItem;
  help();
  BiTree T;
  InitBiTree(T);
}