nit-picking an explanation...

SamBC sambc at nights.force9.co.uk
Sun Jul 23 14:05:26 PDT 2000


In the explanation of Bison (Appendix A, HTML Page x8082), a binary tree is
used. When used in this manner, a binary tree should be presented for
in-order traversal, which the tree you show is not. The left and right main
sub-trees need to be swapped.

Explained differently:

The description you give shows:

            +
           / \
          1   *
             / \
            2   3

which, as in-order traversal, is 1 + 2 * 3. Given that such trees are used
to store data unambiguously, and operators are evaluated immediately, this
gives the result 9. The correct tree would be (IMO):

            +
           / \
          *   1
         / \
        2   3

Of course, thinking off the trees in terms of simplifiable sub-trees would
mean that the two are identical, but the latter suits both methods of tree
interpretation.

If you got this straight from a manpage, sorry, but i thought I would point
it out...


SamBC
The Movement for simpleLinux	http://sourceforge.net/projects/simpleLinux/
	  site soon to be at	http://simplelinux.sourceforge.net

--
Mail archive: http://www.pcrdallas.com/mail-archives/lfs-discuss
IRC access: server: irc.linuxfromscratch.org port: 6667 channel: #LFS
Unsubscribe: email lfs-discuss-request at linuxfromscratch.org and put
"unsubscribe" (without the quotation marks) in the body of the message
(no subject is required)



More information about the lfs-dev mailing list