Create binary tree and hierarchical traversal according to generalized table

[problem description] true topic of postgraduate entrance examination: given a binary tree, it is required to traverse the binary tree from bottom to top by layers. The access order of each layer is from left to right, and each layer outputs a separate line.

[input form] a binary tree represented by a generalized table. The node element type is integer and is greater than 0, for example: 1 (2 (3 (4, 5)), 6 (7, 8 (9, 10)))

[output form] print the node element values of each layer from bottom to top, and the elements are separated by spaces. The access order of each layer is from left to right, and each layer outputs a separate line.

[sample input] 1 (2 (3 (4,5)), 6 (7,8 (9,10))), there is no space in the string

[sample output]

4 5 9 10

3 7 8

2 6

1

Examination questions:

1. Create a binary tree according to the generalized table

2. Traverse the binary tree hierarchically

First, solve the first problem - create a binary tree according to the generalized table.

Examples 1 (2 (3 (4,5)), 6 (7,8 (9,10))) given in the title are transformed into binary trees, as shown in the figure below.

We can see that the binary tree in the form of generalized table is structurally_ (_( ),_ ()), the first underline represents the parent node, the second and third underline represent the child node, and the child node may not exist.

For example, 1, 2 and 6 in the figure are 1 (2 (3 (4,5)), 6 (7,8 (9,10))) in the original generalized table.

For another example, 3, 4 and 5 in the figure are 1 (2 (3 (4,5)), 6 (7,8 (9,10))) in the original generalized table.

Moreover, this structure is nested and recursive.

When the child node does not have parentheses, the recursion ends, that is, in the case of 3, 4 and 5.

After understanding this, it is very important to find the comma that separates the left and right subtrees.

Here, the stack structure is used for bracket matching. If a comma is matched, there is only one left bracket in the stack, which proves that this comma is the comma we are looking for.

Another noteworthy point is that our data are not all single digits, so we need to consider how to identify multiple digits.

BiNode* Bitree::create(char *s,int i,int j)//i. j points to the root node number and the last right parenthesis respectively
{
    if(i<=j)
    {
        BiNode *r=new BiNode;

        int t=i;
        while(1)
        {
            if(s[t]<'0'||s[t]>'9')
                break;
            t++;
        }

        int sum=0;
        for(int k=i;k<=t-1;k++)
        {
            sum=sum*10+s[k]-'0';//Can't write+=
        }

        r->data=sum;

        if(i==j||j==t-1)
        {
            return r;
        }
        else{
            int rr=i+1;
            int flag=0;//Judge whether there is a comma
            Stack st;//Bracket matching private stack
            while(rr<=j)//Find the comma position that separates the left and right subtrees
            {
                switch(s[rr])
                {
                    case '(':st.push(s[rr]);break;
                    case ')':st.pop();break;
                }
                if(s[rr]==','&&st.data[st.top]=='('&&st.top==0)
                {
                    flag=1;
                    break;
                }
                rr++;
            }

            if(flag)
            {
                r->lf=create(s,i+2,rr-1);
                r->rt=create(s,rr+1,j-1);
            }

            else
            {
                r->lf=create(s,i+2,rr-2);
                r->rt=NULL;
            }
        }
        return r;
    }
    else
        return NULL;
}

After it is created, the binary tree is traversed hierarchically. As the name suggests, it comes layer by layer

Because the title requires the tree level to be output upside down, I choose to first save the tree into a binary array and then traverse it.

Therefore, while traversing the hierarchy, it also requires the width and depth of the binary tree

int tree[N][N]={0};
int width[N]={0};//Record the width of the n th layer
int depth=0;//Recording depth
void Bitree::bfs()
{
    Queue q;int i=0,j=0;
    q.enterQueue(*root);
    int c=1;//The rightmost de last position on the upper floor
    while(q.len!=0)
    {
        BiNode temp=q.outQueue();
        tree[i][j++]=temp.data;

        if(temp.lf!=NULL)
            q.enterQueue(*temp.lf);
        if(temp.rt!=NULL)
            q.enterQueue(*temp.rt);

        if(q.fr==c)
        {
            c=q.re;
            width[i]=j;
            i++;
            j=0;
        }
    }
    depth=i;
}

