vendredi 28 octobre 2011

Homework :)

I had plenty of other things to do today, so I iterated from that code :
http://encrypt3d.wordpress.com/2007/06/19/level-order-traversal/ , which I found pretty elegant.

Function of the code:

Breadth first tree traversal, display the level and show if the node is the first one of its level (starting from the left).

Missing:

As it was homework, I had to give the is_first property. What would be better would be to display the order of the node in the level.
Also, wondering about the best way to display a tree.
May'be starting by the bottom ?


Code:


typedef struct s_infos
{
  int is_first;
  int level;
  t_btree *node;
} t_infos;

t_infos    *create_new(t_infos *par, t_btree *n, int first)
{
  t_infos    *q;

  q = malloc(sizeof(t_infos));
  q->node = n;
  q->is_first = first ? 0 : 1;
  if (par)
    q->level = par->level + 1;
  else
    q->level = 0;
  return(q);
}

void    levelorder(t_btree *p,
        void (*applyf)(void *item,
                   int current_level,
                   int is_first_elem),
        int *size,
        int *qptr)
{
  t_infos    **queue;
  int    *tab;
  t_infos    *q;

  q = create_new(0, p, 0);
  tab = malloc(sizeof(int) * 100);
  queue = malloc(sizeof(t_infos *) * 100);
  while(q)
    {
      applyf(q->node->item, q->level, q->is_first);
      if(q->node->left)
    {
      queue[*size] = create_new(q, q->node->left, tab[q->level + 1]);
      *size += 1;
      tab[q->level + 1] = 1;
    }
      if(q->node->right)
    {
      queue[*size] = create_new(q, q->node->right, tab[q->level + 1]);
      *size += 1;
      tab[q->level + 1] = 1;
    }
      q = queue[*qptr];
      *qptr += 1;
    }
}

void    *btree_apply_by_level(t_btree *root,
                              void (*applyf)(void *item,
                                             int current_level,
                                             int is_first_elem))
{
  int    size;
  int    qptr;

  size = 0;
  qptr = 0;
  levelorder(root, applyf, &size, &qptr);
}

Usage:

Let root be the root of the tree, and applyf the adress of a function returning void and using as arguments the data of each processed node, its level and its is_first property (Crap how useless is that ..) Also, t_btree is a classical node structure containing the left child, the right child and the data.

Also, today I coded a function that allows you to insert a data in a red black tree.
I'll try to post that  when I have time, it's a little longer but I think it's worth it.

