Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
1.8 kB
0
Indexable
Never
#include <stdio.h>
#include <stdlib.h>

typedef struct BTNode_{
    int data;
    struct BTNode_* left,*right;
}BTNode;

typedef struct Node_{
    BTNode *root;
    struct Node_* next;
}Node;

int N;

void Preorder(BTNode* root){
    if(root!=NULL){
        printf(" %d",root->data);
        Preorder(root->left);
        Preorder(root->right);
    }
}

Node* RecEnumTrees(int l,int r){
    Node *head=NULL,*tail=NULL;

    if(l>r){
        head=(Node*)malloc(sizeof(Node));
        head->next=NULL;
        head->root=NULL;
        return head;
    }

    for(int i=l;i<=r;i++){
        Node* ltrees=RecEnumTrees(l,i-1);
        Node* rtrees=RecEnumTrees(i+1,r);

        while(ltrees!=NULL){
            Node* rtrees_iter=rtrees;
            while(rtrees_iter!=NULL){
                BTNode* nrt=(BTNode*)malloc(sizeof(BTNode));
                nrt->data=i;
                nrt->left=ltrees->root;
                nrt->right=rtrees_iter->root;
                
                Node* ln=(Node*)malloc(sizeof(Node));
                ln->root=nrt;
                ln->next=NULL;
                if(head==NULL)
                    head=tail=ln;
                else{
                    tail->next=ln;
                    tail=ln;
                }
                rtrees_iter=rtrees_iter->next;
            }
            ltrees=ltrees->next;
        }
    }
    return head;
}

int main(void){
    scanf("%d",&N);
    Node* TreeListHead=RecEnumTrees(1,N);
    while(TreeListHead!=NULL){
        BTNode *root=TreeListHead->root;
        printf("%d",root->data);
        Preorder(root->left);
        Preorder(root->right);
        printf("\n");
        TreeListHead=TreeListHead->next;
    }
}