作者：薛飞 　摘自Ｃ语言基地

/******************/
/*二叉树的基本操作*/
/*    非递归法    */
/*   0305  薛飞   */
/*    ---06'10.24 */
/******************/
#include"stdio.h"
#include"stdlib.h"
#include"limits.h"
#include"graphics.h"
#include"io.h"
#include"math.h"
#include"process.h"
#include"conio.h"
#define N 50
#define maxint 10000
typedef char ElemT;/*树元素的类型*/
typedef struct treenode
   {ElemT data;
    int x,y;
    struct treenode *lchild,*rchild;
   } TREENODE,*TREENODEPTR;
void createtree(TREENODEPTR *root)
     {int r1,r2;
      ElemT value;
      TREENODEPTR t,q[N];
      printf("please input data of node(in layer order):");
      scanf("%c",&value);
      if(value!=' ')
        {*root=(TREENODEPTR)malloc(sizeof(TREENODE));
         (*root)->data=value;
         r2=r1=1;
         q[r1]=*root;
         }
      else {printf("input error!\n");return;}
      while(r2<=r1)
           {t=q[r2];
            r2++;
            scanf("%c",&value);
            if(value==' ')
              t->lchild=NULL;
            else
               {t->lchild=(TREENODEPTR)malloc(sizeof(TREENODE));
                t->lchild->data=value;
                r1++;q[r1]=t->lchild;
               }
            scanf("%c",&value);
     if(value==' ')
              t->rchild=NULL;
            else
               {t->rchild=(TREENODEPTR)malloc(sizeof(TREENODE));
                t->rchild->data=value;
                r1++;
                q[r1]=t->rchild;
                }
             }
       }
void CreateNodeOrder(TREENODEPTR *root,int a,int b)/*先序递归建立结点输出位置*/
    { int c=35;
      if(!(*root))
      return;
      else
       {(*root)->x=a;(*root)->y=b;
        CreateNodeOrder(&((*root)->lchild),a-c,b+c);
        CreateNodeOrder(&((*root)->rchild),a+c,b+c);
       }
    }
void preorder(TREENODEPTR root)
     {TREENODEPTR k,s[N];
      int top=0;
      k=root;
      while(1)
           {while(k!=NULL)
                 {printf("->%c",k->data);
                  top++;s[top]=k;
    k=k->lchild;
                 }
             if(top!=0)
               {k=s[top];top--;k=k->rchild;}
             else return;
            }
      }
void inorder(TREENODEPTR root)
     {TREENODEPTR k,s[N];
      int top=0;
      k=root;
      while(1)
           {while(k!=NULL)
                 {top++;s[top]=k;k=k->lchild;}

             while(top!=0&&(s[top]->lchild==NULL||k==s[top]->lchild))
                       {k=s[top];
                        printf("->%c",k->data);
                        if(s[top]->rchild==NULL||k==s[top]->rchild)
                           {top--;
                            while(k==s[top]->rchild)
                              {
                                k=s[top];
                                top--;
                              }
                            k=s[top]->lchild;
                           }
                        else {k=s[top]->rchild;break;}

                        }
              if(top==0) return;

            }
     }

void inorder1(TREENODEPTR root)
     {TREENODEPTR k,s[N];
      ElemT str[N];
      int top=0,m=-maxint,n=0,n0=0,tag=1,i;
      k=root;
      while(1)
           {while(k!=NULL)
                 {top++;s[top]=k;k=k->lchild;}

             while(top!=0&&(s[top]->lchild==NULL||k==s[top]->lchild))
                       {k=s[top];
                        n++;
                        if(tag)
                          if(k->data>m) m=k->data;
                          else tag=0;
                        if(k->lchild==NULL&&k->rchild==NULL)
                          {n0++;
                           str[n0]=k->data;
                          }
                        if(s[top]->rchild==NULL||k==s[top]->rchild)
                           {top--;
                            while(k==s[top]->rchild)
                              {
                                k=s[top];
                                top--;
                              }
                            k=s[top]->lchild;
                           }
                        else {k=s[top]->rchild;break;}

                        }
              if(top==0)
   {printf("\nThis binarytree have %3d leaves,their data are: ",n0);
                  for(i=1;i<=n0;i++)
                     {printf(" %c",str[i]);}
                  printf("\nThis binarytree have %3d Only one child nodes.",n+1-2*n0);
                  if(tag) printf("\nThis tree is a binary sort tree.\n");
                  else    printf("\nThis tree isn't a binary sort tree.\n");
                  return;
                 }

            }
     }
void posorder(TREENODEPTR root)
     {TREENODEPTR k,s[N];
      int top=0;
      k=root;
      while(1)
           {while(k!=NULL)
                 {top++;s[top]=k;k=k->lchild;}
            while(1)
                 {if (s[top]->rchild!=NULL)
                     {k=s[top]->rchild;break;}
    while(top!=0&&(k==s[top]->rchild||s[top]->rchild==NULL))
                       {k=s[top];
                        printf("->%c",k->data);
                        top--;
                        }
                   if(top==0) return;
                  }
              }
       }

