二叉树的遍历及重建

二叉树的遍历及重建

二叉树的遍历

我们知道二叉树是一种常用的数据结构,包括内部节点和叶节点,每个节点有0-2个子女。对于一棵二叉树来说,我们一般从根节点开始遍历每个节点。二叉树的遍历一般有三种方法:前序遍历、中序遍历和后序遍历。

D

/ \

/  \

B    E

/ \    \

/  \    \

A    C    G

/

/

F

对于如上所示的二叉树,三种遍历访问的顺序分别是:

前序遍历:DBACEGF
  中序遍历:ABCDEFG
  后序遍历:ACBFGED

从中可以发现,前序遍历一定从根节点开始,后序遍历一定以根节点结束。再结合中序遍历的顺序,可以发现这样的规律对于一棵二叉树的子树来说也是成立的。如左子树前中后遍历顺序分别为:BAC、ABC和ACB。

二叉树的重建

如果我们给出三种遍历结果中的一个或两个,能不能把整棵树的结构重建出来呢?很明显,根据单个遍历结果是不能重建一棵二叉树的,而由于前序遍历和后序遍历没有保存根节点的位置信息,所以也不能根据前序遍历和后序遍历重建一棵二叉树。也就说由中序遍历结果和前序遍历或后序遍历中的一种,我们就能重建一棵二叉树。

相关例题

这里有两道重建二叉树的题目,可以供大家练习。

1. 前序和中序重建二叉树转后序遍历(POJ 2255 二叉树重建)

题目链接:?id=2255
AC代码:

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;

struct node
{
    char c;
    node* left;
    node* right;
};
string s1,s2;

node* buildtree(int l1,int r1,int l2,int r2)
{
    if(l1>r1)  return NULL;
    int temp=0;
    node* now=new node;
    now->c=s1[l1];
    if(l1==r1){
        now->left=NULL;
        now->right=NULL;
        return now;
    }
    for(int i=l2;i<=r2;i++){
        if(s2[i]==s1[l1]){
            temp=i;
            break;
        }
    }
    now->left=buildtree(l1+1,l1+temp-l2,l2,temp-1);
    now->right=buildtree(l1+temp-l2+1,r1,temp+1,r2);
    return now;
}

void post_order(node* root)
{
    if(root==NULL)  return;
    post_order(root->left);
    post_order(root->right);
    printf("%c",root->c);
}

int main()
{
    while(cin>>s1>>s2){
        node* tree=buildtree(0,s1.length()-1,0,s2.length()-1);
        post_order(tree);
        printf("\n");
    }
    return 0;
}

2. 中序和后序重建二叉树转前序遍历(POJ 由中根序列和后根序列重建二叉树)

题目链接:
AC代码:

#include<bits/stdc++.h>
using namespace std;
#define eps 1e-8
#define INF 0x3f3f3f3f
const int num=1e6;

int a[num+5],b[num+5],n[num+5],ans[num+5],cnt;
struct node{
    int x;
    node* left;
    node* right;
    node(int _x=0){
        x=_x;
        left=NULL;
        right=NULL;
    }
};

node* buildtree(int l1,int r1,int l2,int r2)
{
    //cout<<l1<<' '<<r1<<' '<<l2<<' '<<r2<<"###"<<endl;
    if(l1>r1)  return NULL;
    if(l1==r1){
        node* nd=new node(a[l1]);
        return nd;
    }
    node* nd=new node(b[r2]);
    int tmp=b[r2],id=l1;
    for(int i=l1;i<=r1;i++){
        if(a[i]==tmp){
            id=i;
            break;
        }
    }
    nd->left=buildtree(l1,id-1,l2,l2+id-l1-1);
    nd->right=buildtree(id+1,r1,l2+id-l1,r2-1);
    return nd;
}

void pre_order(node* nd){
    if(nd==NULL)    return;
    ans[cnt++]=nd->x;
    pre_order(nd->left);
    pre_order(nd->right);
}

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/90ead88c22f29841ca1098450562cc0b.html