数据结构——二叉树

文章目录

• • • 非递归二叉树的前序遍历 计蒜客 - 141
    • 非递归二叉树的中序遍历 计蒜客 - 144
    • 非递归二叉树的后序遍历 计蒜客 - 140
    • 二叉树中序遍历 51Nod - 2064
    • 求先序排列 洛谷 - P1030
    • 新二叉树 洛谷 - P1305
    • 遍历问题 洛谷 - P1229
    • 美国血统 American Heritage 洛谷 - P1827
    • 淘汰赛 洛谷 - P4715
    • 二叉树深度 洛谷 - P4913
    • 二叉树结点公共祖先 CSG - 1012
    • 二叉树 OpenJ_Bailian - 2756
    • 二叉树 OpenJ_Bailian - 2788

非递归二叉树的前序遍历 计蒜客 - 141 非递归二叉树的中序遍历 计蒜客 - 144 非递归二叉树的后序遍历 计蒜客 - 140

问题描述

给定一个层数小于等于 10 的二叉树，输出对其遍历的节点名序列。

输入包括一行，为由空格分隔开的各节点，按照二叉树的分层遍历顺序给出，
每个节点形式如 X(Y,num)，X 表示该节点，Y 表示父节点，num 为 0,1,2 中的一个，
0 表示根节点，1 表示为父节点的左子节点，2 表示为父节点的右子节点。

【这里我将题目合在一起了】
输出为三行，为前序遍历，中序遍历，后序遍历的结果。

输入样例：

A(0,0) B(A,1) C(A,2) D(B,1) E(B,2) F(C,1) G(D,1) H(D,2)

输出样例：

A B D G H E C F
G D H B E A F C
G H D E B F C A

• 参考程序

#include
#include
using namespace std;
const int N=(1<<10);
char a[100], tree[N];
int n=0, m=0;
void preorder(char root){
    if(root=='') return;
    if(tree[0]==root) printf("%c", root);
    else printf(" %c", root);
    preorder(tree[2*root]);
    preorder(tree[2*root+1]);
}
void inorder(char root){
    if(root=='') return;
    inorder(tree[2*root]);
    if(m==n-1) {
        printf("%c", root); m++;
    } else {
        printf("%c ", root); m++;
    }
    inorder(tree[2*root+1]);
}
void postorder(char root){
    if(root=='') return;
    postorder(tree[2*root]);
    postorder(tree[2*root+1]);
    if(tree[0]==root) printf("%c", root);
    else printf("%c ", root);
}
int main(){
//    freopen("data.in", "r", stdin);
    while(~scanf("%s", a)){
        char x,y,num; sscanf(a, "%c(%c,%c)", &x,&y,&num);
        if(num=='0'){
            tree[0] = x;
        }else if(num=='1'){
            tree[2*y] = x;// y是单个字符，在内存中以ASCII码的形式进行存储
        }else if(num=='2'){
            tree[2*y+1] = x;
        }
    }
    preorder(tree[0]); printf("n");
    inorder(tree[0]);  printf("n");
    postorder(tree[0]);printf("n");
    return 0;
}

二叉树中序遍历 51Nod - 2064

问题描述

输入一个整数n（n <= 100000），表示二叉树中节点个数，编号为1~n。
约定1号节点为二叉树的根节点。
然后输入n行，每行包括两个整数，第i行表示编号为i的节点的左子节点和右子节点的编号。
如果某个节点没有左子节点，那么对应输行的第一个整数为0；
如果某个节点没有右子节点，那么对应行的第二个整数为0。
中序遍历输出此二叉树每个节点的编号，每行输出一个编号。

输入格式：第一行，一个整数n，接下来n行，每行有两个整数。
输出格式：输出n行，每行一个整数，表示节点编号。

输入样例

5
2 5
3 4
0 0
0 0
0 0

输出样例

3
2
4
1
5

• 参考程序

#include
#include
using namespace std;
const int N=1e5+0;
struct T{
    int l,r;
}tree[N];
void inorder(int m){
    if(m==0) return;
    inorder(tree[m].l);
    printf("%dn", m);
    inorder(tree[m].r);
}
int main(){
    int n; scanf("%d", &n);
    for(int i=1; i<=n; i++) {
        scanf("%d%d", &tree[i].l, &tree[i].r);
    }
    inorder(1);    
    return 0;
}

• 下列程序wa了，待调试

#include
#include
using namespace std;
const int N=2e5+10;
int tree[N];
void inorder(int i){
    if(tree[i]==0) return;
    inorder(2*i);
    printf("%dn", tree[i]);
    inorder(2*i+1);
}
int main(){
    int n; scanf("%d", &n);
    tree[1] = 1;
    for(int i=1; i<=n; i++){
        int lch, rch; scanf("%d%d", &lch,&rch);
        tree[2*i] = lch;
        tree[2*i+1] = rch;
    }
    inorder(1);
    return 0;
}

求先序排列 洛谷 - P1030

问题描述

给出一棵二叉树的中序与后序排列，求出它的先序排列。
（约定树结点用不同的大写字母表示，长度 ≤8）。

输入格式：2行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。
输出格式：1行，表示一棵二叉树的先序。

输入样例

BADC
BDCA

输出样例

ABCD

• 参考程序

