L2-004. Is this a binary search tree?

Chen Yue
A binary search tree can be defined recursively as a binary tree with the following properties: for any node,

The key values of all nodes in the left subtree are less than those of the nodes.
The key value of all nodes in the right subtree is greater than or equal to the key value of the node.
Its left and right subtrees are binary search trees.
The so-called "mirror image" of the binary search tree is the tree obtained by the replacement of the left and right subtrees of all nodes.

Given a sequence of integer keys, please write a program to determine whether this is the result of a preorder traversal of a binary search tree or its image.

Input format:

The first line of input gives a positive integer N (<=1000). The next line gives N integer key values separated by spaces.

Output format:

If the input sequence is the result of a preorder traversal of a binary search tree or its image, the result of a postorder traversal of the tree is first output in one line and then in the next line. There is one space between the numbers, and no extra space is allowed at the beginning and end of a line. If the answer is no, output "NO".

Input Sample 1:
7
8 6 5 7 10 8 11
Output Sample 1:
YES
5 7 6 8 11 10 8
Input Sample 2:
7
8 10 11 8 6 7 5
Output Sample 2:
YES
11 8 10 7 5 6 8
Input Sample 3:
7
8 6 8 5 10 9 11
Output Sample 3:
NO
Train of thought: Firstly, according to the meaning of the question, it builds a tree according to the original method of searching binary tree, then it builds a tree according to the method of mirror binary tree. Finally, it traverses the two trees in order. If one of them is the same as the sequence given in the question, it outputs its follow-up traversal result or it outputs NO.

#include <stdio.h>
#include <malloc.h>
#include <iostream>
using namespace std;
typedef char InfoType[10];
typedef struct node                 /*Record type*/
{
    int key;                    /*Keyword Items*//*Other data domains*/
    struct node *lchild,*rchild;    /*Left and right child pointer*/
} BSTNode;
int b[1005],c[1005],t=0,s=0;
int b1[1005],c1[1005],t1=0,s1=0;
int InsertBST(BSTNode *&p,int k)
{
    if (p==NULL)                        /*The original tree is empty and the newly inserted record is the root node.*/
    {
        p=(BSTNode *)malloc(sizeof(BSTNode));
        p->key=k;
        p->lchild=p->rchild=NULL;
        return 1;
    }
    else if (k<p->key)
        return InsertBST(p->lchild,k);  /*Insert into the left subtree of * p*/
    else
        return InsertBST(p->rchild,k);  /*Insert into the right subtree of * p*/
}
BSTNode *CreateBST(int A[],int n)   /*Returns BST tree root node pointer*/
{
    BSTNode *bt=NULL;                   /*Initially, bt is an empty tree*/
    int i=0;
    while (i<n)
    {
        InsertBST(bt,A[i]);             /*Insert keyword A[i] into binary sorting tree T*/
        i++;
    }
    return bt;                          /*Returns the root pointer of the established binary sort tree*/
}
int InsertBST1(BSTNode *&p,int k)
{
    if (p==NULL)                        /*The original tree is empty and the newly inserted record is the root node.*/
    {
        p=(BSTNode *)malloc(sizeof(BSTNode));
        p->key=k;
        p->lchild=p->rchild=NULL;
        return 1;
    }
    else if (k<p->key)
        return InsertBST1(p->rchild,k); /*Insert into the left subtree of * p*/
    else
        return InsertBST1(p->lchild,k);  /*Insert into the right subtree of * p*/
}
BSTNode *CreateBST1(int A[],int n)  /*Returns BST tree root node pointer*/
{
    BSTNode *bt1=NULL;                  /*Initially, bt is an empty tree*/
    int i=0;
    while (i<n)
    {
        InsertBST1(bt1,A[i]);           /*Insert keyword A[i] into binary sorting tree T*/
        i++;
    }
    return bt1;                         /*Returns the root pointer of the established binary sort tree*/
}
void PreOrder(BSTNode * bt)//Preemptive traversal of binary trees
{
    if(bt!=NULL)
    {
        //printf("%d ",bt->key);
        b[t++]=bt->key;
        PreOrder(bt->lchild);
        PreOrder(bt->rchild);
    }

}
void PostOrder(BSTNode * bt)//Follow-up traversal of binary trees
{
    if(bt!=NULL)
    {
        PostOrder(bt->lchild);
        PostOrder(bt->rchild);
        c[s++]=bt->key;
    }

}
int main()
{
    BSTNode *bt,*bt1;
    int n,a[1005],ans=0,ans1=0;
    int flag=0;
    cin>>n;
    for(int i=0; i<n; i++)
        cin>>a[i];
    bt=CreateBST(a,n);
    PreOrder(bt);
    for(int i=0; i<n; i++)
        if(a[i]==b[i])
            ans++;
    if(ans==n)
    {
        flag=1;
        cout<<"YES"<<endl;
        PostOrder(bt);
        for(int i=0; i<n; i++)
        {
            if(i==0)
                cout<<c[i];
            else
                cout<<" "<<c[i];
        }
        cout<<endl;
    }
    if(flag==0)
    {
        t=0;
        bt1=CreateBST1(a,n);
        PreOrder(bt1);
        for(int i=0; i<n; i++)
            if(a[i]==b[i])
                ans1++;
        if(ans1==n)
        {flag=1;
            cout<<"YES"<<endl;s=0;
            PostOrder(bt1);
            for(int i=0; i<n; i++)
            {
                if(i==0)
                    cout<<c[i];
                else
                    cout<<" "<<c[i];
            }cout<<endl;
        }
    }

    if(flag==0)
        cout<<"NO"<<endl;
    return 0;
}

