二叉树的遍历图解例题都有哪些?二叉树详解

TheDisguiser 2020-07-05 22:38:30 java常见问答 7411

二叉树是在一般面试中是必问的问题之一,小伙伴们知道为什么吗?因为它是最稳定的数据结构之一,下面我们就来看下常见的二叉树遍历题吧。

例1:已知前序遍历和后序遍历,求中序遍历。

思路:前序遍历的第一个元素是根。

若只有左子树,则前序遍历的第二个元素和后序遍历的倒数第二个元素相同,且都是左子树的根;

若只有右子树,则前序遍历的第二个元素和后序遍历的倒数第二个元素相同,且都是右子树的根;

若既有左子树又有右子树,则前序遍历的第二个元素是左子树的根,后序遍历的倒数第二个元素是右子树的根;

即,若前序遍历的第二个元素和后序遍历的倒数第二个元素相同,则对于当前根结点来说有两种可能,要么只有左子树,要么只有右子树。这两种情况下,前序遍历是相同的,后序遍历也是相同的,但中序遍历不同。

(1)求任意一种中序遍历。

#include<cstdio>
#include<vector>
#include<map>
using namespace std;
const int MAXN = 30 + 10;
int pre[MAXN], pos[MAXN];
int cnt;
map < int, int > mp1;
map < int, int > mp2;
vector < int > ans;
void dfs(int prL, int prR, int poL, int poR, int root)
{
    if (prL > prR) return;
    if (prL == prR)
    {
        ans.push_back(root);
        return;
    }
    int tmp1 = pre[prL + 1];
    int tmp2 = pos[poR - 1];
    if (tmp1 != tmp2)
    {
        dfs(mp1[tmp1], mp1[tmp2] - 1, poL, mp2[tmp1], pre[mp1[tmp1]]);
        ans.push_back(root);
        dfs(mp1[tmp2], prR, mp2[tmp1] + 1, poR - 1, pre[mp1[tmp2]]);
    }
    else
    {
        ++cnt;
        dfs(mp1[tmp1], prR, poL, mp2[tmp1], pre[mp1[tmp1]]);
        ans.push_back(root);
    }
}
int main()
{
    int N;
    scanf("%d", & N);
    for (int i = 0; i < N; ++i)
    {
        scanf("%d", & pre[i]);
        mp1[pre[i]] = i;
    }
    for (int i = 0; i < N; ++i)
    {
        scanf("%d", & pos[i]);
        mp2[pos[i]] = i;
    }
    int root = pre[0];
    dfs(0, N - 1, 0, N - 1, root);
    if (cnt >= 1) printf("No\n");
    else printf("Yes\n");
    int len = ans.size();
    for (int i = 0; i < len; ++i)
    {
        printf("%d", ans[i]);
        if (i == len - 1) printf("\n");
        else printf(" ");
    }
    return 0;
}

(2)求中序遍历可能的种数。

#include<cstdio>
#include<vector>
#include<map>
using namespace std;
const int MAXN = 10000 + 10;
const int MOD = 1000000000;
int pre[MAXN], pos[MAXN];
int cnt;
map < int, int > mp1;
map < int, int > mp2;
int ans[MAXN];
void dfs(int prL, int prR, int poL, int poR)
{
    if (prL >= prR) return;
    int tmp1 = pre[prL + 1];
    int tmp2 = pos[poR - 1];
    if (tmp1 != tmp2)
    {
        dfs(mp1[tmp1], mp1[tmp2] - 1, poL, mp2[tmp1]);
        dfs(mp1[tmp2], prR, mp2[tmp1] + 1, poR - 1);
    }
    else
    {
        ++cnt;
        dfs(prL + 1, prR, poL, poR - 1);
    }
}
void solve(int n, int k)
{ //将最终的结果每隔9位数存在ans数组中
    int len = 1;
    ans[1] = 1;
    while (k--)
    {
        for (int i = 1; i <= len; ++i)
        {
            ans[i] *= n;
        }
        for (int i = 1; i <= len; ++i)
        {
            ans[i + 1] += ans[i] / MOD;
            ans[i] %= MOD;
        }
        if (ans[len + 1]) ++len;
    }
    for (int i = len; i >= 1; --i)
    {
        if (i == len) printf("%d", ans[i]);
        else printf("%09d", ans[i]);
    }
    printf("\n");
}
int main()
{
    int N;
    scanf("%d", & N);
    for (int i = 0; i < N; ++i)
    {
        scanf("%d", & pre[i]);
        mp1[pre[i]] = i;
    }
    for (int i = 0; i < N; ++i)
    {
        scanf("%d", & pos[i]);
        mp2[pos[i]] = i;
    }
    dfs(0, N - 1, 0, N - 1);
    solve(2, cnt); //计算2的cnt次方,不取模
    return 0;
}

例2:已知前序遍历和中序遍历,求后序遍历。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 50000 + 10;
int pre[MAXN], in [MAXN];
vector < int > ans;
void dfs(int pL, int pR, int iL, int iR, int root)
{
    if (pL > pR) return;
    int id = iL;
    while ( in [id] != root) ++id;
    int cnt = id - iL;
    dfs(pL + 1, pL + cnt, iL, id - 1, pre[pL + 1]);
    dfs(pL + cnt + 1, pR, id + 1, iR, pre[pL + cnt + 1]);
    ans.push_back(root);
}
int main()
{
    int N;
    scanf("%d", & N);
    for (int i = 0; i < N; ++i)
    {
        scanf("%d", & pre[i]);
    }
    for (int i = 0; i < N; ++i)
    {
        scanf("%d", & in [i]);
    }
    int root = pre[0];
    dfs(0, N - 1, 0, N - 1, root);
    printf("%d\n", ans[0]);
    return 0;
}

例3:给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100 + 10;
int post[MAXN], in [MAXN];
int lchild[MAXN], rchild[MAXN];
vector < int > ans;
int dfs(int pL, int pR, int iL, int iR, int root)
{
    if (pL > pR) return 0;
    int id = iL;
    while ( in [id] != root) ++id;
    int cnt = id - iL;
    lchild[root] = dfs(pL, pL + cnt - 1, iL, id - 1, post[pL + cnt - 1]);
    rchild[root] = dfs(pL + cnt, pR - 1, id + 1, iR, post[pR - 1]);
    return root;
}
void bfs(int root)
{
    queue < int > q;
    q.push(root);
    while (!q.empty())
    {
        int x = q.front();
        ans.push_back(x);
        q.pop();
        if (lchild[x]) q.push(lchild[x]);
        if (rchild[x]) q.push(rchild[x]);
    }
}
int main()
{
    int N;
    scanf("%d", & N);
    for (int i = 0; i < N; ++i)
    {
        scanf("%d", & post[i]);
    }
    for (int i = 0; i < N; ++i)
    {
        scanf("%d", & in [i]);
    }
    int root = post[N - 1];
    dfs(0, N - 1, 0, N - 1, root);
    bfs(root);
    int len = ans.size();
    for (int i = 0; i < len; ++i)
    {
        printf("%d", ans[i]);
        if (i == len - 1) printf("\n");
        else printf(" ");
    }
    return 0;
}

以上就是本篇文章的所有内容了,对于二叉树你了解了吗?如果还想知道一些其他java程序代码例子,可以来关注我们的网站了解详情。

推荐阅读;

二叉树转化为森林例子要怎么实现?步骤有哪些?

二叉树的遍历算法有哪些?通常用在何处?

二叉树的度是什么意思?二叉树是什么?