threaded binary tree

#include<stdio.h>

#include<stdlib.h>

#include<memory.h>

typedef struct treenode {

    int data;

    struct treenode* left;

    struct treenode* right;

    int is_thread;

} treenode;

treenode* makeNode(int data, treenode* leftnode,treenode* rightnode,int is_thread) {

    treenode* node=(treenode *)malloc(sizeof(treenode));

    node->data=data;

    node->left=leftnode;

    node->right=rightnode;

    node->is_thread=is_thread;

    return node;

}

treenode *findthreadsucc(treenode *p) {

    treenode *q = p->right;

    if(q==NULL) return q;

    if(p->is_thread) return q;

    while(q->left!=NULL)q=q ->left;

    return q;

}

void inorder(treenode *t) {

    treenode *q;

    q=t;

    while(q->left)q=q->left;

    while(q) {

        printf("%d ",q->data);

        q=findthreadsucc(q);

    }

}

treenode *findthreadsucc2(treenode *p) {

    treenode *q = p->right;

    if(q==NULL) return q;

    if(p->is_thread) return q;

    while(q->left!=NULL) {

       printf("%d ",q->data); 

       q=q ->left;

    }

    printf("%d ",q->data); 

    return q;

}

void preorder(treenode *t) {

    treenode *q=t;

    printf("%d ",q->data); 

    while(q->left) { 

        q=q->left;

        printf("%d ",q->data);

    }

    while(q) {

        q=findthreadsucc2(q);

    }

}

void postorder(treenode *t) {

    if(t&&t->left) postorder(t->left);

    if(t&&t->is_thread==0) postorder(t->right);

    if(t) printf("%d ", t->data);

}

int main() {

    treenode *n1,*n2,*n3,*n4,*n5,*n6,*n7,*n8,*n9,*n10,*n11,*n12;

    treenode *root;

 

    n12=makeNode(12,NULL,NULL,1);

    n11=makeNode(18,NULL,NULL,0);

    n10=makeNode(14,n12,NULL,1);

    n9=makeNode(5,NULL,NULL,1);

    n7=makeNode(16,n10,n11,0);

    n6=makeNode(9,NULL,NULL,1);

    n5=makeNode(6,n9,NULL,1);

    n4=makeNode(2,NULL,NULL,1);

    n3=makeNode(10,n6,n7,0);

    n2=makeNode(4,n4,n5,0);

    n1=makeNode(8,n2,n3,0);

 

    n4->right=n2;    // right를 이용하여 다음에 방문할 노드를 바로 찾아갈수 있도록 한다.

    n5->right=n1;    // is_thread 라는 변수를 이용하여 right 포인터가 thread 포인터인지 아닌지를 알수 있다.

    n6->right=n3;    // threaded 나무를 쓰는 이유는 노드를 순차적으로 방문하는 것이 아주 빠르기 때문이다.

    n12->right=n10;  //

    n9->right=n5;    //

    n10->right=n7;   //

    root=n1;

    printf("\ninorder: ");

    inorder(root);

    printf("\npreorder: ");

    preorder(root);

    printf("\npostorder: ");

    postorder(root);

    return 0;

}