#include<stdio.h>
#include<stdlib.h>
#define MAXCHILD 4
#define MAXNODE 20
struct treenode
{
char info;
// pointer to first child
struct treenode * firstchild;
// pointer to next sibling or father node
struct treenode * next;
// flag=0 if next is sibling , 1 if next is father node
int flag;
} ;
typedef struct treenode * NODEPTR;
int nodename= 65 ; // used for naming tree node
int nodecount= 0 ; // To count total number of node in Tree
// To store address of ptr to every node
// Every Node and its related info can be directly accessed from it
NODEPTR * stack[ MAXNODE] ;
NODEPTR root; //Pointer to the root of the Tree
/* All function written are listed Here */
NODEPTR getnode( ) ;
void freenode( NODEPTR p) ;
NODEPTR maketree( char x) ;
void setchild( NODEPTR tptr, char child[ ] , int n) ;
void breadthTraversalTreeGenerate( ) ;
int main( )
{
srand ( time ( NULL
) ) ; // used to get random Trees // Random Tree Generation
breadthTraversalTreeGenerate( ) ;
return 0 ;
}
NODEPTR getnode( )
{
NODEPTR p;
p
= ( struct treenode
* ) malloc ( sizeof ( struct treenode
) ) ; return p;
}
void freenode( NODEPTR p)
{
}
NODEPTR maketree( char x)
{
NODEPTR p;
p= getnode( ) ;
p-> info= x;
p-> flag= 0 ;
p-> firstchild= NULL;
p-> next= NULL;
return ( p) ;
}
void setchild( NODEPTR tptr, char child[ ] , int n)
{
NODEPTR p, q;
int i, j= 0 ;
if ( ( tptr-> firstchild) != NULL)
else
{
if ( n== 1 )
printf ( "\n %c has one child, namely \t " , tptr
-> info
) ; else
printf ( "\n %c has %d children, namely \t " , tptr
-> info
, n
) ;
p= maketree( child[ j] ) ;
j++;
tptr-> firstchild= p;
printf ( "%c" , tptr
-> firstchild
-> info
) ; stack[ nodecount] =& ( tptr-> firstchild) ;
nodecount++;
for ( i= 0 ; i< n- 1 ; i++ )
{
q= maketree( child[ j] ) ;
j++;
p-> next= q;
stack[ nodecount] =& ( p-> next) ;
nodecount++;
p= q;
}
p-> flag= 1 ;
p-> next= tptr;
}
}
void breadthTraversalTreeGenerate( )
{
int i, j, n, dummy;
char * child, lol;
NODEPTR tptr;
// tree-> info can be given anything I used char notation,it will
// be easy to understand order traversing using alphabats.
root= maketree( nodename) ;
// to store address of ptr to everynode
// will be used in generating children
stack[ nodecount] =& root;
nodecount++;
// nodename++ will make next nodename as next character
//i.e A, then B, then C & so on..
nodename++;
// Set children for next levels
dummy= nodecount- 1 ;
while ( dummy>= 0 )
{
dummy= nodecount- 1 ;
tptr=* ( stack[ dummy] ) ;
while ( tptr-> firstchild== NULL)
{
if ( nodecount+ n> MAXNODE)
break ;
child
= ( char * ) malloc ( sizeof ( char ) * n
) ; for ( i= 0 ; i< n; i++ )
{
child[ i] = nodename;
nodename++;
}
setchild( tptr, child, n) ;
dummy--;
if ( dummy< 0 )
{
dummy++;
break ;
}
tptr=* stack[ dummy] ;
}
if ( nodecount+ n> MAXNODE)
break ;
}
}
CiNpbmNsdWRlPHN0ZGlvLmg+CiNpbmNsdWRlPHN0ZGxpYi5oPgojZGVmaW5lIE1BWENISUxEIDQKI2RlZmluZSBNQVhOT0RFIDIwCgoKc3RydWN0IHRyZWVub2RlCnsKICAgIGNoYXIgaW5mbzsKCS8vIHBvaW50ZXIgdG8gZmlyc3QgY2hpbGQKCXN0cnVjdCB0cmVlbm9kZSAqZmlyc3RjaGlsZDsKCS8vIHBvaW50ZXIgdG8gbmV4dCBzaWJsaW5nIG9yIGZhdGhlciBub2RlCglzdHJ1Y3QgdHJlZW5vZGUgKm5leHQ7CgkvLyBmbGFnPTAgaWYgbmV4dCBpcyBzaWJsaW5nICwgMSBpZiBuZXh0IGlzIGZhdGhlciBub2RlCglpbnQgZmxhZzsKfTsKCnR5cGVkZWYgc3RydWN0IHRyZWVub2RlICpOT0RFUFRSOwppbnQgbm9kZW5hbWU9NjU7Ly8gdXNlZCBmb3IgbmFtaW5nIHRyZWUgbm9kZQppbnQgbm9kZWNvdW50PTA7IC8vIFRvIGNvdW50IHRvdGFsIG51bWJlciBvZiBub2RlIGluIFRyZWUKLy8gVG8gc3RvcmUgYWRkcmVzcyBvZiBwdHIgdG8gZXZlcnkgbm9kZQovLyBFdmVyeSBOb2RlIGFuZCBpdHMgcmVsYXRlZCBpbmZvIGNhbiBiZSBkaXJlY3RseSBhY2Nlc3NlZCBmcm9tIGl0Ck5PREVQVFIgKnN0YWNrW01BWE5PREVdOyAKTk9ERVBUUiByb290Oy8vUG9pbnRlciB0byB0aGUgcm9vdCBvZiB0aGUgVHJlZQoJCi8qICBBbGwgZnVuY3Rpb24gd3JpdHRlbiBhcmUgbGlzdGVkIEhlcmUgKi8KTk9ERVBUUiBnZXRub2RlKCk7CnZvaWQgZnJlZW5vZGUoTk9ERVBUUiBwKTsKTk9ERVBUUiBtYWtldHJlZShjaGFyIHgpOwp2b2lkIHNldGNoaWxkKE5PREVQVFIgdHB0cixjaGFyIGNoaWxkW10saW50IG4pOwp2b2lkIGJyZWFkdGhUcmF2ZXJzYWxUcmVlR2VuZXJhdGUoKTsKCmludCBtYWluKCkKewoKCXNyYW5kKHRpbWUoTlVMTCkpOy8vIHVzZWQgdG8gZ2V0IHJhbmRvbSBUcmVlcwoJLy8gUmFuZG9tIFRyZWUgR2VuZXJhdGlvbgoJYnJlYWR0aFRyYXZlcnNhbFRyZWVHZW5lcmF0ZSgpOwoJcHJpbnRmKCJcbiIpOwoJcmV0dXJuIDA7Cn0KCk5PREVQVFIgZ2V0bm9kZSgpCnsKCU5PREVQVFIgcDsKCXA9KHN0cnVjdCB0cmVlbm9kZSopbWFsbG9jKHNpemVvZihzdHJ1Y3QgdHJlZW5vZGUpKTsKCXJldHVybiBwOwp9Cgp2b2lkIGZyZWVub2RlKE5PREVQVFIgcCkKewoJZnJlZShwKTsKfQoKTk9ERVBUUiBtYWtldHJlZShjaGFyIHgpCnsKCU5PREVQVFIgcDsKCXA9Z2V0bm9kZSgpOwoJcC0+aW5mbz14OwoJcC0+ZmxhZz0wOwoJcC0+Zmlyc3RjaGlsZD1OVUxMOwoJcC0+bmV4dD1OVUxMOwoJCgkKCXJldHVybihwKTsKfQoKdm9pZCBzZXRjaGlsZChOT0RFUFRSIHRwdHIsY2hhciBjaGlsZFtdLGludCBuKQp7CglOT0RFUFRSIHAscTsKCWludCBpLGo9MDsKCWlmKCh0cHRyLT5maXJzdGNoaWxkKSE9TlVMTCkKCQlwcmludGYoIlZPSUQgSU5TRVJUSU9OIik7CgllbHNlIAoJewoJCWlmIChuPT0xKQoJCQlwcmludGYoIlxuJWMgaGFzIG9uZSBjaGlsZCwgbmFtZWx5IFx0Iix0cHRyLT5pbmZvKTsKCQllbHNlCgkJCXByaW50ZigiXG4lYyBoYXMgJWQgY2hpbGRyZW4sIG5hbWVseSBcdCIsdHB0ci0+aW5mbyxuKTsgCgkJCgkJcD1tYWtldHJlZShjaGlsZFtqXSk7CgkJaisrOwoJCXRwdHItPmZpcnN0Y2hpbGQ9cDsKCQlwcmludGYoIiVjIix0cHRyLT5maXJzdGNoaWxkLT5pbmZvKTsKCQlzdGFja1tub2RlY291bnRdPSYodHB0ci0+Zmlyc3RjaGlsZCk7CiAgICAJbm9kZWNvdW50Kys7CgkJZm9yKGk9MDtpPG4tMTtpKyspCgkJewoJCQlxPW1ha2V0cmVlKGNoaWxkW2pdKTsKCQkJaisrOwoJCQlwLT5uZXh0PXE7CgkJCXByaW50ZigiXHQlYyIscS0+aW5mbyk7CgkJCXN0YWNrW25vZGVjb3VudF09JihwLT5uZXh0KTsKICAgIAkJbm9kZWNvdW50Kys7CgkJCXA9cTsKCQl9CgkJcC0+ZmxhZz0xOwoJCXAtPm5leHQ9dHB0cjsKCQlwcmludGYoIlxuIik7Cgl9Cn0KCQp2b2lkIGJyZWFkdGhUcmF2ZXJzYWxUcmVlR2VuZXJhdGUoKQp7CglpbnQgaSxqLG4sZHVtbXk7CgljaGFyICpjaGlsZCxsb2w7CglOT0RFUFRSIHRwdHI7CgkKCS8vIHRyZWUtPiBpbmZvIGNhbiBiZSBnaXZlbiBhbnl0aGluZyBJIHVzZWQgY2hhciBub3RhdGlvbixpdCB3aWxsCgkvLyBiZSBlYXN5IHRvIHVuZGVyc3RhbmQgb3JkZXIgdHJhdmVyc2luZyB1c2luZyBhbHBoYWJhdHMuCglyb290PW1ha2V0cmVlKG5vZGVuYW1lKTsKCS8vIHRvIHN0b3JlIGFkZHJlc3Mgb2YgcHRyIHRvIGV2ZXJ5bm9kZQoJLy8gd2lsbCBiZSB1c2VkIGluIGdlbmVyYXRpbmcgY2hpbGRyZW4KCXN0YWNrW25vZGVjb3VudF09JnJvb3Q7CiAgICBub2RlY291bnQrKzsKCS8vIG5vZGVuYW1lKysgd2lsbCBtYWtlIG5leHQgbm9kZW5hbWUgYXMgbmV4dCBjaGFyYWN0ZXIKCS8vaS5lIEEsIHRoZW4gQiwgdGhlbiBDICYgc28gb24uLgoJbm9kZW5hbWUrKzsKCgkKCS8vIFNldCBjaGlsZHJlbiBmb3IgbmV4dCBsZXZlbHMKCWR1bW15PW5vZGVjb3VudC0xOwoJd2hpbGUoZHVtbXk+PTApCgl7CQoJCWR1bW15PW5vZGVjb3VudC0xOwoJCXRwdHI9KihzdGFja1tkdW1teV0pOwoJCXdoaWxlKHRwdHItPmZpcnN0Y2hpbGQ9PU5VTEwpCgkJewoJCQkKCQkJbj0ocmFuZCgpJShNQVhDSElMRCkpKzE7CgkJCWlmKG5vZGVjb3VudCtuPk1BWE5PREUpCgkJCQlicmVhazsKCQkJY2hpbGQ9KGNoYXIgKiltYWxsb2Moc2l6ZW9mKGNoYXIpKm4pOwoJCQlmb3IoaT0wO2k8bjtpKyspCgkJCXsKCQkJCWNoaWxkW2ldPW5vZGVuYW1lOwoJCQkJbm9kZW5hbWUrKzsKCQkJfQoJCQlzZXRjaGlsZCh0cHRyLGNoaWxkLG4pOwoJCQlkdW1teS0tOwoJCQlpZiAoZHVtbXk8MCkKCQkJewoJCQkJZHVtbXkrKzsKCQkJCWJyZWFrOwoJCQl9CgkJCXRwdHI9KnN0YWNrW2R1bW15XTsKCQkKCQl9CgkJaWYobm9kZWNvdW50K24+TUFYTk9ERSkKCQkJYnJlYWs7Cgl9CgkKfQoK
stdout
A has 2 children, namely B C
C has 4 children, namely D E F G
B has 2 children, namely H I
I has 2 children, namely J K
H has 2 children, namely L M
G has one child, namely N
F has 3 children, namely O P Q
E has one child, namely R