L2-006. Tree traversal

Given a binary tree's post-order traversal and intermediate-order traversal, please output the sequence of its sequence traversal. It is assumed that the key values are positive integers that are not equal to each other.

Input format:

The first line of input gives a positive integer N (<=30), which is the number of nodes in the binary tree. The second line gives the sequential traversal sequence. The third line gives the order traversal sequence. Numbers are separated by spaces.

Output format:

Output the sequence of sequential traversal of the tree in a row. Numbers are separated by one space, and no extra space is allowed at the beginning and end of the line.

Input sample:
7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
Output sample:
4 1 6 3 5 7 2
Problem-solving ideas; people who have studied data structure know that ordinal traversal and sequential or sequential traversal can only determine a binary tree, so we just need to build a book and then go through the hierarchical traversal on OK.

#include <iostream>
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
struct BTNode
{
    int key;
    BTNode *lchild,*rchild;
};
BTNode *CreateBTNode(int a[],int b[],int n)//a denotes post-order traversal, b denotes post-order traversal. Each time the last node of post-order is taken, the middle order is divided into two parts by using it as the demarcation point, and then the same operation is performed on each part.
{
    BTNode *bt;
    bt=(BTNode*)malloc(sizeof(BTNode));
    int t,temp1[35],temp2[35],i,k;
    if(n<=0)
        return NULL;
    t=a[n-1];
    bt->key=t;
    for(i=0;i<n;i++)
        if(b[i]==t)
            break;
    k=0;
    for(int j=i+1;j<n;j++)
        temp2[k++]=b[j];
    k=0;
    for(int j=i;j<n-1;j++)
        temp1[k++]=a[j];
    bt->lchild=CreateBTNode(a,b,i);
    bt->rchild=CreateBTNode(temp1,temp2,n-i-1);
    return bt;

}
int c[35],tt;
void LevelOrder(BTNode *bt)//Intermediate traversal of trees with queues
{
    queue<BTNode*> Q;
    BTNode *p;
    Q.push(bt);
    while(!Q.empty())
    {
        p=Q.front();
        c[tt++]=p->key;
        Q.pop();
        if(p->lchild)
            Q.push(p->lchild);
        if(p->rchild)
            Q.push(p->rchild);
    }
}
int main()
{
    int n,a[35],b[35];
    BTNode *bt;
    tt=0;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n;i++)
        cin>>b[i];
    bt=CreateBTNode(a,b,n);
    LevelOrder(bt);
    cout<<c[0];
    for(int i=1;i<n;i++)
            cout<<" "<<c[i];
    cout<<endl;
    return 0;
}

L2-011. Playing with Binary Trees

Given a binary tree's mid-order traversal and pre-order traversal, you first mirror the tree, and then output the sequence of the inverted sequence traversal. The so-called mirror inversion refers to the exchange of left and right children of all non-leaf nodes. It is assumed that the key values are positive integers that are not equal to each other.

Input format:

The first line of input gives a positive integer N (<=30), which is the number of nodes in the binary tree. The second line gives the order traversal sequence. The third line gives its preamble traversal sequence. Numbers are separated by spaces.

