此次重点在于 二叉树的结构体构造（指针的大量练习），数组方式构造（简易）
建树的输入方式为，
(11,LL) (7,LLL) (8,R) (5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
()表示结束LL表示从根节点开始向右移两次，并且同时延伸 (5,)表示根节点
首先还是先来比较麻烦的结构体构造方法，但是看起来很高端。
char s[100];//保存输入
int Failed=0,cnt=0; //表明是否输入有误 cnt是计数器 记录节点数目
//定义结构体
typedef struct Tnode //自定义一个结构体
{
int hv;// have been valued
int v;//存储节点数值
struct Tnode *l,*r;//左右儿子 都是指向Tnode的指针 此时不能用Node*是因为Node还没有定义完全
} Node;//命名在Node
//发现了 二叉树的定义过程中其实用到了递归的方法
Node* root;//此为根节点
//此函数用来创建新node且为之申请动态内存 stdlib.h
Node* newnode()
{
Node* u = (Node*)malloc(sizeof(Node)) ;//将申请来的内存格式化
if(u != NULL)//防止是非法内存
{
u->hv=0;//为u初始化
u->l=u->r=NULL;//还无左右儿子 连续赋值 必须赋值为空 否则后续无法判断是否为空
}
return u;//返回新建的节点
}
//向已有的树上添加节点 v来赋值 s来确定节点位置
void addnode(int v,char *s)
{
//按照移动序列行走 *s =="LL)"
int len=strlen(s);//用来做循环控制
Node* u =root;//起点是root根节点 每一次寻找位置都要从根节点开始
for(int i=0;i<len;i++)
{
if(s[i]=='L')
{
if(u->l==NULL) u->l=newnode();//找到了空节点，说明要进行延伸
u=u->l;//向左走 //延伸了之后才能移动
}else if(s[i]=='R')
{
if(u->r==NULL) u->r=newnode();
u=u->r;//向左走
}
}
<span style="white-space:pre"> </span>//此时已经找到了要赋值的节点了
if(u->hv) Failed=1;//如果输入有误则报错
else
{
u->v=v;
u->hv=1;
}
}
//读入并建树
int read()
{
Failed=0;//每次新建树时要重置
remove_tree(root) ;//释放原有内存
root = newnode();//为根节点进行初始化 ，建立一棵新树 主要是为了覆盖上一次的树
for(;;)//不断地读入
{
if(scanf("%s",s)!=1)
return 0;//表示输入结束
//strcmp 的返回值比较奇葩 若str1=str2，则返回零 说明完全相同
if(!strcmp(s,"()")) break;//如果读入的是（）就表示完成了一次输入 return 1
int v;//存储节点值
sscanf(&s[1],"%d",&v);//&s[1] 返回的是从s的第二个字符到结尾\0的数组 sscanf 从字符数组中读入v
addnode(v,strchr(s,',')+1);//strchr(s,',')返回的正好是','的指针，再+1
}
return 1;
}
void remove_tree(Node* u)
{
if(u==NULL)
return;//走到某一个叶子时就return
//利用递归循环删除
remove_tree(u->l);
remove_tree(u->r);
free(u);
}
此种方法的优点是比较易懂，后序过程时思考难度下降，并且是动态内存，所以不用管数据的大小
还有一种避免指针的方式，就是用数组来进行建树。
const int root=1; int left[10000],right[10000],cnt; int nodes[10000]={0};
//left和right只用来记录节点之间的父子关系，且序号是按照输入顺序进行的
//真正的数据值存储在nodes里
bool failed = false; char s[100];
//建立一棵新树，
void newtree()
{
left[root]=right[root]=0;
cnt=1;
memset(nodes,0,sizeof(nodes));
}
int newnode()
{
<span style="white-space:pre"> </span>int u = ++cnt;//使cnt增加1 表明有了一个新的节点
<span style="white-space:pre"> </span>left[u]=right[u]=0;
<span style="white-space:pre"> </span>return u;//返回u
}
void addnode(int v,char *s)//值v s= LL)
{
<span style="white-space:pre"> </span>int len= strlen(s);
<span style="white-space:pre"> </span>int t=root;
<span style="white-space:pre"> </span>for(int i=0;i<len;i++)
<span style="white-space:pre"> </span>{
<span style="white-space:pre"> </span>//先找到节点位置，如果遇到空就建立新节点
<span style="white-space:pre"> </span>if(s[i]=='L')
<span style="white-space:pre"> </span>{
<span style="white-space:pre"> </span>if(left[t]==0)
<span style="white-space:pre"> </span>left[t]=newnode();//如果当前的左边是空的就建立一个节点
<span style="white-space:pre"> </span>t=left[t];//向左走
<span style="white-space:pre"> </span>}else
<span style="white-space:pre"> </span>{
<span style="white-space:pre"> </span>if(s[i]=='R')
<span style="white-space:pre"> </span>{
<span style="white-space:pre"> </span>if(right[t]==0)
<span style="white-space:pre"> </span>right[t]=newnode();//如果当前的左边是空的就建立一个节点
<span style="white-space:pre"> </span>t=right[t];//向左走
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>if(nodes[t])
<span style="white-space:pre"> </span>failed = true;
<span style="white-space:pre"> </span>else
<span style="white-space:pre"> </span>nodes[t]=v;
<span style="white-space:pre"> </span>
}
int read()
{
<span style="white-space:pre"> </span>newtree();
<span style="white-space:pre"> </span>while(scanf("%s",s)==1)
<span style="white-space:pre"> </span>{
<span style="white-space:pre"> </span>if(!strcmp(s,"()"))
<span style="white-space:pre"> </span>return 1;//结束
<span style="white-space:pre"> </span>int d=0;
<span style="white-space:pre"> </span>sscanf(&s[1],"%d",&d);
<span style="white-space:pre"> </span>addnode(d,strchr(s,',')+1);
<span style="white-space:pre"> </span>}
<span style="white-space:pre"> </span>return 0;
}
代码其实并没有减少多少，说简单了但是其实也有点复杂 比如left right nodes 三个数组之间的关系有时候会闹不清楚