二叉树的遍历

题目：

​ 编写一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。

例如如下的先序遍历字符串： abc##de#g##f### 其中 # 表示的是空格，空格字符代表空树。

建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。

输入格式：

共一行，包含一个字符串，表示先序遍历字符串。

输出格式

共一行，输出将输入字符串建立二叉树后中序遍历的序列，字符之间用空格隔开。

注意，输出中不用包含 #。

数据范围

输入字符串长度不超过 100100，且只包含小写字母和 #。

输入样例：

abc##de#g##f###

输出样例：

c b e g d f a

解题思路：

​ 给定先序遍历，求中序遍历。

​ 首先我们要知道什么是先序遍历和后序遍历。

• 先序遍历（Preorder Traversal）：先访问根节点，再递归地遍历左子树和右子树。先序遍历的顺序是根节点 -> 左子树 -> 右子树。
• 中序遍历（Inorder Traversal）：先递归地遍历左子树，再访问根节点，最后递归地遍历右子树。中序遍历的顺序是左子树 -> 根节点 -> 右子树。
• 后序遍历（Postorder Traversal）：先递归地遍历左子树和右子树，再访问根节点。后序遍历的顺序是左子树 -> 右子树 -> 根节点。

​ 于是我们以样例为例，画出先序遍历，如下图

​

​ 然后我们就可以发现，只要我们在每次搜到空树的时候，即回溯到该节点的父节点后，将当前节点（上一个节点的父节点）时，将其输出就能得到中序遍历。因为每次回溯到的点，都是一个父亲节点，且回溯到了这个点，说明其子节点也已经回溯过了，即输出过了。

AC代码如下：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int k;
string str;

void dfs()
{
    if (str[k] == '#')  //遍历到了空树，回溯的同时，遍历下一个节点
    {
        k ++;
        return;
    }
    char t = str[k ++];     //记录当前节点
    dfs();  //遍历左子树，直至走到空树，
    cout << t << " ";
    dfs();  //遍历右节点，直至走到空树
}

int main()
{
    cin >> str;
    
    dfs();
    
    return 0;
}

Go语言版

package main

import (
    "fmt"
    "bufio"
    "os"
)

var in = bufio.NewReader(os.Stdin)
var k int
var str string

func dfs(){
    if str[k] == '#' {
        k ++
        return
    }
    
    t := str[k]
    k ++
    dfs()
    fmt.Printf("%c ", t)
    dfs()
}

func main(){
    fmt.Fscan(in, &str)
    
    dfs()
    
    return
}