我相信，大家都已经了解了这道题的背景，以及明白了我们需要做的事情。
对于这道题的背景，相信大家都熟悉，所以就不说了。
关于我们需要做的事情，大家也已经有了自己的思路。所以，我只在下面简短的写一写我的思路：
1.保存从键盘输入的源字符串；
2.加工从键盘输入的源字符串：只去掉里面的","；（这样后续操作简单）
3.构建二叉树，根据加工后的字符串；
4.遍历二叉树，根据我们构建的二叉树。
在我们需要做的事情中，针对“3.构建二叉树”，我们应该怎么做呢？我整理出了递归和非递归2种思路，但是，我并不先写代码，而是想向大家展示一下，我是怎么想出来思路的：
1.递归方式：
是不是一看就有思路啦？恭喜你！现在自己尝试做一做叭！
void BinTree_Building(PBinTreeNode p_temp,char* begin_str,char* end_str){//递归构建1棵完整二叉树//首先填充数据 p_temp->info=*begin_str;//然后判断:是否要进行递归 //如果begin_str==end_str，也就是说，字符串里只有1个字符，那么不需要递归 if(begin_str==end_str);//如果begin_str!=end_str，也就是说，字符串里不只有字符，那么需要递归 else if(begin_str!=end_str){//设置temp_str，它最后停下来的地方很重要！ char* temp_str=begin_str+2;//如果说，在begin_str和end_str中间，只有1对（），那么： if(*(begin_str+3)!='('){}//如果说，在begin_str和end_str中间，不只有1对（），那么：else{//通过一个循环的设置，遇到"("则加1，遇到")"则减1，减到0后，temp_str就停下来 int i=0;do{temp_str++;if(*temp_str=='(') i++;else if(*temp_str==')') i--;}while(i!=0);}//新建并初始化一个左孩子结点，并让p_temp的左针指向它，它的父针指向p_temp PBinTreeNode L_PBinTree=CreateBinTreeNode();p_temp->lchild=L_PBinTree;L_PBinTree->dad=p_temp;//然后调用函数，完善p_temp的左子树 BinTree_Building(L_PBinTree,begin_str+2,temp_str); //新建并初始化一个右孩子结点，并让p_temp的右针指向它，它的父针指向p_temp PBinTreeNode R_PBinTree=CreateBinTreeNode();p_temp->rchild=R_PBinTree;R_PBinTree->dad=p_temp;//然后调用函数，完善p_temp的右子树 BinTree_Building(R_PBinTree,temp_str+1,end_str-1); }}
2.非递归方式：
void BuildBinTreeNode(PBinTreeNode temp,char* p){for(;*p!='\0';){if(*p=='('){PBinTreeNode L=CreateBinTreeNode();temp->lchild=L;L->dad=temp;temp=temp->lchild;p++;}else if(*p==')'){temp=temp->dad;p++;}else if((*p=='#')&&(temp->info!='0')){PBinTreeNode R=CreateBinTreeNode();temp->dad->rchild=R;R->dad=temp->dad;temp=R;temp->info=*p;p++;}else if((*p=='#')&&(temp->info=='0')){temp->info=*p;p++;}else if((*p>='A')&&(*p<='Z')&&(temp->info!='0')){PBinTreeNode R=CreateBinTreeNode();temp->dad->rchild=R;R->dad=temp->dad;temp=R;temp->info=*p;p++;}else if((*p>='A')&&(*p<='Z')&&(temp->info=='0')){temp->info=*p;p++;}}}
好了，最后还是无足轻重的完整代码分享了：
#include<stdio.h>#include<stdlib.h>#include<string.h>#include<math.h>typedef char DataType;typedef struct BinTreeNode{DataType info;struct BinTreeNode* lchild;struct BinTreeNode* rchild;struct BinTreeNode* dad;}BinTreeNode,*PBinTreeNode;void InitializeBinTreeNode(PBinTreeNode PNode){//初始化二叉树中的一个结点 PNode->info='0';PNode->lchild=NULL;PNode->rchild=NULL;PNode->dad=NULL;}PBinTreeNode CreateBinTreeNode(){//创建二叉树中的一个结点 PBinTreeNode PNode=(PBinTreeNode)malloc(sizeof(BinTreeNode));if(PNode==NULL){printf("out of space!");}else{InitializeBinTreeNode(PNode);return PNode;}}//A(B(#D)C(E(#F)#)) void BuildBinTreeNode(PBinTreeNode temp,char* p){for(;*p!='\0';){if(*p=='('){PBinTreeNode L=CreateBinTreeNode();temp->lchild=L;L->dad=temp;temp=temp->lchild;p++;}else if(*p==')'){temp=temp->dad;p++;}else if((*p=='#')&&(temp->info!='0')){PBinTreeNode R=CreateBinTreeNode();temp->dad->rchild=R;R->dad=temp->dad;temp=R;temp->info=*p;p++;}else if((*p=='#')&&(temp->info=='0')){temp->info=*p;p++;}else if((*p>='A')&&(*p<='Z')&&(temp->info!='0')){PBinTreeNode R=CreateBinTreeNode();temp->dad->rchild=R;R->dad=temp->dad;temp=R;temp->info=*p;p++;}else if((*p>='A')&&(*p<='Z')&&(temp->info=='0')){temp->info=*p;p++;}}}void preOrderOutput(BinTreeNode *PNode){//这是借用的别人的递归函数 printf("%c",PNode->info);if(PNode->lchild){preOrderOutput(PNode->lchild);}if(PNode->rchild){preOrderOutput(PNode->rchild);}}int main(){//Firstly,记录从键盘中读入的字符串，将字符串存到ori中 char ori[1000]={0};fgets(ori,950,stdin); //同时对原字符串加工，去掉里面的逗号 //用str保存加工后的字符串 char str[1000]={0};char* p1=ori;char* p2=str;while(*p1!='\0'){if(*p1==','){p1++;}else{*p2=*p1;p1++;p2++;}}//Secondly,为调用创建二叉树函数做准备：//1.定义一个字符指针p，指向str字符串 char* p=str;//2.创建一个二叉树根节点指针mainroot,并且temp和它一样的指向 PBinTreeNode mainroot=CreateBinTreeNode();PBinTreeNode temp=mainroot;//这样子，我们有了p，有了temp，就可以调用创建二叉树函数了： BuildBinTreeNode(temp,p);//Thirdly,用先序遍历二叉树函数，遍历一遍二叉树preOrderOutput(mainroot);return 0;}
#include<stdio.h>#include<stdlib.h>#include<string.h>#include<math.h>typedef char DataType;typedef struct BinTreeNode{DataType info;struct BinTreeNode* lchild;struct BinTreeNode* rchild;struct BinTreeNode* dad;}BinTreeNode,*PBinTreeNode,BinTree,*PBinTree;void InitializeBinTreeNode(PBinTreeNode PNode){//初始化二叉树中的单个结点 PNode->info='0';PNode->lchild=NULL;PNode->rchild=NULL;PNode->dad=NULL;}PBinTreeNode CreateBinTreeNode(){//创建二叉树中的单个结点 PBinTreeNode PNode=(PBinTreeNode)malloc(sizeof(BinTreeNode));if(PNode==NULL){printf("out of space!");}else{InitializeBinTreeNode(PNode);return PNode;}}//A(B(#D)C(E(#F)#)) void BinTree_Building(PBinTreeNode p_temp,char* begin_str,char* end_str){//递归构建1棵完整二叉树//首先填充数据 p_temp->info=*begin_str;//然后判断:是否要进行递归 //如果begin_str==end_str，也就是说，字符串里只有1个字符，那么不需要递归 if(begin_str==end_str);//如果begin_str!=end_str，也就是说，字符串里不只有字符，那么需要递归 else if(begin_str!=end_str){//设置temp_str，它最后停下来的地方很重要！ char* temp_str=begin_str+2;//如果说，在begin_str和end_str中间，只有1对（），那么： if(*(begin_str+3)!='('){}//如果说，在begin_str和end_str中间，不只有1对（），那么：else{//通过一个循环的设置，遇到"("则加1，遇到")"则减1，减到0后，temp_str就停下来 int i=0;do{temp_str++;if(*temp_str=='(') i++;else if(*temp_str==')') i--;}while(i!=0);}//新建并初始化一个左孩子结点，并让p_temp的左针指向它，它的父针指向p_temp PBinTreeNode L_PBinTree=CreateBinTreeNode();p_temp->lchild=L_PBinTree;L_PBinTree->dad=p_temp;//然后调用函数，完善p_temp的左子树 BinTree_Building(L_PBinTree,begin_str+2,temp_str); //新建并初始化一个右孩子结点，并让p_temp的右针指向它，它的父针指向p_temp PBinTreeNode R_PBinTree=CreateBinTreeNode();p_temp->rchild=R_PBinTree;R_PBinTree->dad=p_temp;//然后调用函数，完善p_temp的右子树 BinTree_Building(R_PBinTree,temp_str+1,end_str-1); }}void preOrderOutput(BinTreeNode *PNode){//这是借用的别人的递归函数 printf("%c",PNode->info);if(PNode->lchild){preOrderOutput(PNode->lchild);}if(PNode->rchild){preOrderOutput(PNode->rchild);}}int main(){//Firstly,记录从键盘中读入的字符串，将字符串存到ori中 char ori[1000]={0};scanf("%s",ori);//同时对原字符串加工，去掉里面的逗号 //用processed保存加工后的字符串 char processed[1000]={0};char* p1=ori;char* p2=processed;while(*p1!='\0'){if(*p1==','){p1++;}else{*p2=*p1;p1++;p2++;}}//Secondly,调用创建二叉树函数：//1.定义字符指针begin_str和end_str，一个指processed字符串的开头，一个指结尾 char* begin_str=processed;char* end_str=processed;while(*(end_str+1)!='\0') end_str++;//2.创建并初始化根结点mainroot PBinTreeNode mainroot=CreateBinTreeNode();//3.调用创建二叉树函数： BinTree_Building(mainroot,begin_str,end_str); //Thirdly,用先序遍历二叉树函数，遍历一遍二叉树preOrderOutput(mainroot);return 0;}