Output format:

Output the sequence traversed by the tree after inversion in a row. Numbers are separated by one space, and no extra space is allowed at the beginning and end of the line.

Input sample:
7
1 2 3 4 5 6 7
4 1 3 2 6 5 7
Output sample:
4 6 1 7 5 3 2

#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
#include <string>
#include <malloc.h>

using namespace std;

struct BTNode
{
    int key;
    BTNode *lchild,*rchild;
};
BTNode *CreatBTNode(int b[],int a[],int n)//a denotes ordinal order, b denotes ordinal order, tree-building method and similarity between ordinal and postordinal order
{
    int p,k,i,temp1[35],temp2[35],temp3[35];
    BTNode *bt;
    if(n<=0) return NULL;
    bt=(BTNode*)malloc(sizeof(BTNode));
    bt->key=b[0];
    for(i=0;i<n;i++)
        if(b[0]==a[i])
            break;
    k=0;
    for(int j=1;j<i+1;j++)
        temp1[k++]=b[j];
    bt->lchild=CreatBTNode(temp1,a,i);
    k=0;
    for(int j=i+1;j<n;j++)
        temp2[k++]=b[j];
    k=0;
    for(int j=i+1;j<n;j++)
        temp3[k++]=a[j];
    bt->rchild=CreatBTNode(temp2,temp3,n-i-1);
    return bt;
}
void Change(BTNode *&bt)//Recursively swapping left and right subtrees
{
    BTNode *p;
    if(bt)
    {
        p=bt->lchild;
        bt->lchild=bt->rchild;
        bt->rchild=p;
        Change(bt->lchild);
        Change(bt->rchild);
    }
}
int c[35],tt;
void LevelOrder(BTNode *bt)//Hierarchical traversal of swapped trees
{
    queue<BTNode*> Q;
    BTNode *p;
    Q.push(bt);
    while(!Q.empty())
    {
        p=Q.front();
        c[tt++]=p->key;
        Q.pop();
        if(p->lchild)
            Q.push(p->lchild);
        if(p->rchild)
            Q.push(p->rchild);
    }
}
int main()
{
    int n,a[35],b[35];
    BTNode *bt,*b1;
    tt=0;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n;i++)
        cin>>b[i];
    bt=CreatBTNode(b,a,n);
    Change(bt);
    LevelOrder(bt);
    cout<<c[0];
    for(int i=1;i<n;i++)
        cout<<" "<<c[i];
    cout<<endl;
    return 0;
}

L3-010. Complete Binary Search Tree

To insert a series of given numbers into an initial empty binary search tree (defined as a left subtree with large keys and a right subtree with small keys), you need to determine whether the final tree is a complete binary tree and give the results of its sequence traversal.

Input format:

The first line of input gives a positive integer N of no more than 20; the second line gives N distinct positive integers separated by spaces.

Output format:

The input N positive integers are sequentially inserted into a binary search tree that is initially empty. In the first line, the sequence traversal results of the output result tree are separated by one space between the numbers, and no extra space is allowed at the beginning and end of the line. The second line outputs "YES" if the tree is a complete binary tree; otherwise it outputs "NO".

Input Sample 1:
9
38 45 42 24 58 30 67 12 51
Output Sample 1:
38 45 24 58 42 30 12 67 51
YES
Input Sample 2:
8
38 24 12 45 58 67 42 51
Output Sample 2:
38 45 24 58 42 12 67 51
NO

#include <iostream>
#include <queue>
#include <cstdio>
#include <malloc.h>
using namespace std;
typedef struct node
{
    int key;
    struct node *lchild,*rchild;
} BSTNode;

