数据结构上机实验6.15问题 A: 出栈合法性问题 B: 算法3-1：八进制数问题 C: 算法3-2：行编辑程序问题 D: 算法3-7：银行排队问题 E: 算法3-4：表达式求值问题 F: 算法6-1~6-4：二叉链表存储的二叉树

75 阅读 0 评论 50 点赞

我是靠谱客的博主舒适电话，最近开发中收集的这篇文章主要介绍数据结构上机实验6.15问题 A: 出栈合法性问题 B: 算法3-1：八进制数问题 C: 算法3-2：行编辑程序问题 D: 算法3-7：银行排队问题 E: 算法3-4：表达式求值问题 F: 算法6-1~6-4：二叉链表存储的二叉树，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

问题 A: 出栈合法性

题目描述

已知自然数1，2，…，N（1<=N<=100）依次入栈，请问序列C1，C2，…，CN是否为合法的出栈序列。

输入

输入包含多组测试数据。
每组测试数据的第一行为整数N（1<=N<=100），当N=0时，输入结束。
第二行为N个正整数，以空格隔开，为出栈序列。

输出

对于每组输入，输出结果为一行字符串。
如给出的序列是合法的出栈序列，则输出Yes，否则输出No。

样例输入

样例输出

Yes
No

思路

入栈顺序是从小到大，所以设一个计数，监测入栈到第几个了，例如出栈顺序第一个是3，则ptr=3;

再看下一个出栈顺序，先和ptr比较，大于ptr，将ptr之后直到出栈顺序之前的数据压入栈，ptr=新出栈值

若小于ptr,和栈顶元素比较，若相等则弹出栈顶元素，ptr值不改变，若小于栈顶元素则错误输出no

代码

#include<iostream>
#include<stdlib.h>
#include<assert.h>
using namespace std;
struct LinkNode{
    int data;
    LinkNode* next;
    LinkNode(LinkNode*p=NULL){next=p;}
    LinkNode(int x,LinkNode*p=NULL){data=x;next=p;}
};
class LinkedStack{
    public:
        LinkedStack():top(NULL){}
        ~LinkedStack() { makeEmpty(); }
        void Push(const int &x);
        bool Pop(int &x);
        bool getTop(int &x)const; //返回最上面的值
        bool IsEmpty() const { return (top == NULL) ? true : false; }
        int getSize() const;
        void makeEmpty();
        //friend ostream &operator<<(ostream &os, LinkedStack &s);
    private:
        LinkNode *top;
};

void LinkedStack::makeEmpty(){
    LinkNode *p;
    while(top!=NULL){
        p = top;
        top = top->next;
        delete p;
    }
}
void LinkedStack::Push(const int & x){
    top = new LinkNode(x,top);
    assert(top != NULL);
}
bool LinkedStack::Pop(int& x){
    if(IsEmpty()==true)
        return false;
    LinkNode *p = top;
    x = top->data;
    top = top->next;
    delete p;
    return true;
}
bool LinkedStack::getTop(int& x)const{
    if(IsEmpty()==true)
        return false;
    x = top->data;
    return true;
}
int LinkedStack::getSize()const{
    int count = 0;
    LinkNode *p = top;
    while(p!=NULL){
        p = p->next;
        count++;
    }
    return count;
}
int main(){
	LinkedStack s1;
	/*int n=0;
	cin>>n;
	s1.Push(n);
	int m=0;
	s1.Pop(m);
	cout<<m;*/
	
	int n=0;
	cin>>n;
	int ptr=1;
	int c1=0;
	int top=0;s1.Pop(top);
	while(n!=0){
		//cout<<"in"<<endl;
		while(n!=0){
			cin>>c1;
		if((c1>top)||(c1>ptr)){
			//cout<<n<<"f1"<<endl;
			for(int i=ptr;i<c1;i++){
			s1.Push(i);
		}
		ptr=c1+1;
		s1.getTop(top);
		//cout<<top<<endl;
		n--;
		}else if(c1==top){
			//cout<<n<<"f2"<<endl;
			s1.Pop(c1);s1.getTop(top);n--;
		}else if(c1<top){
			//cout<<n<<"f3"<<endl;n--;
		break;
		}
		}
		s1.makeEmpty();
		if(n==0){
			cout<<"Yes"<<endl;
		} 
		else {
			//cout<<n<<endl;
			for(int j=1;j<n;j++){
				cin>>c1;
			}
		cout<<"No"<<endl;}
		cin>>n;
		ptr=0;
		top=0;s1.Pop(top);
	}
	return 0;
}/*cin>>c1;
		ptr=c1;
		for(;ptr<c1;ptr++){
			s1.Push(ptr);
		}
		s1.getTop(top);
		cin>>c1;
		if((c1>top)&&(c1>ptr)){
			for(;ptr<c1;ptr++){
			s1.Push(ptr);
		}s1.getTop(top);
		}else if(c1==top){
			s1.Pop(c1);s1.getTop(top);
		}else if(c1<top){
			cout<<"No"<<endl;
			cin>>n;
			break;
		}*/

