数据结构 二叉树

基于hdu1662改的二叉树（www.cnblogs.com/general10/p/5856794.html）

非递归遍历忘记打了 回头补上……

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<string>
#include<map>
#include<set>
#include<vector>
#include<queue>
#define M(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
queue<int>ans;
struct Binary_Tree //二叉树
{
    int value;
    Binary_Tree *lchild,*rchild;
    Binary_Tree()
    {
        value=0;
        lchild=rchild=NULL;
    }
};

bool add(Binary_Tree *&Root,char *s,int value)  //向二叉树中加入点
{
    if(Root==NULL)
        Root=new Binary_Tree();
    if(*s=='')
    {
        if(Root->value!=0)
        {
            return false;
        }
        Root->value=value;
        return true;
    }
    if(*s=='L') //寻找路径
    {
        return add(Root->lchild,s+1,value);
    }
    else if(*s=='R')
    {
        return add(Root->rchild,s+1,value);
    }
    return false;
}

//bool add(Binary_Tree *&Root,int num,int value){ //向完全二叉树中加入点
//    if(Root==NULL)
//    {
//        Root=new Binary_Tree();
//        Root->value=value;
//        return true;
//    }
//    if(num==0||num==1) //根据序号判断左右孩子
//    {
//       if(num)
//           (Root->rchild)->value=value;
//         else
//            (Root->lchild)->value=value;
//        return true;
//    }
//    if(num%2==0) //寻找路径
//    {
//        return add(Root->lchild,num/2,value);
//    }
//    else
//    {
//        return add(Root->rchild,num/2+1,value);
//    }
//    return false;
//}

void Delete(Binary_Tree *Root) //删除二叉树
{
    if(Root==NULL) return ;
    Delete(Root->lchild);
    Delete(Root->rchild);
    delete Root;
}
bool bfs(Binary_Tree *Root) //层次遍历
{
    Binary_Tree *q[260]; //数组模拟队列
    int front=0;
    int rear=1;
    q[0]=Root;
    while (front<rear)
    {
        Binary_Tree *temp=q[front++];
        if(!temp->value) //没有值就返回false
        {
            return false;
        }
        ans.push(temp->value); //当前节点入ans队
        if(temp->lchild) //左孩子入队
        {
            q[rear++]=temp->lchild;
        }
        if(temp->rchild) //右孩子入队
        {
            q[rear++]=temp->rchild;
        }
    }
    return true;
}

bool preorder(Binary_Tree *Root) //递归先序遍历二叉树
{
    if(Root==NULL)
    {
        return false;
    }
    ans.push(Root->value);
    preorder(Root->lchild);
    preorder(Root->rchild);
    return true;
}

bool midorder(Binary_Tree *Root) //递归中序遍历二叉树
{
    if(Root==NULL)
    {
        return false;
    }
    midorder(Root->lchild);
    ans.push(Root->value);
    midorder(Root->rchild);
    return true;
}

bool inorder(Binary_Tree *Root) //递归后序遍历二叉树
{
    if(Root==NULL)
    {
        return false;
    }
    inorder(Root->lchild);
    inorder(Root->rchild);
    ans.push(Root->value);
    return true;
}

int main()
{
    Binary_Tree *Root=NULL;
    char s[50];
    bool no=false;
    while(true)
    {
        no=false;
        Delete(Root);
        Root=NULL; //二叉树初始化
        while(true)
        {
            if(scanf("%s",s)==EOF) //读入
            {
                return 0;
            }
            if(strcmp(s,"()")==0)
            {
                break;
            }
            int val;
            char loc[10];
            strcpy(loc,"");
            sscanf(&s[1],"%d",&val);
            char *start=strchr(s,',')+1;
            sscanf(start,"%[A-Z]",&loc);
            if(!add(Root,loc,val))
            {
                no=true;
            }
        }
//        int n; //建立完全二叉树
//        scanf("%d",&n); //输入二叉树层数
//        int num=(int)(pow(2,n)+0.5)-1;
//        int sum=0;
//        while(num!=sum)
//        {
//            int value;
//            scanf("%d",&value);
//            sum++;
//            add(Root,sum,value);
//        }
        string str;
        while(cin>>str)
        {
            if(str=="end") break;
            if(str=="front")
            {
                preorder(Root);
                while(!ans.empty())
                {
                    int ll=ans.front();
                    ans.pop();
                    printf("%d%c",ll,ans.empty()?'
':' ');
                }
            }
            if(str=="middle")
            {
                midorder(Root);
                while(!ans.empty())
                {
                    int ll=ans.front();
                    ans.pop();
                    printf("%d%c",ll,ans.empty()?'
':' ');
                }
            }
            if(str=="back")
            {
                inorder(Root);
                while(!ans.empty())
                {
                    int ll=ans.front();
                    ans.pop();
                    printf("%d%c",ll,ans.empty()?'
':' ');
                }
            }
            if(str=="bfs")
            {
                bfs(Root);
                while(!ans.empty())
                {
                    int ll=ans.front();
                    ans.pop();
                    printf("%d%c",ll,ans.empty()?'
':' ');
                }
            }
        }
        /* if(no)
         {
             puts("not complete");
         }
         else
         {
             if(!bfs(Root))
                 puts("not complete");
             else
             {
                 while(!ans.empty())
                 {
                     int ll=ans.front();
                     ans.pop();
                     printf("%d%c",ll,ans.empty()?'
':' ');
                 }
             }
         }*/
    }
    return 0;
}
/*

(11,LL) (7,LLL) (8,R)
(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()

(3,L) (4,R) ()



       5
     4    8
  11    13  4
7   2         1

*/