2.7 binary tree, post order traversal - [FBI tree]

Title Description

Input description

The first line is an integer N（0<=N<=10）
The second line is a length of 2^N Of “01” strand .

Output description

Output a string , namely FBI The subsequent traversal sequence of the tree .

I/o sample

Input ：

3
10001011

Output ：

IBFBBBFIBFIIIFF

---

The final code

1. c/c++

#include <bits/stdc++.h>
using namespace std;
char s[2000],tree[280000]; //tree[] Full binary tree 



// First, the leaf node has a value , Then determine the value of the parent node according to the value of the leaf node 
void build_FBI(int k,int left,int right)
{
    
         // Reach the leaf node 
        if(left==right)
        {
         
        if(s[right]=='1') tree[k]='I';
        else tree[k]='B';
        return;
        }
        
        int mid=(left+right)/2;      // Split in two 
        build_FBI(2*k,left,mid);     // Recursive left half 
        build_FBI(2*k+1,mid+1,right); // Recursive right half 

        if(tree[2*k]=='B' && tree[2*k+1]=='B') // Both left and right sons B
        tree[k]='B';
        else if(tree[2*k]=='I'&&tree[2*k+1]=='I') // Both left and right sons I
        tree[k]='I';
        else tree[k]='F';
}

void postorder (int v){
       // After the sequence traversal 
        if(tree[2*v])
            postorder (2*v);
        if(tree[2*v+1])
            postorder (2*v+1);

        printf("%c",tree[v]);
}

int main(){
    
        int n;
        scanf("%d",&n);
        scanf("%s",s+1);
        
        build_FBI(1,1,strlen(s+1));
        
        // Post order traversal output 
        postorder(1);
}

---

2. java

---

3. python

---

Process understanding