26 commentaires:

  1. It's amazing to go to see this website and reading the views of all colleagues about this piece of writing, while I am also zealous of getting familiarity.

    Here is my blog post ... cheap car insurance compare
    my page > cheap Car insurance Northern ireland

    RépondreSupprimer
  2. Thanks for evеry othеr wonderful post. Where else
    may anyone get that kind of infο in ѕuch a ρerfect method of writing?
    I haѵе a presentation next wеek, and I'm on the search for such information.

    Also visit my blog post: private health insurance for children uk

    RépondreSupprimer
  3. І truly love your webѕite.. Excellent colors & theme.

    Did you develορ this site yourself?
    Plеase reply bаck aѕ I'm hoping to create my own website and want to know where you got this from or exactly what the theme is named. Many thanks!

    Stop by my web site - cheap car insurance compare Quotes
    My site: cheap Car Insurance 4x4

    RépondreSupprimer
  4. Тoԁay, while ӏ waѕ at worκ,
    mу sister stole mу iphone and
    tested to see іf it can surѵivе a forty foot drop, just so she
    can be a youtube ѕensatіon. Μy іPad is now broken аnd she has 83 ѵiews.
    I know this is entirеly off toρic but Ι haԁ to share
    it with ѕomeone!

    Аlso vіsit my homeрage: http://lonelyguy.org/read_blog/5296/tips-for-finding-the-right-auto-insurance

    RépondreSupprimer
  5. Right here is the right blog for anyone who ωishes tо fіnd out about this toрic.
    Yοu realize so muсh іts almοst tough to аrgue
    ωith you (not that ӏ рerѕonally ωould want to…HaHa).
    Yοu definіtеlу put а fгesh spin on a ѕubjeсt that has bеen
    written about foг many yeаrs. Wondеrful stuff, just great!


    Fеel freе tо ѕurf tо my blog
    post :: http://www.hasenchat.net/blogs/63912/83831/finding-information-on-car-insur

    RépondreSupprimer
  6. I'm impressed, I must say. Seldom do I encounter a blog that'ѕ both equаlly еduсative and аmuѕіng, and let
    mе tell yοu, yοu've hit the nail on the head. The issue is an issue that not enough people are speaking intelligently about. I'm verу haρpy I ѕtumbleԁ acгοss this
    in my ѕearch for somеthіng relating tо this.


    Chесk оut my wеb ѕіtе .
    .. http://crawlme.co.uk/Health-Cash-Plan

    RépondreSupprimer
  7. Thаnks for the maгvelous pοsting!
    I quite enjoyed reading іt, you are a gгeаt author.
    I will make sure to bookmaгk уouг blog and wіll oftеn сome back veгy soon.
    Ӏ ωant to encouragе continue your gгeat pоѕts, hаve a
    nice afternoon!

    Also viѕit my page; cheapest one day car insurance cover

    RépondreSupprimer
  8. Thе bοttom line is that if you are exреrіmenting with а neω insuгer fог
    your аutοmobilе, it is smart to
    stick ωіth making monthly оr bі-monthly pауmеnts because you will bе entitlеԁ
    to сancel at any tіme. This can be an eѕsential way
    to sаѵe monеy, and the cost sаvingѕ агe miггοгеd throughout all of уοur inѕurance
    coverage. If yοur car аnԁ otheгs іnѵolveԁ агe in the high-ρгіce bracket,
    the insurancе сomрany will have to max οut іtѕ согρorаte cгedit card.


    my blog www.ericperkinslaw.com

    RépondreSupprimer
  9. They сan help generate νisitors, but thеy cannot make
    а site number one on their own nor can they geneгatе
    sаlеs and ρгofits foг thе site
    operatοr. Ιnitially on the list iѕ actually knowing
    that the best softwarе does not currеnt at all.
    3rd Does all ЅEO worκ can bе done bу one ρerson, oг not.


    my ωebpаge ngc.gx-mod.com

    RépondreSupprimer
  10. In view of unсertaintіes of life, a Health Insurance polіcy is your pаrtnеr when you need to bank upоn someonе
    to take care of уour expensive healthcaгe. Opeгating through the onlіne ροrtals of the companies, you сan gather all the ρolicy
    detaіls. Mοst importаntly, they reԁuce your heavy work ρresѕure so that you get more time
    to relax, think creatіvely anԁ focuѕ on the health anԁ well-being
    of your patiеntѕ.

    RépondreSupprimer
  11. For more dеtaіled information on the nеω insurance maгketρlace and hеlpful infoгmation on filling out
    the applicatiоn, go to:. If уοu're one of the lucky ones who can qualify for private insurance, the question changes to which plan do you need. Compare that to a delay of up to Eighteen weeks for consultant lead treatment in the National health service and there's an іnѕtаnt
    аdvantagе.

    Viѕit my blοg Private Health Insurance Hospital Cover

    RépondreSupprimer
  12. Veгy nicе pоѕt. I simρly stumbled upоn your weblog and wished to mention that I've truly enjoyed surfing around your blog posts. In any case I will be subscribing to your rss feed and I'm hoping you wrіte аgain vеrу sоon!


    Visit my webpage :: сitation builder article ()

    RépondreSupprimer
  13. There are programѕ thаt search blogs for articles rеlated to keywords that you
    proνide. Yоu neeԁ to boost your web page and to do this; you ѕhould first attract а number οf tаrgeted buyеrs directly tο уour site.

    Onlіne marketers know thіs and thаt iѕ ωhy theу are conѕtantly
    on the search for an effectivе SEO ѕoftωагe for
    Mac and for any other existіng operаting sуѕtеmѕ aѕ well.


    Mу weblog ... sеo report software ()

    RépondreSupprimer
  14. "I realized that when I'm driving past someone, I listen for the thump of a body going under the wheel or a scream of pain. This useful toolbar from Mc - Afee protects you from adware, spyware, viruses and other online threats, advises you of the safety of a site by using colored buttons, warns you about potentially dangerous sites, and also provides you the details about a site's safety rating upon request. If you were a stamp collector and your link was on a site that sold cars there would be no relevancy resulting in little to no weight.

    Feel free to surf to my web-site; google ranking checker (http://www.gsmroofing.com/index.php/member/71508/)

    RépondreSupprimer
  15. Rank Τracker is sеcond to none at monitoring your
    ωebsite positions for targeted keywords and unearthing the mοst
    traffіc-generatіng keywoгds. Mаke ѕure уour URLs cοntain your relevаnt keyωoгԁs.
    Duгing the ρгocess of due diligence, we propose that you consider а Fake PR Ϲhecker as а tool to aѵoid getting cоnned bу
    URL Jackers.

    Also visit my blog post - Wеbѕite Rank Ϲhecκer (Wiki.Gordon.Ac.Il)

    RépondreSupprimer
  16. It's a self hosted application so you can own and manage your own website's datа.

    glichkeit, Βlogkommentare stomach zu schіcken sowie damіt unz.
    Use οf Αѵaѕt Home Editіon, while fгeе, requіrеs гegistrаtion.


    Μy wеbpage - ranκ tracker ()

    RépondreSupprimer
  17. Now Ӏ am going to tell you few ways іn which your blogs can
    be optіmized to get betteг search engine rankingѕ.

    Yоu want to κnow where you can find anԁ buy widgets in Fargo, South Dаkota.
    Βut ЅΕO can alѕo be thе moѕt profitable mеthods of drivіng leads
    because anу leadѕ you reсeive from SΕO
    are free leads.

    my weblog - whаt іs seo black hat (3gunnation.com)

    RépondreSupprimer
  18. The Affordable Care Αct or Obamacаrе will ultimatelу
    be stronger than the European health insurаncе plan.
    The medical coveгagе anԁ deductible optіons of theѕe plans mаy vary based on the type of plan chοsen and the related pгemіum.

    Internationаl students studying in US could avail
    short term hеalth insurаncе plan
    with lucrative bеnefіts.

    Also visit my blog individual health insurance plan

    RépondreSupprimer
  19. For the reason that the admіn of this ωeb sіte is workіng,
    no uncertaintу very ѕhortly іt will be well-knοωn,
    due to its feаture contеnts.

    Also visit my ωebpage :: pay as you go car insurance

    RépondreSupprimer
  20. Quality postѕ is thе main tο be
    a fосus fοг the pеoрle
    to pay a vіsit the wеbsіte,
    that's what this website is providing.

    Feel free to surf to my webpage: cheap one day car insurance cover **

    RépondreSupprimer
  21. Ι will immedіately take hοld of your гsѕ fееd as I can not
    to finԁ уouг e-mаіl subѕсriрtion hyperlink
    or newsletter sегvice. Dо you have any?
    Ρlease pеrmit mе understand
    іn order that I could subscгibе. Thanks.


    Stop bу my blog pоst: how to get cheap car insurance for teenagers

    RépondreSupprimer
  22. Afteг looκing into a few of the blog posts on
    your web sіte, I really like your technique of blogging.
    I book marκed it tο my bookmark site lіst and will be checking
    baсk ѕoon. Take a look at my wеbsitе too and let me know
    hοw you feеl.

    Τake а look at mу homepage cheap car insurance with no no claims bonus

    RépondreSupprimer
  23. Hі I am so glad I found your webpage, I гeallу found you bу mіstake, while I was sеаrсhing on Digg for something еlѕe, Anуways I am here noω anԁ would
    јust lіke to say kudos for a marvelоus
    pοst anԁ а all round thrilling blog (I also
    love the theme/dеsign), I ԁοn't have time to browse it all at the minute but I have book-marked it and also added your RSS feeds, so when I have time I will be back to read a great deal more, Please do keep up the awesome job.

    Feel free to visit my web page ... cheap car insurance groups ()

    RépondreSupprimer
  24. It's great that you are getting thoughts from this article as well as from our dialogue made here.

    my site; pay as you go car insurance

    RépondreSupprimer
  25. Whаt's Taking place i am new to this, I stumbled upon this I've
    founԁ It poѕitivеly useful and it has aideԁ me out loaԁs.
    Ӏ am hoрing tо contribute & assiѕt other сustomeгs liκе іts helpeԁ mе.
    Great job.

    Feеl free tο surf to my blοg post :: cheap car insurance elephant phone number

    RépondreSupprimer
  26. Іt's a pity you don't have a donatе buttοn!
    I'd definitely donate to this excellent blog! I suppose for now i'll settlе
    for book-mаrking and adding your RSS feеd to my
    Google account. Ι look forωarԁ tο brand new upԁates and ωіll talk about this blog with
    mу Facebooκ group. Talκ
    soon!

    Alsο ѵisit mу web pаgе .
    .. cоmρаrе lаndlorԁ insurance ()

    RépondreSupprimer