Subject: Re: [boost] proposal for tree container
From: Arash Partow (arash_at_[hidden])
Date: 2009-07-16 03:12:56
Let me shorten that for you:
"A tree should be an acyclic simple graph."
Quoting Ross Levine <ross.levine_at_[hidden]>:
> Here's what I can come up with:
> 1. A tree is a node-based container. If nonempty, every node has exactly one
> parent, except for one node. This node is called the _root node_.
> 2. Every node has a finite, non-negative number of children. A node's
> children is the same as the set of nodes which have that node as a parent.
> Corollary: There is exactly one simple path between any two different nodes
> (a simple path is a path that has no repeated vertices).
> Corollary: A node's parent lies on the path between it and the root node.
> 1. If any node in tree T have at most K children, then T is a _K-ary tree_.
> 2. A K-ary tree is _full_ if every node has either 0 or K children.
> 3. The _distance_ between two nodes, A and B, is the number of edges in the
> path that connects A and B.
> 4. The _height_ of tree T is equal to the maximum distance from the root
> node to any other node.
> 5. The _degree_ of a node is the number of children, plus the number of
> parents. Since every node (except the root) has exactly one parent, the
> degree of a non-root node is the number of children plus 1.
> 6. A node is a _leaf_ node if it has no children.
> 7. An _ordered tree_ is a tree in which the position of the nodes, and the
> order of a node's children, is significant.
> That's all I can think of right now. Someone check my work.
> Unsubscribe & other changes:
Be one who knows what they don't know,
Instead of being one who knows not what they don't know,
Thinking they know everything about all things.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk