Tree implementation, ideas for keyboard input method needed

From	Bubba <nickname@banelli.biz.invalid>
Newsgroups	comp.lang.c
Subject	Tree implementation, ideas for keyboard input method needed
Date	2012-01-16 22:01 +0000
Message-ID	<Xns9FDCEA347419Bbubbachipsetone@130.133.4.11> (permalink)

Show all headers | View raw

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!

-- 
"If you lie to the compiler,
it will get its revenge."
Henry Spencer
2.718281828459045235360287471352662497757247093699959574966967627.com

Back to comp.lang.c | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

Tree implementation, ideas for keyboard input method needed Bubba <nickname@banelli.biz.invalid> - 2012-01-16 22:01 +0000
  Re: Tree implementation, ideas for keyboard input method needed Keith Thompson <kst-u@mib.org> - 2012-01-16 14:27 -0800
    Re: Tree implementation, ideas for keyboard input method needed Bubba <nickname@banelli.biz.invalid> - 2012-01-16 22:36 +0000
      Re: Tree implementation, ideas for keyboard input method needed Kaz Kylheku <kaz@kylheku.com> - 2012-01-16 22:53 +0000
      Re: Tree implementation, ideas for keyboard input method needed James Kuyper <jameskuyper@verizon.net> - 2012-01-16 18:06 -0500
      Re: Tree implementation, ideas for keyboard input method needed Keith Thompson <kst-u@mib.org> - 2012-01-16 16:41 -0800
    Re: Tree implementation, ideas for keyboard input method needed Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-01-16 23:01 +0000
      Re: Tree implementation, ideas for keyboard input method needed Shao Miller <sha0.miller@gmail.com> - 2012-01-16 19:49 -0500
        Re: Tree implementation, ideas for keyboard input method needed Keith Thompson <kst-u@mib.org> - 2012-01-16 17:46 -0800
  Re: Tree implementation, ideas for keyboard input method needed Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-01-16 22:29 +0000
    Re: Tree implementation, ideas for keyboard input method needed Bubba <nickname@banelli.biz.invalid> - 2012-01-16 22:38 +0000
    Re: Tree implementation, ideas for keyboard input method needed William Ahern <william@wilbur.25thandClement.com> - 2012-01-16 15:30 -0800
      Re: Tree implementation, ideas for keyboard input method needed Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-01-17 00:03 +0000
      Re: Tree implementation, ideas for keyboard input method needed Keith Thompson <kst-u@mib.org> - 2012-01-16 16:35 -0800
        Re: Tree implementation, ideas for keyboard input method needed cri@tiac.net (Richard Harter) - 2012-01-17 02:00 +0000
          Re: Tree implementation, ideas for keyboard input method needed Keith Thompson <kst-u@mib.org> - 2012-01-16 19:16 -0800
            Re: Tree implementation, ideas for keyboard input method needed cri@tiac.net (Richard Harter) - 2012-01-17 05:15 +0000
              Re: Tree implementation, ideas for keyboard input method needed Keith Thompson <kst-u@mib.org> - 2012-01-17 00:00 -0800
          Re: Tree implementation, ideas for keyboard input method needed Kaz Kylheku <kaz@kylheku.com> - 2012-01-17 04:04 +0000
  Re: Tree implementation, ideas for keyboard input method needed Kaz Kylheku <kaz@kylheku.com> - 2012-01-16 22:44 +0000
  Re: Tree implementation, ideas for keyboard input method needed Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-01-16 17:58 -0500
  Re: Tree implementation, ideas for keyboard input method needed ImpalerCore <jadill33@gmail.com> - 2012-01-16 19:36 -0800
    Re: Tree implementation, ideas for keyboard input method needed Eric Sosman <esosman@ieee-dot-org.invalid> - 2012-01-16 23:33 -0500
      Re: Tree implementation, ideas for keyboard input method needed ImpalerCore <jadill33@gmail.com> - 2012-01-17 07:18 -0800
    Re: Tree implementation, ideas for keyboard input method needed "BartC" <bc@freeuk.com> - 2012-01-17 13:54 +0000
      Re: Tree implementation, ideas for keyboard input method needed ImpalerCore <jadill33@gmail.com> - 2012-01-17 07:39 -0800
    Re: Tree implementation, ideas for keyboard input method needed Kaz Kylheku <kaz@kylheku.com> - 2012-01-17 19:01 +0000
  Re: Tree implementation, ideas for keyboard input method needed jgk@panix.com (Joe keane) - 2012-01-18 21:21 +0000

csiph-web