《算法笔记》9.2小节——数据结构专题(2)-＞二叉树的遍历 问题 D: 二叉树遍历

题目描述

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。
例如如下的先序遍历字符串：
ABC##DE#G##F###
其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

输入

输入包括1行字符串，长度不超过100。

输出

可能有多组测试数据，对于每组数据，
输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。
每个输出结果占一行。

样例输入

a#b#cdef#####
a##

样例输出

a b f e d c 
a 

分析：给出的序列是前序遍历序列，可以用栈来保存节点，模拟前序遍历。注意退栈时，如果当前栈顶元素的右孩子已经填充过（不管是‘#’还是字母），就要继续退栈。

#include    <algorithm>
#include     <iostream>
#include      <cstdlib>
#include      <cstring>
#include       <string>
#include       <vector>
#include       <cstdio>
#include        <queue>
#include        <stack>
#include        <ctime>
#include        <cmath>
#include          <map>
#include          <set>
#include<unordered_map>
#define INF 0x3f3f3f3f
#define db1(x) cout<<#x<<"="<<(x)<<endl
#define db2(x,y) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<endl
#define db3(x,y,z) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<endl
#define db4(x,y,z,a) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#a<<"="<<(a)<<endl
#define db5(x,y,z,a,r) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#a<<"="<<(a)<<", "<<#r<<"="<<(r)<<endl
using namespace std;

typedef struct node
{
    char val;
    struct node *left,*right;
    int flag_l,flag_r,flag;//三个标志分别标志左孩子、右孩子、自己是否已经填充
}node;

void Free(node *root)
{
    if(root->left!=NULL)Free(root->left);
    if(root->right!=NULL)Free(root->right);
    free(root);
    return;
}

void mid_order(node *root)
{
    if(root==NULL)return;
    mid_order(root->left);
    printf("%c ",root->val);
    mid_order(root->right);
    return;
}

int main(void)
{
    #ifdef test
    freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    clock_t start=clock();
    #endif //test

    char pre[1100];
    while(~scanf("%s",pre))
    {
        stack<node*>sta;
        node *root=(node*)malloc(sizeof(node));
        root->flag_l=root->flag_r=root->flag=0;
        root->left=root->right=NULL;
        sta.push(root);

        int len=strlen(pre);
        for(int i=0;i<len;++i)
        {
            node *temp=sta.top();
            if(pre[i]!='#')//不为空
            {
                if(temp->flag==0)temp->val=pre[i],temp->flag=1;//自己还没填，先填自己
                else if(temp->flag_l==0)//自己填了，填左子树
                {
                    node *p=(node*)malloc(sizeof(node));
                    p->val=pre[i];p->flag_l=p->flag_r=0,p->flag=1;p->left=p->right=NULL;
                    temp->flag_l=1,temp->left=p;sta.push(p);//把左孩子进栈，接下来填左子树
                }
                else if(temp->flag_r==0)//自己、左孩子都填了，填右子树
                {
                    node *p=(node*)malloc(sizeof(node));
                    p->val=pre[i];p->flag_l=p->flag_r=0,p->flag=1;p->left=p->right=NULL;
                    temp->flag_r=1,temp->right=p;sta.push(p);//把右孩子进栈，接下来填右子树
                }
            }
            else//为空。自己肯定不为空，因为空节点不会进栈
            {
                if(temp->flag_l==0)temp->flag_l=1;//左子树先为空
                else if(temp->flag_r==0)//左子树已经有了，右子树为空
                {
                    temp->flag_r=1;//出栈要一直出到右子树还没填的节点
                    while(!sta.empty()&&sta.top()->flag_r==1)
                        sta.pop();
                }
            }
        }
        mid_order(root);
        printf("\n");
        Free(root);
    }

    #ifdef test
    clockid_t end=clock();
    double endtime=(double)(end-start)/CLOCKS_PER_SEC;
    printf("\n\n\n\n\n");
    cout<<"Total time:"<<endtime<<"s"<<endl;        //s为单位
    cout<<"Total time:"<<endtime*1000<<"ms"<<endl;    //ms为单位
    #endif //test
    return 0;
}