树2

· · 个人记录

树的输入

常见的输入树的方式

  1. 给定左右儿子
  2. 输入边，u到v的边
  3. 第i个节点的父亲节点（i>=2）
4//表示一共有n个点
//因为i>=2，所以1没有父亲节点
1//表示2的父亲节点是1
2//表示3的父亲节点是2
3//表示4的父亲节点是3

树的遍历

常见的遍历顺序

  1. 先序遍历（前序）
  2. 中序遍历
  3. 后序遍历

指的是根的遍历顺序

  1. 层序遍历

先序遍历（前序）

遍历顺序

根-左节点-有节点

void dfs(int u)
{
    //输出u节点
    //遍历左节点
    //遍历右节点
}

例题

请前序遍历这棵树

遍历过程

现遍历1大块，把根节点输出，遍历左节点所在大块

遍历2大块，把根节点输出，遍历左节点所在大块

遍历3大块，把根节点输出，遍历左节点所在大块

没有左大块了，输出，遍历右节点所在大块

没有右大块了，输出，回到2大块的右节点所在大块

遍历4大块，输出根节点，遍历左节点所在大块

没有左大块了，输出，遍历右节点所在大块

没有右大块了，输出，回到1大块的右节点所在大块

遍历5大块，输出根节点，遍历他的唯一子节点所在的大块

遍历6大块，输出根节点，遍历左节点所在大块

没有左大块了，输出，遍历右节点所在大块

没有右大块了，输出，回到1大块的右节点所在大块

遍历结束

最终输出

输出：1.2.4.7.8.5.9.10.3.11.20.23

中序遍历

遍历顺序

左节点-根-有节点

void dfs(int u)
{
    //遍历左节点
    //输出u节点
    //遍历右节点
}

例题

请中序遍历这棵树

遍历过程

现遍历1大块，遍历左节点所在大块

遍历2大块，遍历左节点所在大块

遍历3大块，遍历左节点所在大块

没有左大块了，输出，回到3大块

输出3大块的根节点，遍历右节点所在大块

没有右大块了，输出，回到2大块

输出2大块的根节点，遍历右节点所在大块

遍历4大块，遍历左节点所在大块

没有左大块了，输出，回到4大块

输出4大块的根节点，遍历右节点所在大块

没有右大块了，输出，回到1大块

输出1大块的根节点，遍历右节点所在大块

遍历5大块，输出根节点，遍历他的唯一子节点所在的大块

遍历6大块，遍历左节点所在大块

没有左大块了，输出，回到6大块

输出6大块的根节点，遍历右节点所在大块

没有右大块了，输出，回到1大块的右节点所在大块

遍历结束

最终输出

输出：7.4.8.2.9.5.10.1.3.20.11.23

后序遍历

遍历顺序

左节点-有节点-根

void dfs(int u)
{
    //遍历左节点
    //遍历右节点
    //输出u节点
}

例题

请后序遍历这棵树

前两题的例题过程较详细，就不写过程了

最终答案

7.8.4.9.10.5.2.20.23.11.3.1

例题

前序遍历：ABCD

中序遍历：BADC

后序遍历：？

得到了这样的树：

答案

后序遍历：BCDA

例题

P1305 新二叉树

代码

#include<bits/stdc++.h>
using namespace std ;
/*
这题我们需要存左右儿子，我用的是邻接表，再dfs把图遍历出来，唯独要注意的是，是前序遍历
*/
vector<int> G[100005] ;//邻接表
void dfs(int u)//前序遍历
{
    cout << char(u) ;//根-左节点-有节点
    for( int i = 0 ; i < G[u].size() ; i++ )
    {
        dfs(G[u][i]) ;
    }
}
int main()
{
    int n ;
    cin >> n ;
    char d ;
    for( int i = 1 ; i <= n ; i++ )
    {
        char a , b , c ;
        cin >> a >> b >> c ;
        if(i == 1) d = a ;//题目保证第一个是根节点
        if(b != '*') G[a].push_back(b) ;
        if(c != '*') G[a].push_back(c) ;
    }
    dfs(d) ;
    return 0 ;
}

P1030 [NOIP2001 普及组] 求先序排列

代码

#include<bits/stdc++.h> 
using namespace std ;
/*
主要是考察模拟能力，总体来说不是很难，就是要注意分段的时候，别把自己也分进去了
*/
void dfs(string zx , string hx)//zx是中序，hx是后序
{
    if(zx == "") return ;//为空退出
    char c = hx[hx.size() - 1] ;//根节点是最后一个
    cout << c ;
    int pos = zx.find(c) ;//模拟
    dfs(zx.substr(0 , pos) , hx.substr(0 , pos)) ;//前半段
    dfs(zx.substr(pos + 1) , hx.substr(pos , hx.size() - 1 - pos)) ;//后半段
}
int main()
{
    string hx , zx ;
    cin >> zx >> hx ;
    dfs(zx , hx) ;
    return 0 ;
}