void Bitree::output()
{
    for(int i=depth-1;i>=0;i--)
    {
        for(int j=0;j<width[i];j++)
        {
            cout<<tree[i][j]<<' ';
        }
        cout<<endl;
    }
}

Finally, the complete code is as follows:

#include <iostream>
#include <cstring>
#define N 50
using namespace std;
//Hierarchical traversal binary tree
//Creating a binary tree from a generalized table
class BiNode
{
public:
    BiNode *lf,*rt;
    int data;
    BiNode():lf(NULL),rt(NULL){}
};

class Bitree
{
public:
    BiNode *root;
    Bitree():root(NULL){}
    BiNode* create(char *s,int i,int j);
    void print(BiNode*);
    void bfs();
    void output();
};

class Stack
{
public:
    int top;
    char data[N];
    Stack():top(-1){}
    void push(char ch)
    {
        if(top<N-1)
        {
            data[++top]=ch;
        }
    }
    char pop()
    {
        if(top!=-1)
        {
            return data[top--];
        }
        return '#';
    }
};

class Queue
{
public:
    int fr,re;//Head and tail pointer
    int len;//length
    BiNode data[N];
    Queue():fr(0),re(0){}
    void enterQueue(const BiNode &num)
    {
        if(fr!=re||len==0)
        {
            data[re]=num;
            re=(re+1)%N;
            len++;
        }
    }
    BiNode outQueue()
    {
        if(len!=0)
        {
            BiNode temp=data[fr];
            fr=(fr+1)%N;
            len--;
            return temp;
        }
        return BiNode();
    }
};

BiNode* Bitree::create(char *s,int i,int j)//i. j points to the root node number and the last right parenthesis respectively
{
    if(i<=j)
    {
        BiNode *r=new BiNode;

        int t=i;
        while(1)
        {
            if(s[t]<'0'||s[t]>'9')
                break;
            t++;
        }

        int sum=0;
        for(int k=i;k<=t-1;k++)
        {
            sum=sum*10+s[k]-'0';//Can't write+=
        }

        r->data=sum;

        if(i==j||j==t-1)
        {
            return r;
        }
        else{
            int rr=i+1;
            int flag=0;//Judge whether there is a comma
            Stack st;//Bracket matching private stack
            while(rr<=j)//Find the comma position that separates the left and right subtrees
            {
                switch(s[rr])
                {
                    case '(':st.push(s[rr]);break;
                    case ')':st.pop();break;
                }
                if(s[rr]==','&&st.data[st.top]=='('&&st.top==0)
                {
                    flag=1;
                    break;
                }
                rr++;
            }

            if(flag)
            {
                r->lf=create(s,i+2,rr-1);
                r->rt=create(s,rr+1,j-1);
            }

            else
            {
                r->lf=create(s,i+2,rr-2);
                r->rt=NULL;
            }
        }
        return r;
    }
    else
        return NULL;
}



void Bitree::print(BiNode *p)
{
    if(p!=NULL)
    {
        cout<<p->data;
        print(p->lf);
        print(p->rt);
    }
}

int tree[N][N]={0};
int width[N]={0};//Record the width of the n th layer
int depth=0;//Recording depth
void Bitree::bfs()
{
    Queue q;int i=0,j=0;
    q.enterQueue(*root);
    int c=1;//The rightmost de last position on the upper floor
    while(q.len!=0)
    {
        BiNode temp=q.outQueue();
        tree[i][j++]=temp.data;

        if(temp.lf!=NULL)
            q.enterQueue(*temp.lf);
        if(temp.rt!=NULL)
            q.enterQueue(*temp.rt);

        if(q.fr==c)
        {
            c=q.re;
            width[i]=j;
            i++;
            j=0;
        }
    }
    depth=i;
}

void Bitree::output()
{
    for(int i=depth-1;i>=0;i--)
    {
        for(int j=0;j<width[i];j++)
        {
            cout<<tree[i][j]<<' ';
        }
        cout<<endl;
    }
}

int main()
{
    char s[N];
    cin.getline(s,N-1);
    //cout<<s<<endl;
    int len=strlen(s);

    Bitree bt;

    bt.root=bt.create(s,0,len-1);
    bt.bfs();
    bt.output();
    return 0;
}

Tags: Algorithm data structure Graph Theory

Posted by Iki on Mon, 02 May 2022 03:28:33 +0300