《算法笔记》树与二叉树专题练习

1、复原二叉树（由前序和中序求后序）

题目描述 小明在做数据结构的作业，其中一题是给你一棵二叉树的前序遍历和中序遍历结果，要求你写出这棵二叉树的后序遍历结果。 输入 输入包含多组测试数据。每组输入包含两个字符串，分别表示二叉树的前序遍历和中序遍历结果。每个字符串由不重复的大写字母组成。 输出 对于每组输入，输出对应的二叉树的后续遍历结果。

DBACEGF ABCDEFG
BCAD CBAD

ACBFGED
CDAB

#include <iostream>
#include<cstring>
using namespace std;
const int maxN=1000;
//分别存储前序序列、中序序列
char pre[maxN],in[maxN];

struct Node
{
  char data;
  Node* lchild;
  Node* rchild;
};
//根据前序序列和中序序列构建一棵二叉树
Node* create(int preL,int preR,int inL,int inR)
{
    if(preL>preR)return NULL;//递归边界，前序序列长度小于等于0时结束
    Node* root=new Node;//创建根节点
    root->data=pre[preL];//先序序列的第一个就是根节点
    int k;
    for(k=inL;k<=inR;k++)
    {
        if(in[k]==pre[preL])break;//找到根节点在中序序列中的位置
    }
    int numLeft=k-inL;//左子树的节点个数
    //注意区间
    root->lchild=create(preL+1,preL+numLeft,inL,k-1);
    root->rchild=create(preL+numLeft+1,preR,k+1,inR);
    return root;
}
//二叉树的后序遍历，左右根顺序
void postOrder(Node* root)
{
    if(root==NULL)return;
    postOrder(root->lchild);
    postOrder(root->rchild);
    printf("%c",root->data);
}
int main()
{
    while(scanf("%s%s",pre,in)!=EOF)
    {
        int preLen=strlen(pre);
        int inLen=strlen(in);
        Node* root=create(0,preLen-1,0,inLen-1);
        postOrder(root);
        printf("\n");
    }

    return 0;
}

2、二叉树遍历

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

输入

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

输出

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

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

a b f e d c 
a

#include<iostream>
#include<cstring>
using namespace std;

char pre[105];
int pos;
struct Node
{
  char data;
  Node* lchild;
  Node* rchild;
    
};
//创建空节点
Node* createNode()
{
    Node* node=new Node;
    node->lchild=NULL;
    node->rchild=NULL;
    return node;
}
//创建二叉树
Node* createTree()
{
    int len=strlen(pre);
    if(len==0||pos==len)return NULL;//数据为空或已经遍历完
    if(pre[pos]=='#')//空树，直接遍历下一个，然后返回空
    {
        pos++;
        return NULL;
    }
    Node* root=createNode();//先创建一个根节点
    root->data=pre[pos++];
    //递归创建左右子树
    root->lchild=createTree();
    root->rchild=createTree();
    return root;
}
//二叉树的中序遍历，左根右顺序
void inOrder(Node* root)
{
    if(root==NULL)return;
    inOrder(root->lchild);
    printf("%c ",root->data);
    inOrder(root->rchild);
}
int main()
{
    while(scanf("%s",pre)!=EOF)
    {
        pos=0;
        Node* root=createTree();
        inOrder(root);
        printf("\n");
    }
    return 0;
}