#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int data;
struct node *next;
struct node *left;
}LNode;
LNode* newNode(int data){
LNode *n = (LNode*)malloc(sizeof(LNode));
n->data = data;
n->next = NULL;
n->left = NULL;
return n;
}
void buildList(LNode **headRef){
int i;
for(i=7;i>0;i--){
LNode *n = newNode(i);
n->next = *headRef;
*headRef = n;
}
}
void freeMem(LNode *head){
LNode *temp;
while(head != NULL){
temp = head;
head = head->next;
free(temp);
}
}
void display(LNode *head){
while(head->next != NULL){
printf("%d->",head->data);
head = head->next;
}
printf("%d\n",head->data);
}
LNode* buildBST(LNode* head){
if(head == NULL || head->next == NULL) return head;
LNode *root = NULL;
LNode *slow = head;
LNode *fast = head;
LNode *prev = NULL;
while(fast != NULL && fast->next != NULL){
prev = slow;
slow = slow->next;
fast = fast->next->next;
}
root = slow;
prev->next = NULL;
root->left = buildBST(head);
root->next = buildBST(slow->next);
return root;
}
void preorder(LNode* root){
if(root != NULL){
printf("%d ",root->data);
preorder(root->left);
preorder(root->next);
}
}
void inorder(LNode* root){
if(root != NULL){
inorder(root->left);
printf("%d ",root->data);
inorder(root->next);
}
}
void postorder(LNode* root){
if(root != NULL){
postorder(root->left);
postorder(root->next);
printf("%d ",root->data);
}
}
int main(){
LNode *head = NULL;
LNode *root = NULL;
buildList(&head);
display(head);
root = buildBST(head);
preorder(root);
printf("\n");
inorder(root);
printf("\n");
postorder(root);
// freeMem(head);
return 0;
}
No comments:
Post a Comment