9. 二叉树的遍历问题

题目来源和说明

2006年清华大学计算机研究生机试真题，本题设计二叉树的建立、由二叉树的两种遍历还原二叉树、二叉树的遍历等多种知识点。希望通过本题梳理和总结二叉树的各种知识点~

题目描述

根据先序和中序遍历，还原二叉树，并后续遍历树，打印结果

样例

输入：
ABC
BAC
FDXEAG
XDEFAG
输出：
BCA
XEDGAF

C++ 代码

#include<iostream>
#include<string.h>
using namespace std;

struct Node {
    Node *l;
    Node *r;
    char c;
}Tree[50];

int idx;

Node *create() { //申请一个节点空间，返回指向其的指针
    Tree[idx].l=NULL;
    Tree[idx].r=NULL;
    return &Tree[idx++]; //返回指针，且idx累加
}

char str1[30]; //先序遍历结果
char str2[30];//中序遍历结果

void postOrder(Node *T) { //后续遍历
    if(T->l!=NULL) {
        postOrder(T->l);
    }
    if(T->r!=NULL) {
        postOrder(T->r);
    }
    printf("%c",T->c);
}

Node* build(int s1,int e1,int s2,int e2) {
    //由字符串的前序遍历和中序遍历还原树，并返回根节点
    Node* ret=create(); //为该树根节点申请空间
    ret->c=str1[s1];
    int rootIdx;
    for(int i=s2;i<=e2;i++) { //查找根节点再中序遍历中的位置
        if(str2[i]==str1[s1]) {
            rootIdx=i;
            break;
        }
    }
    if(rootIdx!=s2) { //左树不为空
        ret->l=build(s1+1,s1+(rootIdx-s2),s2,rootIdx-1);
    }
    if(rootIdx!=e2) { //右树不为空
        ret->r=build(s1+(rootIdx-s2)+1,e1,rootIdx+1,e2);
    }
    return ret;//返回根节点
}
int main() {
    while(scanf("%s",str1)!=EOF) {
        scanf("%s",str2);//输入
        idx=0;
        int l1=strlen(str1);
        int l2=strlen(str2);
        Node *T=build(0,l1-1,0,l2-1); //递归还原整个树
        postOrder(T); //后续遍历
        printf("\n"); 
    }
    return 0;
}

同类题目

C++代码

2. 二叉树遍历

https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpId=60&tqId=29483&tPage=1&ru=/kaoyan/retest/1001&qru=/ta/tsing-kaoyan/question-ranking

简要分析

该问题是根据前序遍历序列还原树，并打印中序遍历的结果。我们只需要基于上面的例题改动就行。首先就是打印函数，就调整一下三条语句之间的顺序，即将printf("%c",T->c)放在中间就行了。然后就是改变一下build函数。具体的代码如下：

C++代码

#include<iostream>
#include<string.h>
using namespace std;

struct Node {
    Node *l;
    Node *r;
    char c;
}Tree[50];

int idx;

Node *create() { //申请一个节点空间，返回指向其的指针
    Tree[idx].l=NULL;
    Tree[idx].r=NULL;
    return &Tree[idx++]; //返回指针，且idx累加
}

char str[30]; //先序遍历结果
int pos=0;
void inOrder(Node *T) { //后续遍历
    if(T->l!=NULL) {
        inOrder(T->l);
    }
    printf("%c",T->c);
    if(T->r!=NULL) {
        inOrder(T->r);
    }
}

Node* build() { //pos为字符的下标
    char c=str[pos++];
    if(c=='#') return NULL;
    Node *root=create();
    root->c=c;
    root->l=build();
    root->r=build();
    return root;
}
int main() {
   while(scanf("%s",str)!=EOF) {
     Node* root=build();
     inOrder(root);
     printf("\n");
   }
}

3.树查找

https://www.nowcoder.com/questionTerminal/9a10d5e7d99c45e2a462644d46c428e4

简要分析

题目要求输出每一层的节点，只需找出每一层的起点和终点的下标规律即可。

C++代码

#include<iostream>
#include<cmath>
const int N=1005;

int tree[N];
int main() {
    int n,d;
    while(scanf("%d",&n)!=EOF) {
        for(int i=1;i<=n;i++) {
            scanf("%d",&tree[i]);
        }
        scanf("%d",&d);
        int st=(int)pow(2,d-1);
        if(st>n){
            printf("EMPTY\n");
        }
        else {
            int en=pow(2,d)-1>n? n : (int)pow(2,d)-1;
            for(int i=st;i<=en;i++) {
                printf("%d ",tree[i]);
            }
            printf("\n");
        }
    }
}

3.二叉树