int InsertBST(BSTNode *&p,int k)
{
    if(p==NULL)
    {
        p=(BSTNode*)malloc(sizeof(BSTNode));
        p->key=k;
        p->lchild=p->rchild=NULL;
        return 1;
    }
     else if(k==p->key)
        return 0;
    else if(k<p->key)
        return InsertBST(p->rchild,k);
    else
        return InsertBST(p->lchild,k);
}
BSTNode *CreateBSTNode(int a[],int n)
{
    BSTNode *bt=NULL;
    int i=0;
    while(i<n)
    {
        InsertBST(bt,a[i]);
        i++;
    }
    return bt;
}
int IsCompleteBiTree(BSTNode *bt)//Using the hierarchical traversal of the tree to judge whether it is a complete binary tree or not, because the complete binary tree must be empty for the right child when the left child is empty, so as long as the left child of p is empty and the right child is not empty when the p is not empty, if it returns directly to Fals in this way, otherwise it will bring all the left and right children into Fals. Team, if it encounters the first empty node, if all the nodes behind it are empty, it is a complete binary tree, otherwise it is not.
{
    queue<BSTNode*> Q;
    BSTNode *p;
    Q.push(bt);
    while(!Q.empty())
    {
        p=Q.front();
        Q.pop();
        if(p)
        {
            if(!p->lchild&&p->rchild)
                return 0;
            Q.push(p->lchild);
            Q.push(p->rchild);
        }
        else
        {
            Q.pop();
            break;
        }
    }
    while(!Q.empty())
    {
        p=Q.front();
        Q.pop();
        if(p)
            return 0;
    }
    return 1;
}
int t,b[25];
void LevelOrder(BSTNode *bt)//Hierarchical traversal of the tree
{
    BSTNode *p;
    queue<BSTNode*> Q;
    Q.push(bt);
    while(!Q.empty())
    {
        p=Q.front();
        //printf("%d ",p->key);
        b[t++]=p->key;
        Q.pop();
        if(p->lchild!=NULL)
            Q.push(p->lchild);
        if(p->rchild!=NULL)
            Q.push(p->rchild);
    }
}
int main()
{
    int n,a[25],flag;
    BSTNode *bt;
    t=0;
    cin>>n;
    for(int i=0; i<n; i++)
        cin>>a[i];
    bt=CreateBSTNode(a,n);
    LevelOrder(bt);
    cout<<b[0];
    for(int i=1; i<n; i++)
        cout<<" "<<b[i];
    cout<<endl;
    flag=IsCompleteBiTree(bt);
    if(flag==0)
        cout<<"NO"<<endl;
    else
        cout<<"YES"<<endl;
    return 0;
}

The last one is a question of the Ninth ACM Programming Competition in Henan Province. The idea is to give you T-group test data first. The first line of each test data is two numbers n. K means that there are n trees, and each tree has k nodes, so you can judge how many types of N trees there are.
Solution: First construct the tree, then store the n trees with an array of pointers, and then compare them one by one. At this time, we should pay attention to the need for marking when comparing. If not marking, the value of the same type of tree will increase if repeated comparisons are not made.

#include <iostream>
#include <bits/stdc++.h>

using namespace std;
struct Tree
{
    struct Tree *lchild,*rchild;
    int key;
};
int Insert(Tree *&p,int k)
{
    if(p==NULL)
    {
        p = (Tree*)malloc(sizeof(Tree));
        p->key=k;
        p->lchild=p->rchild=NULL;
        return 1;
    }
    else if(k<p->key)
        return Insert(p->lchild,k);
    else if(k>p->key)
        return Insert(p->rchild,k);
}
Tree *CreatT(int A[],int n)
{
    Tree *tr = NULL;
    int i=0;
    while(i<n)
    {
        Insert(tr,A[i]);
        i++;
    }
    return tr;
}
bool Like(Tree *b1,Tree *b2)//Recursive comparison of similarities between two trees
{
    bool like1,like2;
    if(b1==NULL&&b2==NULL)
        return true;
    else if(b1==NULL||b2==NULL)
        return false;
    else
    {
        like1=Like(b1->lchild,b2->lchild);
        like2=Like(b1->rchild,b2->rchild);
        return (like1&&like2);
    }
}
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
        int n,k;
        int a[25];
        Tree *tr[55];
        scanf("%d %d",&n,&k);
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<k;j++)
            {
                scanf("%d",&a[j]);
            }
            tr[i]=CreatT(a,k);
        }
        int sum=0,s=-1;//sum is used to denote how many similar trees there are, and s is used to denote how many trees of the same type there are, because the same type of tree is only one, so the initial value is -1.
        int vis[55];
        memset(vis,0,sizeof(vis));
        for(int i=0;i<n;i++)
        {
            if(vis[i])continue;
            s=0;
            vis[i]=1;
            for(int j=0;j<n;j++)
            {
                if(i!=j&&Like(tr[i],tr[j])&&!vis[j])
                {
                    vis[j]=1;
                    s++;
                }
            }sum=sum+s;
        }
        cout<<n-sum<<endl;
    }
    return 0;
}