二叉树 的建立及遍历 过程

我知道二叉树有先序遍历，中序遍历，后续遍历等等，不过这里说的的是输入一些点(11,LL) (7,LLL) (8,R) (5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ( )；对这些点进行构建出对应的二叉数，并对其进行层次遍历。过程为：

1. 定义结构体变量（表示有关结点及特征）

2. 函数--申请结点

3. 函数---增加新结点

4. 对数据处理，进入输入过程（建树过程）

5. 对数的层次遍历，利用的是宽度优先搜索（队列）

<span style="font-size: 18px;">#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

# define maxn 100

typedef struct Tnode
{
    int have_value;                 //记录该结点是否被赋值 
    int v;                          //记录结点值 
    struct Tnode *left,*right;        //指指向左右结点的指针 
}Node;

Node* root;                       //二叉树的根结点
char s[maxn+10];                    //保存读入的结点，要足够大哦
int n=0,ans[maxn];                  //结点总数和输出序列
 
 
Node* newnode()                     //建立新的结点
{
   Node* u = (Node*)malloc(sizeof(Node)); //定义一Node指针，并指向申请的动态内存 
   if(u != NULL)            //若申请成功
   { 
       u->have_value = 0;                //新结点的初始化 
       u->left = u->right = NULL;        //指针的初始化操作，很重要 
   }
   return u;                    //返回指向该结点的指针 
}  

int failed;                       //记录输入是否正确 

void addnode(int v,char *s)         //对树的完善工作
{
 
   int i;
   int n = strlen(s);
   Node * u = root;                 //从根开始走
   for(i=0;i<n;i++)
   {
        if(s[i] == 'L')
        {
          if(u->left == NULL)            //结点不存在吗 
               u->left = newnode();        //不存在就建立新的结点 
          u = u->left;                    //向左延伸 
        }
        else if(s[i] == 'R')
        {
             if(u->right == NULL)
                  u->right = newnode();
             u = u->right; 
        } 
   }
   if(u->have_value)               //该结点是否被赋值过
      failed = 1;                   //输入有误
  else
  { u->v = v;                      //该结点的值赋给该结点 
   u->have_value = 1;             //宣布此结点已被赋值（标记作用）    
  } 
}





int read_input()                  //对各结点读入
{
    failed = 0;                    //刚开始显然读入无误
    root = newnode();
    for( ; ; )
    {
         if(scanf("%s",s)!=1)
           return 0;                 //系统故障导致输入结束
         if(!strcmp(s,"()"))break;            //读到结束标志，退出循环
         int v;
         scanf(&s[1],"%d",&v);          //读入结点值
         addnode(v,strchr(s,',')+1);       //查逗号，插结点，示具体情况而定 
    }
    return (1); 
}


    
     
int bfs()                       //宽度优先搜索，对二叉树遍历
{
    int front=0,rear=1;
    Node* q[maxn];
    q[0] = root;
    while(front <rear)
    {
        Node* u=q[front++];
        if(!u->have_value)
           return 0;               //存在结点，但未赋值，输入有误.....
        ans[n++] = u->v;
        if(u->left != NULL)q[rear++] = u->left;
        if(u->right != NULL)q[rear++] = u->right; 
    }
    return 1;
} 


int main()
{
    int i;
    read_input();
    bfs();
    for(i=0;i<n;i++)
    {
      if(i)printf(" ");
      printf("%d",ans[i]);
    }
    printf("\n");
    return 0;
    
}
</span>