问题 B: 算法3-1：八进制数

题目描述

将十进制数转换为八进制，并输出。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8DTo8AGd-1624035589325)(http://192.168.173.163/JudgeOnline/upload/pimg1324_1.jpg)]

图：将十进制数转换为八进制并输出

输入

输入包含若干十进制正整数。

输出

输出相应的八进制数，每个占一行。

样例输入

样例输出

提示

书上有相应的算法，需要补充缺失的函数。

总结：

1、数值转换使用到堆栈，但是用函数调用（系统的堆栈）将会更为方便。

2、书中的算法实际上只能处理正整数，你有更好的方法还能够处理0和负整数么？

思路

传统思路，除数倒取余，用数组存余数，直至商为零

代码

#include<iostream>
using namespace std;
void fun10_8(int& x);
int main(){
    int n=0;
    while(scanf("%d",&n)!=EOF){
    fun10_8(n);
    cout<<n<<endl;}
    return 0;
}
void fun10_8(int& x){
    int i=x,j=0;
    int array[100];
    while(i){
        array[j]=i%8;
        j++;
        i=i/8;
    }
    j--;
    x=array[j];
    j--;
    for(;j>=0;j--){
        x=array[j]+x*10;
    }
}

问题 C: 算法3-2：行编辑程序

题目描述

一个简单的行编辑程序的功能是：接收用户从终端输入的程序或数据，并存入用户的数据区。由于用户在终端上进行输入时，不能保证不出差错，因此，若在编辑程序中，“每接收一个字符即存入用户数据区”的做法显然不是很恰当。较好的做法是，设立一个输入缓冲区，用以接收用户输入的一行字符，然后逐行存入用户数据区。允许用户输入出差错，并在发现有误时可以及时更正。例如，当用户发现刚刚键入的一个字符是错的时，可补进一个退格符“#”，以表示前一个字符无效；如果发现当前键入的行内错误较多或难以补救，则可以键入一个退行符“@”，以表示当前行中的字符均无效。例如假设从终端接收了这样的两行字符：
whil##ilr#e(s#*s)
outcha@ putchar(*s=#++);
则实际有效的是下列两行：
while(*s)
putchar(*s++);

为此，可设这个输入缓冲区为一个栈结构，每当从终端接收了一个字符之后先作如下判别：如果它不是退格符也不是退行符，则将该字符压入栈顶；如果是一个退格符，则从栈顶删去一个字符；如果它是一个退行符，则将字符栈清为空栈。上述处理过程可用下面算法描述之：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qRMwJucq-1624035589327)(http://192.168.173.163/JudgeOnline/upload/pimg1325_1.jpg)]

图：行编辑程序算法

输入

若干行程序或者数据，每行不超过200个字符。

输出

经过行编辑程序处理过后的输出。

样例输入

whil##ilr#e(s#*s)
	outcha@	putchar(*s=#++);

样例输出

while(*s)
	putchar(*s++);

思路

题目讲的很清楚，照着做就行

但是比较坑的是在oj上如果第一位输入的是‘#’则下一位输入的也要删除

因此提供两种代码

代码1，只删除’#'之前的字符

#include<iostream>
#include<stdlib.h>
#include<assert.h>
using namespace std;
struct LinkNode{
    char data;
    LinkNode* next;
    LinkNode(LinkNode*p=NULL){next=p;}
    LinkNode(char x,LinkNode*p=NULL){data=x;next=p;}
};
class LinkedStack{
    public:
        LinkedStack():top(NULL){}
        ~LinkedStack() { makeEmpty(); }
        void Push(const char &x);
        bool Pop(char &x);
        bool getTop(char &x)const; //返回最上面的值
        bool IsEmpty() const { return (top == NULL) ? true : false; }
        int getSize() const;
        void makeEmpty();
        //friend ostream &operator<<(ostream &os, LinkedStack &s);
    private:
        LinkNode *top;
};

void LinkedStack::makeEmpty(){
    LinkNode *p;
    while(top!=NULL){
        p = top;
        top = top->next;
        delete p;
    }
}
void LinkedStack::Push(const char & x){
    top = new LinkNode(x,top);
    assert(top != NULL);
}
bool LinkedStack::Pop(char& x){
    if(IsEmpty()==true)
        return false;
    LinkNode *p = top;
    x = top->data;
    top = top->next;
    delete p;
    return true;
}
bool LinkedStack::getTop(char& x)const{
    if(IsEmpty()==true)
        return false;
    x = top->data;
    return true;
}
int LinkedStack::getSize()const{
    int count = 0;
    LinkNode *p = top;
    while(p!=NULL){
        p = p->next;
        count++;
    }
    return count;
}
int main(){
	char ch=NULL;
	LinkedStack chs,cs;
	ch=getchar();
	while(ch!=EOF){
		//cout<<1<<endl;
		while(ch!=EOF&&ch!='n'){
		//cout<<2<<endl;
		switch(ch){
			case '#':chs.Pop(ch);
			ch=getchar();
			break;
			case '@':
			chs.makeEmpty();
			ch=getchar();
			break;
			default:chs.Push(ch);
			ch=getchar();break;
		}
		
		}
		if(chs.IsEmpty()==true){//cout<<6<<endl;
			ch=getchar();
		}
		else{//cout<<7<<endl;
			while(!chs.IsEmpty()){//cout<<8<<endl;
				chs.Pop(ch);
				cs.Push(ch);				
			}
			while(!cs.IsEmpty()){
				cs.Pop(ch);
			cout<<ch;
			}
			chs.makeEmpty();
			cs.makeEmpty();
			cout<<endl;
			ch=getchar();
		}
	}
	return 0;
}

代码2，首位输入‘#’删除下一位字符

#include<iostream>
using namespace std;
int main(){
	char s[500];
	char x;
	int top=-1;
	while(scanf("%c",&x)!=EOF){
		while(x!=EOF&&x!='n'){		
		switch(x){
			case '#':top--;break;
			case '@':top=-1;break;
			default: 
			
			s[++top]=x;
		
			break;
		}
		x=getchar();
		}
		if(top>=0){
			for(int i=0;i<=top;i++){
				putchar(s[i]);
			}
			cout<<endl;
		}	
		top=-1;
		puts("");
	}	
}

答案代码

#include<stdio.h>
int main()
{
    char s[450],s1[450];
    int i,j;
    while(gets(s))
    {
        j=0;
        for(i=0;s[i]!='';i++)
        {   
            if(s[i]!='#'&&s[i]!='@')
            {
                s1[j]=s[i];
                j++;
            }
            else if(s[i]=='#')
                    j=j-1;
            else if(s[i]=='@')
                    j=0;
        }
        s1[j]='';
    printf("%sn",s1);
    }
}

问题 D: 算法3-7：银行排队

题目描述

我们大多都有在银行排队的经历，唉，那坑爹的排队啊！现在就让我们来算算我们这些客户平均需要等多久吧。
每天刚开始时银行会开m个窗口来为我们total个客户办理业务，当有客户需要办理业务时，先选择可以办理业务的窗口，如果有多个窗口可以办理业务就选择空闲时间最长的窗口，如果有多个窗口空闲的时间一样长，则选择序号小的窗口办理业务。假设我们每个人来到的时间和办理业务所需要的时间（为了简化问题，采用整数表示时间）都知道了。现在请你算算我们平均需要等待多久呢？

输入

有多组测试数据，每组数据开始有两个正整数m(<20)和total(<200)，后面有total对整数，对应客户先后到来的时间以及办理业务所需的时间。

输出

平均等待的时间，保留两位小数。

样例输入

2 6 1 3 4 1 5 3 9 2 13 4 13 3
3 14 0 3 2 2 2 4 5 4 7 2 11 3 12 3 12 4 12 1 13 3 15 4 19 1 22 3 23 2
2 5 0 6 0 5 0 6 7 1 7 2

样例输出

0.00
0.29
1.20

提示

题目中选择办理的窗口有三个状态，实际上从序号自小到大查找可以最早办理业务的窗口就已经满足上述三个状态了。可以使用数组来模拟列表。

总结：

实际上数组既可以模拟堆栈又可以模拟队列。

思路

按理来说，应该是用最小堆或者队列，将时间靠后的往后放，基于思路简单采用数组遍历比较，其他方法等有余力再补充

数组详细思路就是要记录柜台结束上一次服务的时间，客户来的时间和需要的用时

题目给出的数据是按时间按顺序来的就比较方便，可以从第一个顾客开始来进行寻找柜台更新状态

总之就是遍历虽简单但有效

代码

#include<iostream>
#include<iomanip>
using namespace std;
struct mood{
	int hours;
	mood():hours(0){}
};//记录柜台状态，实际改成数组也可
//void godowork(mood*cou,int*cu,int*ti,double&time);
int main(){
	int m=0,total=0;
	while(scanf("%d",&m)!=EOF){
	cin>>total;
	double time=0;
	mood*counts=new mood[m];
	int *cus=new int[total];//客户到来的时间和花费的时间，下标一一对应
	int *tim=new int[total];
	for(int i=0;i<total;i++){
		cin>>cus[i]>>tim[i];
	}
	int temp=0;
	for(int i=0;i<total;i++){
		for(int j=0;j<m;j++){
			if(counts[j].hours<counts[temp].hours){
				temp=j;//找最早结束的柜台，同等时间结束找小号
			}
		}
		if(counts[temp].hours<=cus[i]){
				counts[temp].hours=cus[i]+tim[i];//柜台结束时间早于等于顾客到来的时间
		}else if(counts[temp].hours>cus[i]){//晚于
			time=time+counts[temp].hours-cus[i];
			counts[temp].hours=counts[temp].hours+tim[i];//记录等待时间
			//cout<<time<<endl;			
		}
		temp=0;
	}
	time=time/total;cout<<fixed<<setprecision(2)<<time<<endl;}
	//cout<<time<<endl;
	return 0;
}

问题 E: 算法3-4：表达式求值

题目描述

算数四则运算的规则是1）先乘除，后加减；2）从左算到右；3）先括号内，后括号外。

由此，算式4+23-10/5的计算顺序为4+23-10/5=4+6-10/5=4+6-2=8。

给定一个以“#”作为结束符的算式，求出算式的结果。

给出严蔚敏《数据结构（C语言）》中的一段算法描述以作参考：

输入

以“#”结尾的表达式，运算数为正整数。每个表达式占一行。

输出

输出表达式运算的结果。

样例输入

4+2*3-10/5#
3*(7-2)#
2*3/2#

样例输出

8
15
3

提示：

使用栈来解决本题，很多人都会想到。但怎样建栈，却带来了问题。同样，严书上的代码实际上也给大家带来了问题。看过严书光盘中代码的人应该知道，代码中使用了两个栈，一个是存储运算符的，类型为char；另一个存储运算数，类型为float。而操作两个栈的函数都一样。要知道，除非像C++中使用泛型，C语言中却基本不能实现这样的操作。所以在C语言环境中需要将这两个栈结合在一起。由于char与int有种特别的联系，可以使用int来代替char存储运算符。

总结：

注意灵活运用栈，要是能够学习C++使用template就更好了。可以模拟STL了。

思路

书上的习题改，中缀转后缀，然后后缀运算，难点在于怎么输入后缀，尤其是两位数及以上的数字

代码

#include<iostream>
#include <string.h>
#include<stdlib.h>
#include<assert.h>
using namespace std;
const int stackIncreament=20;
template<class T>
class SeqStack{
public:
    SeqStack(int sz=50);
    ~SeqStack(){delete[] elements;}
    void Push(const T& x);//放里面放进去值，叠在上面
    bool Pop(T& x);//退出一个值，拿走最上面的
    bool getTop(T& x);//返回最上面的值
    bool IsEmpty()const{return (top==-1)?true:false;}
    bool IsFull() const { return (top == maxSize - 1) ? true : false; }
    int getSize()const{return top+1;}//top指向的是数组下标，0-maxSize-1
    void MakeEmpty(){top=-1;}//清空栈的内容
    /*template<class T>
    friend ostream& operator<<(ostream& os,SeqStack<T>& s);*/
private:
    T* elements;
    int top;
    int maxSize;
    void overflowProcess();
};
template<class T>
void SeqStack<T>::overflowProcess(){
    T* newarray=new T[maxSize+stackIncreament];
    for(int i=0;i<maxSize;i++){
        newarray[i]=elements[i];
    }
    delete[] elements;
    elements=newarray;
    top=maxSize-1;
    maxSize=maxSize+stackIncreament;
}
template<class T>
SeqStack<T>::SeqStack(int sz){
    maxSize=sz;
    elements= new T[maxSize];
    top=-1;
    assert(elements!=NULL);
}
template<class T>
void SeqStack<T>::Push(const T& x){
    if(top==-1){
        top=0;
        elements[top]=x;
    }
    else if(top==maxSize-1){
        overflowProcess();
        top++;
        elements[top]=x;
    }
    else if(top>-1){
        top++;
        elements[top]=x;
    }
}
template<class T>
bool SeqStack<T>::Pop(T& x){
    if(IsEmpty()==true) return false;
    x=elements[top];
    top--;
    return true;
}
template<class T>
bool SeqStack<T>::getTop(T& x){
    if(IsEmpty()==true) return false;
    x = elements[top];
    return true;
}
class calculatorplus{
    private:
    SeqStack<double> numstack;//存数据
    SeqStack<char> charstack;
    void AddOperand(double value);//进操作数栈
    bool get2o(double &left, double &right);//从栈中推出两个操作数
    void doo(char op);//形成运算指令，进行计算
    int isp(char x);
    int icp(char x);
    bool isdigit(char ch);
public:
    calculatorplus(int sz) : numstack(sz), charstack(sz) { charstack.Push('#'); }
    void postfix(string s,char* s1,int &count);
    void Run(char*s1,int count);
    void Clear();
};
bool calculatorplus::isdigit(char ch){
    if(ch>=48&&ch<=57)
        return true;
    else
        return false;
}
int calculatorplus::isp(char x){
    switch(x){
        case '#':
            return 0;
        case '(':
            return 1;
        case '*':case '/':case '%':
            return 5;
        case '+':case '-':
            return 3;
        case ')':
            return 6;
        default:
            cout << "wrong operation"<<endl ;
            return false;
    }
}
int calculatorplus::icp(char x){
     switch(x){
        case '#':
            return 0;
        case '(':
            return 6;
        case '*':case '/':case '%':
            return 4;
        case '+':case '-':
            return 2;
        case ')':
            return 1;
        default:
            cout << "wrong operation" << endl;
            return false;
    }
}
void calculatorplus::postfix(string s,char*s1,int &count) {
    char op = '#';

    //double newo;
    int i = 0;
    int len = s.length();
    while (charstack.IsEmpty() == false && s[i] != '#' && i < len) {
        if (isdigit(s[i])) {//输出数字
        	while(isdigit(s[i])){
			
            s1[count]=s[i];
			//cout<<s1[count]<<endl;
            i++;
            count++;}//cout<<"Af"<<endl;
            //cout << "num config" << endl;
            s1[count]=' ';
            count++;
        }
        else {
            charstack.getTop(op);
            if(op=='#'){
                charstack.Push(s[i]);
                //cout << "be the first op" << endl;
                i++;
            }
            else if (isp(op) < icp(s[i])) {
                charstack.Push(s[i]);
                i++;//优先级高，进栈
                //cout << "be higher in" << endl;
                charstack.getTop(op);
            }
            else if ((isp(op) > icp(s[i]))) {//优先级低，出栈至没有比它高的&&s[i]!=')'
                while( (isp(op) > icp(s[i]))&&isp(op)!='(') {
                    charstack.Pop(op);
                    s1[count]=op;
                    count++;//cout<<count<<endl;
                    charstack.getTop(op);
                    //cout << "pop and lower in" << endl;
                }
                if(s[i]!=')')
                charstack.Push(s[i]);
                i++;
            }
            else if(icp(s[i])==1){
                while(op!='(')
                {
                	s1[count]=op;//cout<<s1<<endl;
                count++; //cout << op << " ";
                charstack.getTop(op);}
                if(op=='(')
                    charstack.Pop(op);
                i++;
                //cout << "meet the)" << endl;
                        }
        }
    }
    char m='#'; 
    charstack.getTop(m);
    while(m != '#') {
        charstack.Pop(m);
        if(m!='('){
		
        s1[count]=m;//cout<<s1[count]<<endl;
        count++;}
        
        charstack.getTop(m);
    }
    s1[count]='#';
    
    //cout << '#' << " ";
}
void calculatorplus::doo(char op){
    double left, right, value;
    int result;
    result = get2o(left, right);
    if (result==true)
    switch(op){
        case '+':
            value = left + right;
            numstack.Push(value);
            break;
        case '-':
            value = left - right;
            numstack.Push(value);
            break;
        case '*':
            value = left * right;
            numstack.Push(value);
            break;
        case '/':
        if(right==0){
            cerr << "Divide by 0!" << endl;
            Clear();
        }
        else    {value = left / right;
            numstack.Push(value);}
            break;
    }
    else
        Clear();
}
bool calculatorplus::get2o(double& left,double& right){
    if(numstack.IsEmpty()==true) {
        cerr << "lack of right" << endl;
        return false;
    }
    numstack.Pop(right);
    if(numstack.IsEmpty()==true) {
        cerr << "lack of right" << endl;
        return false;
    }
    numstack.Pop(left);
    return true;
}
void calculatorplus::AddOperand(double value){
    numstack.Push(value);
}
void calculatorplus::Run(char*s1,int count){
	int temp=1;
	char ch;
	//double nums=0;
    double newOperand;
    int i=0;
    //cout<<s1[0]<<"s1[0]"<<endl;
    ch=s1[0];
    while (temp<=count&&ch!='#'){	
        switch(ch){
            case '+':case '-':case '*':case '/':
                doo(ch);
                //numstack.getTop(nums);
                //cout<<"nums"<<nums<<endl;
                //cout<<"op"<<endl;
                break;
            case ' '://cout<<" 123"<<endl;
            	break;
            default:
            	newOperand=int(ch-48);
            	//cout<<s1[temp-1]<<"Sfe"<<endl;
                while(s1[temp]>=48&&s1[temp]<=57){
                	newOperand=newOperand*10+(int)(s1[temp]-48);
                	temp++;
				}
				//cout<<"newoperand"<<newOperand<<endl;
                AddOperand(newOperand);
        }
        ch=s1[temp];temp++;
    }
    double t = 0;
    numstack.Pop(t);
    cout << t << endl;
}
void calculatorplus::Clear(){
    numstack.MakeEmpty();
    charstack.MakeEmpty();
}
int main(){
    
    SeqStack<int> seq(10);
    int temp = 0;
    /*for (int i = 1; i <= 9; i++)
		seq.Push(i);
    for (int m = 1; m <= 9;m++){
        seq.Pop(temp);
        cout << temp;
    }*///检验输出
    string s;
    while(cin >> s){
	seq.MakeEmpty();
    char s1[200];
    int count=0;
    //cout << s << endl;
    calculatorplus r1(50);
    //cout << "create success" << endl;
    r1.postfix(s,s1,count);    
	/*for(int i=0;i<=count;i++){	
    cout<<s1[i];}
    cout << endl;*/
    //cout << "postfix success" << endl;
    r1.Run(s1,count);
    r1.Clear();}
    return 0;
}

问题 F: 算法6-1~6-4：二叉链表存储的二叉树

题目描述

树形结构是一类重要的非线性数据结构，其中以树和二叉树最为常用。对于每一个结点至多只有两棵子树的一类树，称其为二叉树。二叉树的链式存储结构是一类重要的数据结构，其形式定义如下：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-txv2FVwW-1624035589333)(http://192.168.173.163/JudgeOnline/upload/pimg1341_1.png)]

而二叉树的前序、中序遍历是非常重要的能够访问二叉树所有结点的算法，下面分别列出一种先序遍历和两种中序遍历的算法。

在本题中，将会给出一个按照先序遍历得出的字符串，空格代表空的子节点，大写字母代表节点内容。请通过这个字符串建立二叉树，并按照题目描述中的一种先序遍历和两种中序遍历的算法分别输出每一个非空节点。

输入

输入只有一行，包含一个字符串S，用来建立二叉树。保证S为合法的二叉树先序遍历字符串，节点内容只有大写字母，且S的长度不超过100。

输出

共有三行，每一行包含一串字符，表示分别按先序、中序、中序得出的节点内容，每个字母后输出一个空格。请注意行尾输出换行。

样例输入

ABC  DE G  F

样例输出

A B C D E G F 
C B E G D F A 
C B E G D F A

提示

遍历是二叉树各种操作的基础，可以在遍历的过程中对节点进行各种操作。通过二叉树的遍历，可以建立二叉树。而先序、中序和后序遍历分别具有各自的特点，是探索二叉树性质的绝佳“武器”。

思路

几种遍历就是递归再递归，主要是顺序先后问题

重点在于先序遍历建立二叉链表

本来想整一个二叉树链表类，后来发现很麻烦，参考老师提供的二叉树代码，发现是使用一个根结点加上众多函数，剥离了类模板，使其方便使用

最坑的在于输出顺序是先序中序中序

代码

#include<iostream>
using namespace std;
struct TreeNode{
    struct TreeNode * lchild, *rchild;
    char val;
    TreeNode(char x): val(x), lchild(NULL), rchild(NULL){}
};
void create(TreeNode* &root){   	
	   char x;
	   if(scanf("%c",&x)!=EOF){	   
	   if(x == ' ')
             root = NULL;
         else{
                 root = new TreeNode(x);
                 create(root->lchild);
                 create(root->rchild);
		  }	}
}
void preorder(TreeNode* root){
    if(root){
        cout << root->val << " ";
        preorder(root->lchild);
        preorder(root->rchild);
    }
}
void inorder(TreeNode* root){
    if(root){
        
        inorder(root->lchild);
		cout << root->val << " ";
        inorder(root->rchild);
    }
}
void postorder(TreeNode* root){
    if(root){       
        postorder(root->lchild);		
        postorder(root->rchild);
		cout << root->val << " ";
    }
}
int main(){	
    TreeNode * root;//,* btree
    create(root);
    preorder(root);
    cout<<endl;
    inorder(root);
    cout<<endl;
    inorder(root);
    cout<<endl;
    return 0;
}