#include
#include
using namespace std;
struct Node{
    char data;
    struct Node *lch,*rch;
};
string in,post;
Node* build(int pl,int pr,int il,int ir){
    if(pl>pr) return NULL;
    Node* root = new Node;
    root->data = post[pr];
    int k=il;
    while(post[pr]!=in[k] && k<=ir) k++;
    root->lch = build(pl,pl+k-il-1,il,k-1);
    root->rch = build(pl+k-il,pr-1,k+1,ir);
    return root;
}
void preorder(Node* root){
    if(root==NULL) return;
    cout<data;
    preorder(root->lch);
    preorder(root->rch);
}
int main(){
    cin>>in>>post; 
    Node* root=build(0, post.size()-1, 0, in.size()-1); 
    preorder(root);
    return 0;
}

• 参考程序

#include
#include
using namespace std;
void dfs(string bs, string cs){
    if(bs.length()==0) return;
    char root = cs[cs.length()-1];
    int id = bs.find(root);

    cout<
    string as,bs,cs;
    cin>>bs>>cs;
    dfs(bs, cs);
    return 0; 
} 

新二叉树 洛谷 - P1305

问题描述
输入一串二叉树，输出其前序遍历。

输入格式
第一行为二叉树的节点数 n(1≤n≤26)。
后面 n 行，每一个字母为节点，后两个字母分别为其左右儿子。
空节点用 * 表示

输出格式：二叉树的前序遍历。

输入样例：

6
abc
bdi
cj*
d**
i**
j**

输出样例：

abdicj

• 参考程序

#include
#include
using namespace std;
const int N=1e5+10;
char tree[N][2], root; 
void dfs(char x){
    if(root=='*') return;
    cout<
    int n; cin>>n;
    for(int i=1; i<=n; i++){
        char a,b,c; cin>>a>>b>>c;
        if(i==1)  root=a;//确定根节点 
        tree[a][0]=b, tree[a][1]=c;
    }
    dfs(root);
    return 0;
}

遍历问题 洛谷 - P1229

问题描述

我们都很熟悉二叉树的前序、中序、后序遍历，在数据结构中常提出这样的问题：
已知一棵二叉树的前序和中序遍历，求它的后序遍历，
相应的，已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。
然而给定一棵二叉树的前序和后序遍历，你却不能确定其中序遍历序列，

输入格式：
输A数据共两行，第一行表示该二叉树的前序遍历结果s1，
第二行表示该二叉树的后序遍历结果s2。

输出格式：输出可能的中序遍历序列的总数，结果不超过长整型数。
输入样例：

abc
cba

输出样例:4

• 分析

确定中序遍历的数量在于含有一个孩子结点的结点个数 N，而可能是左右孩子，所以最后结果为 2^N。

• 参考程序

#include
using namespace std;
int main(){
    string as,cs; cin>>as>>cs;
    int ans=0;
    for(int i=0; i
        for(int j=1; j
            // ab - ba 
            if(as[i]==cs[j]&&as[i+1]==cs[j-1]) ans++;
        }
    }
    cout<<(1< 
思考改进
 
对于已知先后遍历结果，可以求出中序遍历的方案数，输出任意一种中序遍历结果。
 
 
美国血统 American Heritage 洛谷 - P1827 
问题描述
 
农夫约翰非常认真地对待他的奶牛们的血统。
 然而他不是一个真正优秀的记帐员。
 他把他的奶牛们的家谱作成二叉树，并且把二叉树以更线性的“树的中序遍历”
 和“树的前序遍历”的符号加以记录而不是用图形的方法。
 
你的任务是在被给予奶牛家谱的“树中序遍历”和“树前序遍历”的符号后，
 创建奶牛家谱的“树的 后序遍历”的符号。
 每一头奶牛的姓名被译为一个唯一的字母。
 （你可能已经知道你可以在知道树的两 种遍历以后可以经常地重建这棵树。）
 显然，这里的树不会有多于 26 个的顶点。
 这是在样例输入和 样例输出中的树的图形表达方式：
 
　　　 C
      /  
　   /   
　　B　   G
　 / 　　/
  A   D  H
 　  / 
　　 E  F
 
输入格式
 第一行： 树的中序遍历
 第二行： 同样的树的前序遍历
 
输出格式：单独的一行表示该树的后序遍历。
 
输入样例
 
ABEDFCHG
CBADEFGH 
 
输出样例
 
AEFDBHGC
 
参考程序
 
#include
using namespace std;
string as, bs, cs;
void dfs(string bs, string as){
    if(bs.length()==0) return;
    char root = as[0];
    int id = bs.find(root);

    dfs(bs.substr(0,id), as.substr(1,id));//左 
    dfs(bs.substr(id+1), as.substr(id+1));//右 
    cout<
    cin>>bs>>as;
    dfs(bs, as);
    return 0; 
} 
 
淘汰赛 洛谷 - P4715 
问题描述
 
有 2^n (n≤7) 个国家参加世界杯决赛圈且进入淘汰赛环节。
 已经知道各个国家的能力值，且都不相等。
 能力值高的国家和能力值低的国家踢比赛时高者获胜。
 1 号国家和 2 号国家踢一场比赛，胜者晋级。
 3 号国家和 4 号国家也踢一场，胜者晋级…
 晋级后的国家用相同的方法继续完成赛程，直到决出冠军。
 给出各个国家的能力值，请问亚军是哪个国家？
 
输入格式
 第一行一个整数 n，表示一共 2^n个国家参赛。
 第二行 2^n 个整数，第 i 个整数表示编号为 i 的国家的能力值（1≤i≤2^n）。
 数据保证不存在平局。
 
输出格式：仅一个整数，表示亚军国家的编号。
 
输入样例：
 
3
4 2 3 1 10 5 9 7
 
输出样例：1
 
参考程序
 
#include
#include 
#include
#include