void PreOrderTraverse1(TREENODEPTR root,int go_l)
/*把树根结点的左、右子树分别左、右移（以防结点重复）*/
  { int h=14;
    if(root)
      {
       if(go_l==0) root->x+=h;
       else        root->x-=h;
       PreOrderTraverse1(root->lchild,go_l);
       PreOrderTraverse1(root->rchild,go_l);
      }
  }
void PreOrderTraverse2(TREENODEPTR root)/*递归的先序的、画树的结构*/
{
 ElemT str[3];
 int n=20,u=2;;
 if(root)
 {
  sprintf(str,"%c",root->data);
  setcolor(LIGHTMAGENTA);/*设置圆的颜色*/
  circle(root->x,root->y,n/2);/*画圆*/
  setcolor(RED);
  outtextxy((root->x)-u,(root->y)-u,str);/*在圆内输出结点*/
  if(root->lchild!=NULL)
     {
       setcolor(LIGHTGREEN);/*设置线的颜色*/
       line(root->x,root->y+n/2,root->lchild->x,root->lchild->y-n/2);/*画线*/
     }
  if(root->rchild!=NULL)
     {
       setcolor(LIGHTGREEN);/*设置线的颜色*/
       line(root->x,root->y+n/2,root->rchild->x,root->rchild->y-n/2);/*画线*/
     }
  PreOrderTraverse2(root->lchild);
  PreOrderTraverse2(root->rchild);
 }
}
int depth(TREENODEPTR root)
    {int hl,hr;
     if(!root) return 0;
     else
        {hl=depth(root->lchild);
         hr=depth(root->rchild);
         return hl>=hr? (hl+1):(hr+1);
        }
     }

void change(TREENODEPTR *root)
     {TREENODEPTR p;
      if(*root!=NULL)
        {p=(*root)->lchild;
         (*root)->lchild=(*root)->rchild;
         (*root)->rchild=p;
         change(&(*root)->lchild);
         change(&(*root)->rchild);
         }
      }

void main()
    {TREENODEPTR root;
     char ch;
     int graphdriver,graphmode;
     graphdriver=DETECT;
     initgraph(&graphdriver,&graphmode,"C:\TC");/*初始化图象设备*/
     cleardevice();/*清屏*/
     setbkcolor(BROWN);/*设置背景颜色*/
     createtree(&root);
     while(1){
     cleardevice();/*清屏*/
     printf("____\001Welcome to use XueFei's program\001____\n");
     printf("_________________ MENU___________________\n");
     printf(" 1.Show the message of Binary Tree\n");
     printf(" 2.Show the message after change subtrees\n");
     printf(" 3.quit\n");
     printf("_________________________________________\n");
     printf("please make a choice:\n");
     ch=getch();
     switch(ch)
       {case '1':
       {cleardevice();/*清屏*/
        CreateNodeOrder(&root,300,40);
               if(root->lchild!=NULL)/*将根的左子树左移*/
           PreOrderTraverse1(root->lchild,1);
               if(root->rchild!=NULL)/*将根的右子树右移*/
           PreOrderTraverse1(root->rchild,0);
               PreOrderTraverse2(root);/*画树的结构*/
               window(1,17,15,25);/*在点(1,17,15,25)开始输出*/
        printf("         \001 press anykey show the message =>\n");
        printf("________________________MESSAGE______________________");
        getch();
        printf("\nTraversing Binary Tree of DLR:\n");
               preorder(root);
        printf("\nTraversing Binary Tree of LDR:\n");
               inorder(root);
               printf("\nTraversing Binary Tree of LRD:\n");
               posorder(root);
               inorder1(root);
               printf("Depth of this tree is%3d.\n",depth(root));
        printf("_____________________________________________________\n");
        break;
       }
 case '2':
        {graphdriver=DETECT;
               initgraph(&graphdriver,&graphmode,"C:\TC");/*初始化图象设备*/
               cleardevice();/*清屏*/
               setbkcolor(BROWN);/*设置背景颜色*/
               change(&root);
        printf("\n_________After change the sub trees:\n");
               CreateNodeOrder(&root,300,40);
               if(root->lchild!=NULL)/*将根的左子树左移*/
           PreOrderTraverse1(root->lchild,1);
               if(root->rchild!=NULL)/*将根的右子树右移*/
           PreOrderTraverse1(root->rchild,0);
               PreOrderTraverse2(root);/*画树的结构*/
               window(1,17,15,25);/*在点(1,17,15,25)开始输出*/
        printf("         \001 press anykey show the message =>\n");
        printf("________________________MESSAGE______________________");
        getch();
        printf("\nTraversing Binary Tree of DLR:\n");
               preorder(root);
               printf("\nTraversing Binary Tree of LDR:\n");
               inorder(root);
               printf("\nTraversing Binary Tree of LRD:\n");
               posorder(root);
               inorder1(root);
               printf("Depth of this tree is%3d.\n",depth(root));
        printf("_____________________________________________________\n");
        break;
       }
       default :exit(0);
       }
     outtextxy(280,420,"press anykey to menu");
     getch();
    }

  }