B
Bubba
Greetings,
nodes of my ordered tree are implemented like this:
typedef struct __celltype {
labeltype label;
struct __celltype *first_child;
struct __celltype *next_sib;
struct __celltype *last_child;
int zadnji;
} celltype;
typedef celltype *node;
typedef celltype *TREE;
where first_child points to first sibling of the node, next_sib points to
next sibling and last_child points to last sibling in the node. Data
zadnji is true if the node is last child of any other node.
Labeltype is char.
Here's the whole implementation:
#include <stdlib.h>
#include <stdio.h>
#define LAMBDA NULL
#define labeltype char
typedef struct __celltype {
labeltype label;
struct __celltype *first_child;
struct __celltype *next_sib;
struct __celltype *last_child;
int zadnji; /*last*/
} celltype;
typedef celltype *node;
typedef celltype *TREE;
node MAKE_ROOT(labeltype l, TREE *T) {
if (!(*T = (celltype*) malloc(sizeof(celltype)))) {
printf("Nema dovoljno memorije.");
exit(1);
}
(*T)->label=l;
(*T)->first_child=NULL;
(*T)->next_sib=NULL;
(*T)->last_child=NULL;
(*T)->zadnji=0;
return *T;
}
node INSERT_CHILD(labeltype l, node i, TREE *T){
node temp;
if (!i) {
printf("Nema tog cvora.");
exit(1);
}
if (!(i->first_child= (celltype*) malloc(sizeof(celltype)))) {
printf("Nema dovoljno memorije.");
exit(1);
}
if (i->first_child==NULL) {
i->first_child->label=l;
i->first_child->first_child=NULL;
i->first_child->next_sib=NULL;
i->first_child->last_child=NULL;
i->first_child->zadnji=1;
}
if (i->first_child!=NULL) {
temp=i->first_child;
i->first_child->label=l;
i->first_child->first_child=NULL;
i->first_child->next_sib=temp;
i->first_child->last_child=NULL;
i->first_child->zadnji=0;
}
return i->first_child;
}
node ROOT(TREE T){
return T;
}
node INSERT_SIBLING(labeltype l, node i, TREE *T){
node temp;
if (!i) {
printf("Nema tog cvora.");
exit(1);
}
if (!(i->next_sib= (celltype*) malloc(sizeof(celltype)))) {
printf("Nema dovoljno memorije.");
exit(1);
}
if (i==ROOT(*T)) {
printf("Taj cvor je korijen.");
exit(1);
}
if(i->zadnji==1){
i->zadnji=0;
i->next_sib->label=l;
i->next_sib->first_child=NULL;
i->next_sib->next_sib=NULL;
i->next_sib->last_child=NULL;
i->next_sib->zadnji=1;
}
if(i->zadnji==0){
temp=i->next_sib;
i->next_sib->label=l;
i->next_sib->first_child=NULL;
i->next_sib->next_sib=temp;
i->next_sib->last_child=NULL;
i->next_sib->zadnji=0;
}
return i->next_sib;
}
node PARENT(node i,TREE T){
node c, d;
if (i==ROOT(T)) return LAMBDA;
if (!i) {
printf("Nema tog cvora.");
exit(1);
}
for (c=T->first_child; c!=NULL; c=c->next_sib)
if (c==i) return T;
for (c=T->first_child; c!=NULL; c=c->next_sib){
d=PARENT(i,c);
if (d!=NULL) return d;
}
return NULL;
}
void DELETE(node i, TREE *T) {
node c,d,e,f,temp;
if (i==ROOT(*T)) {
printf("Taj cvor je korijen."); /*is root*/
exit(1);
}
if (!i) {
printf("Nema tog cvora."); /*no node*/
exit(1);
}
if (i->first_child!=NULL) {
printf("Taj cvor ima djece."); /*has sib*/
exit(1);
}
c=PARENT(i,*T);
if (c->first_child==c->last_child) {
free(i);
c->first_child=NULL;
c->last_child=NULL;
}
if (i==c->first_child) {
temp=i->next_sib;
free(i);
c->first_child=temp;
}
if(i==c->last_child) {
d=c->first_child;
while(d!=c->last_child) {
if (d->next_sib==i) {
d->next_sib=NULL;
d->zadnji=1;
break;
}
d=d->next_sib;
}
free(i);
c->last_child=d;
}
if ((i!=c->first_child) && (i!=c->last_child)){
for (d=c->first_child; d!=NULL; d=d->next_sib){
if(d->next_sib==i) e=d;
if(i->next_sib==d) f=d;
}
free(i);
e->next_sib=f;
}
}
node FIRST_CHILD(node i, TREE T){
if (i->first_child==NULL) return NULL;
if (!i) {
printf("Nema tog cvora.");
exit(1);
}
return i->first_child;
}
node NEXT_SIBLING(node i, TREE T){
if (i->next_sib==NULL) return NULL;
if (!i) {
printf("Nema tog cvora.");
exit(1);
}
return i->next_sib;
}
labeltype LABEL(node i, TREE T) {
if (!i) {
printf("Nema tog cvora.");
exit(1);
}
return i->label;
}
void CHANGE_LABEL(labeltype l, node i, TREE *T){
if (!i) {
printf("Nema tog cvora.");
exit(1);
}
i->label=l;
}
void POSTORDER(node i, TREE T) {
node c;
for(c=FIRST_CHILD(i,T); c!=LAMBDA; c=NEXT_SIBLING(c,T))
POSTORDER(c,T);
printf("%c ", LABEL(i,T));
}
int main(void)
{
return 0;
}
Now I need a sane way to input a tree from keyboard. What would be the
easiest one?
Thanks in advance!
nodes of my ordered tree are implemented like this:
typedef struct __celltype {
labeltype label;
struct __celltype *first_child;
struct __celltype *next_sib;
struct __celltype *last_child;
int zadnji;
} celltype;
typedef celltype *node;
typedef celltype *TREE;
where first_child points to first sibling of the node, next_sib points to
next sibling and last_child points to last sibling in the node. Data
zadnji is true if the node is last child of any other node.
Labeltype is char.
Here's the whole implementation:
#include <stdlib.h>
#include <stdio.h>
#define LAMBDA NULL
#define labeltype char
typedef struct __celltype {
labeltype label;
struct __celltype *first_child;
struct __celltype *next_sib;
struct __celltype *last_child;
int zadnji; /*last*/
} celltype;
typedef celltype *node;
typedef celltype *TREE;
node MAKE_ROOT(labeltype l, TREE *T) {
if (!(*T = (celltype*) malloc(sizeof(celltype)))) {
printf("Nema dovoljno memorije.");
exit(1);
}
(*T)->label=l;
(*T)->first_child=NULL;
(*T)->next_sib=NULL;
(*T)->last_child=NULL;
(*T)->zadnji=0;
return *T;
}
node INSERT_CHILD(labeltype l, node i, TREE *T){
node temp;
if (!i) {
printf("Nema tog cvora.");
exit(1);
}
if (!(i->first_child= (celltype*) malloc(sizeof(celltype)))) {
printf("Nema dovoljno memorije.");
exit(1);
}
if (i->first_child==NULL) {
i->first_child->label=l;
i->first_child->first_child=NULL;
i->first_child->next_sib=NULL;
i->first_child->last_child=NULL;
i->first_child->zadnji=1;
}
if (i->first_child!=NULL) {
temp=i->first_child;
i->first_child->label=l;
i->first_child->first_child=NULL;
i->first_child->next_sib=temp;
i->first_child->last_child=NULL;
i->first_child->zadnji=0;
}
return i->first_child;
}
node ROOT(TREE T){
return T;
}
node INSERT_SIBLING(labeltype l, node i, TREE *T){
node temp;
if (!i) {
printf("Nema tog cvora.");
exit(1);
}
if (!(i->next_sib= (celltype*) malloc(sizeof(celltype)))) {
printf("Nema dovoljno memorije.");
exit(1);
}
if (i==ROOT(*T)) {
printf("Taj cvor je korijen.");
exit(1);
}
if(i->zadnji==1){
i->zadnji=0;
i->next_sib->label=l;
i->next_sib->first_child=NULL;
i->next_sib->next_sib=NULL;
i->next_sib->last_child=NULL;
i->next_sib->zadnji=1;
}
if(i->zadnji==0){
temp=i->next_sib;
i->next_sib->label=l;
i->next_sib->first_child=NULL;
i->next_sib->next_sib=temp;
i->next_sib->last_child=NULL;
i->next_sib->zadnji=0;
}
return i->next_sib;
}
node PARENT(node i,TREE T){
node c, d;
if (i==ROOT(T)) return LAMBDA;
if (!i) {
printf("Nema tog cvora.");
exit(1);
}
for (c=T->first_child; c!=NULL; c=c->next_sib)
if (c==i) return T;
for (c=T->first_child; c!=NULL; c=c->next_sib){
d=PARENT(i,c);
if (d!=NULL) return d;
}
return NULL;
}
void DELETE(node i, TREE *T) {
node c,d,e,f,temp;
if (i==ROOT(*T)) {
printf("Taj cvor je korijen."); /*is root*/
exit(1);
}
if (!i) {
printf("Nema tog cvora."); /*no node*/
exit(1);
}
if (i->first_child!=NULL) {
printf("Taj cvor ima djece."); /*has sib*/
exit(1);
}
c=PARENT(i,*T);
if (c->first_child==c->last_child) {
free(i);
c->first_child=NULL;
c->last_child=NULL;
}
if (i==c->first_child) {
temp=i->next_sib;
free(i);
c->first_child=temp;
}
if(i==c->last_child) {
d=c->first_child;
while(d!=c->last_child) {
if (d->next_sib==i) {
d->next_sib=NULL;
d->zadnji=1;
break;
}
d=d->next_sib;
}
free(i);
c->last_child=d;
}
if ((i!=c->first_child) && (i!=c->last_child)){
for (d=c->first_child; d!=NULL; d=d->next_sib){
if(d->next_sib==i) e=d;
if(i->next_sib==d) f=d;
}
free(i);
e->next_sib=f;
}
}
node FIRST_CHILD(node i, TREE T){
if (i->first_child==NULL) return NULL;
if (!i) {
printf("Nema tog cvora.");
exit(1);
}
return i->first_child;
}
node NEXT_SIBLING(node i, TREE T){
if (i->next_sib==NULL) return NULL;
if (!i) {
printf("Nema tog cvora.");
exit(1);
}
return i->next_sib;
}
labeltype LABEL(node i, TREE T) {
if (!i) {
printf("Nema tog cvora.");
exit(1);
}
return i->label;
}
void CHANGE_LABEL(labeltype l, node i, TREE *T){
if (!i) {
printf("Nema tog cvora.");
exit(1);
}
i->label=l;
}
void POSTORDER(node i, TREE T) {
node c;
for(c=FIRST_CHILD(i,T); c!=LAMBDA; c=NEXT_SIBLING(c,T))
POSTORDER(c,T);
printf("%c ", LABEL(i,T));
}
int main(void)
{
return 0;
}
Now I need a sane way to input a tree from keyboard. What would be the
easiest one?
Thanks in advance!