Loading ...
Sorry, an error occurred while loading the content.

simple tree data structure

Expand Messages
  • Ashish Agarwal
    Are there any simple tree data structure implementations? All I find is fancier stuff like binary search trees, AVL trees, etc. But I just want the most simple
    Message 1 of 8 , Nov 29, 2007
    • 0 Attachment
      Are there any simple tree data structure implementations? All I find is
      fancier stuff like binary search trees, AVL trees, etc. But I just want the
      most simple tree. A tree is a leaf node or a node with some sub-trees.
      Insertion requires specifying the parent node to insert under. There should
      be methods for traversing the tree in depth-first or breadth-first order. It
      should be easy to implement, but that's why I'm hoping its already been
      done.


      [Non-text portions of this message have been removed]
    • Konrad Meyer
      ... I remember seeing an example of a basic tree on http://ocaml-tutorial.org/ . HTH, -- Konrad Meyer http://konrad.sobertillnoon.com/
      Message 2 of 8 , Nov 29, 2007
      • 0 Attachment
        Quoth Ashish Agarwal:
        > Are there any simple tree data structure implementations? All I find is
        > fancier stuff like binary search trees, AVL trees, etc. But I just want the
        > most simple tree. A tree is a leaf node or a node with some sub-trees.
        > Insertion requires specifying the parent node to insert under. There should
        > be methods for traversing the tree in depth-first or breadth-first order. It
        > should be easy to implement, but that's why I'm hoping its already been
        > done.

        I remember seeing an example of a basic tree on http://ocaml-tutorial.org/ .

        HTH,
        --
        Konrad Meyer <konrad@...> http://konrad.sobertillnoon.com/


        [Non-text portions of this message have been removed]
      • Jon Harrop
        ... # type a tree = Node of a * a tree list;; type a tree = Node of a * a tree list ... Not usually in OCaml, where trees are immutable. ... # let rec
        Message 3 of 8 , Nov 29, 2007
        • 0 Attachment
          On Friday 30 November 2007 03:19, Ashish Agarwal wrote:
          > Are there any simple tree data structure implementations? All I find is
          > fancier stuff like binary search trees, AVL trees, etc. But I just want the
          > most simple tree. A tree is a leaf node or a node with some sub-trees.

          # type 'a tree = Node of 'a * 'a tree list;;
          type 'a tree = Node of 'a * 'a tree list

          > Insertion requires specifying the parent node to insert under.

          Not usually in OCaml, where trees are immutable.

          > There should be methods for traversing the tree in depth-first or
          > breadth-first order. It should be easy to implement, but that's why I'm
          > hoping its already been done.

          # let rec depth_first f (Node(x, ts)) =
          f x;
          List.iter (depth_first f) ts;;
          val depth_first : ('a -> 'b) -> 'a tree -> unit = <fun>

          # let rec breadth_first f = function
          | [] -> ()
          | ts ->
          breadth_first f
          (List.flatten
          (List.map (function Node(x, ts) -> f x; ts) ts));;
          val breadth_first : ('a -> 'b) -> 'a tree list -> unit = <fun>

          # let example =
          Node ("root",
          [Node ("left", [Node ("ll", []); Node ("lr", [])]);
          Node ("right", [Node ("rl", []); Node ("rr", [])])]);;
          val example : string tree =
          Node ("root",
          [Node ("left", [Node ("ll", []); Node ("lr", [])]);
          Node ("right", [Node ("rl", []); Node ("rr", [])])])

          # depth_first print_endline example;;
          root
          left
          ll
          lr
          right
          rl
          rr

          # breadth_first print_endline [example];;
          root
          left
          right
          ll
          lr
          rl
          rr
          Interrupted.

          --
          Dr Jon D Harrop, Flying Frog Consultancy Ltd.
          http://www.ffconsultancy.com/products/?e
        • Fabrice Marchant
          Hi ! ... Moreover, you could grep tree in the code examples of Programmation Fonctionnelle Générique et Objet that Philippe Narbel shows here :
          Message 4 of 8 , Nov 30, 2007
          • 0 Attachment
            Hi !

            > Are there any simple tree data structure implementations? All I find is
            > fancier stuff like binary search trees, AVL trees, etc. But I just want the
            > most simple tree. A tree is a leaf node or a node with some sub-trees.
            > Insertion requires specifying the parent node to insert under. There should
            > be methods for traversing the tree in depth-first or breadth-first order. It
            > should be easy to implement, but that's why I'm hoping its already been
            > done.

            Moreover, you could grep "tree" in the code examples of "Programmation Fonctionnelle Générique et Objet" that Philippe Narbel shows here :
            http://dept-info.labri.fr/~narbel/PFGO/Sources/

            Many things on this subject.

            Regards,

            Fabrice.
          • Ashish Agarwal
            Thanks to all for the tips. If I write something that seems general enough, I will be sure to post it. On Nov 30, 2007 11:30 AM, Fabrice Marchant
            Message 5 of 8 , Nov 30, 2007
            • 0 Attachment
              Thanks to all for the tips. If I write something that seems general enough,
              I will be sure to post it.


              On Nov 30, 2007 11:30 AM, Fabrice Marchant <fabrice.marchant@...>
              wrote:

              > Hi !
              >
              >
              > > Are there any simple tree data structure implementations? All I find is
              > > fancier stuff like binary search trees, AVL trees, etc. But I just want
              > the
              > > most simple tree. A tree is a leaf node or a node with some sub-trees.
              > > Insertion requires specifying the parent node to insert under. There
              > should
              > > be methods for traversing the tree in depth-first or breadth-first
              > order. It
              > > should be easy to implement, but that's why I'm hoping its already been
              > > done.
              >
              > Moreover, you could grep "tree" in the code examples of "Programmation
              > Fonctionnelle Générique et Objet" that Philippe Narbel shows here :
              > http://dept-info.labri.fr/~narbel/PFGO/Sources/<http://dept-info.labri.fr/%7Enarbel/PFGO/Sources/>
              >
              > Many things on this subject.
              >
              > Regards,
              >
              > Fabrice.
              >
              >
              >


              [Non-text portions of this message have been removed]
            • Richard Jones
              ... XML-Light (http://tech.motion-twin.com/xmllight.html) uses a simple n-ary tree to represent XML documents. ... I recently got into zippers (hmmm, that
              Message 6 of 8 , Dec 1, 2007
              • 0 Attachment
                On Thu, Nov 29, 2007 at 10:19:51PM -0500, Ashish Agarwal wrote:
                > Are there any simple tree data structure implementations? All I find is
                > fancier stuff like binary search trees, AVL trees, etc. But I just want the
                > most simple tree. A tree is a leaf node or a node with some sub-trees.

                XML-Light (http://tech.motion-twin.com/xmllight.html) uses a simple
                n-ary tree to represent XML documents.

                > Insertion requires specifying the parent node to insert under. There should
                > be methods for traversing the tree in depth-first or breadth-first order. It
                > should be easy to implement, but that's why I'm hoping its already been
                > done.

                I recently got into zippers (hmmm, that sounds sexual?) by reading
                this excellent explanation:

                http://caml.inria.fr/pub/ml-archives/caml-list/2003/04/d9701aacd4580cf3feb60ae8cd7a1836.en.html

                A useful exercise would be to implement zippers for xml-light & submit
                it for inclusion.

                Rich.

                --
                Richard Jones
                Red Hat
              • Ashish Agarwal
                ... Thanks for the references. Reins also implements zippers and I ve been meaning to study them. I do use xml-light (lightly), and so might be interested in
                Message 7 of 8 , Dec 1, 2007
                • 0 Attachment
                  > A useful exercise would be to implement zippers for xml-light & submit
                  > it for inclusion.

                  Thanks for the references. Reins also implements zippers and I've been
                  meaning to study them. I do use xml-light (lightly), and so might be
                  interested in doing this. Not sure when I'll have time though...


                  [Non-text portions of this message have been removed]
                • Karl Zilles
                  ... I would like to do the same thing for the parsed HTML tree that OcamlNet generates. Assuming I ever have time (and that someone hasn t beaten me to it.)
                  Message 8 of 8 , Dec 3, 2007
                  • 0 Attachment
                    Richard Jones wrote:
                    > I recently got into zippers (hmmm, that sounds sexual?) by reading
                    > this excellent explanation:
                    >
                    > http://caml.inria.fr/pub/ml-archives/caml-list/2003/04/d9701aacd4580cf3feb60ae8cd7a1836.en.html
                    > <http://caml.inria.fr/pub/ml-archives/caml-list/2003/04/d9701aacd4580cf3feb60ae8cd7a1836.en.html>
                    >
                    > A useful exercise would be to implement zippers for xml-light & submit
                    > it for inclusion.

                    I would like to do the same thing for the parsed HTML tree that OcamlNet
                    generates. Assuming I ever have time (and that someone hasn't beaten me
                    to it.)
                  Your message has been successfully submitted and would be delivered to recipients shortly.