Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!eternal-september.org!feeder.eternal-september.org!mx02.eternal-september.org!.POSTED!not-for-mail From: Steve Thompson Newsgroups: comp.lang.c Subject: Re: primitive instruction for programming Date: Sun, 19 Apr 2015 16:28:33 +0000 Organization: Friends of the Galactic Collective Lines: 129 Message-ID: References: <263NCi.tYn.6s7aE@gmail.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Injection-Info: mx02.eternal-september.org; posting-host="dfca600df3027c25a5e3889f25105c66"; logging-data="12371"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18/99Iw/9yC/8Yia/ayzobF" User-Agent: NN 6.4.3 Cancel-Lock: sha1:gJSOo4DJ/InLuyWRAs/RjrNyv1Q= Xref: csiph.com comp.lang.c:60451 On Sat, Apr 18, 2015 at 06:59:14PM -0700, Tim Rentsch wrote: > Steve Thompson writes: > > On Thu, Apr 16, 2015 at 09:04:34AM -0700, Tim Rentsch wrote: > >> Steve Thompson writes: > >> > >>> On Mon, Apr 13, 2015 at 11:36:56AM +0100, Bartc wrote: > >>>> On 13/04/2015 11:28, asetofsymbols@gmail.com wrote: > >>>>> Bartc wrote: > >>>>> [code example that uses labels and goto's] > >>>> > >>>> This style of code is more error-prone. It's not even obvious > >>>> where l1 needs to go; I can put it in several places and it > >>>> would still compile, but the program won't work. > >>>> > >>>> This is something that just isn't a problem when using > >>>> conventional control structures; why do you want to introduce > >>>> a new source of bugs? > >>> > >>> One of the things I've been trying to do is an inorder traversal > >>> of a binary tree without using recursion. With normal control > >>> structures it doesn't seem possible without using goto. > >> > >> This is an interesting problem. It has a solution that is > >> fairly simple but not immediately obvious. The key idea is > >> to keep track of two different kinds of state - a (pointer to > >> a) tree which represents a completely unprocessed subtree, > >> and a stack of (pointers to) trees which represent subtrees > >> that have had their left sides taken care of but still need > >> their value processed and their right side done; loop over > >> processing those as long as the unprocessed subtree is > >> non-empty or the stack is non-empty, always processing an > >> unprocessed subtree first. Here is a function to illustrate > >> that does inorder printing (the Index type is just an > >> ordinary integer type; note that the type Tree is a pointer > >> type, so the 'stack' variable is a pointer to an array of > >> pointers): > > > > That is a succint description. As I wrote in a followup I should > > have clarified that I found an algorithm, but it is rather goto > > oriented. > > I saw that. I find code like that very difficult to understand. > Perhaps not completely impenetrable, but enough so to raise at > least a couple of red flags in a code review. It is one of those examples that straddles the line. Some programmers will understand what it does without much difficulty, wheras intermediate/beginners may be instantly confused. Fortunately it is my project and coding standard, and not subject to third-party constraints. > >> void > >> inorder_print( Tree root ){ > >> Tree *stack = malloc( 100 * sizeof *stack ); > > > > A balanced binary tree with a depth of 90 will easily exceed the > > number of nodes one might hope to address with a 64-bit address > > space. > > That depends on how good the balancing is. In any case, the > number chosen was meant only to be sufficient, not minimal. I understood that the number was somewhat arbitrary, but I wanted to point out the potential risk since we are not discussing a particular C implementation of a known binary tree algorithm. > > If the tree is unbalanced you should guard against stack overflow > > or make sure that your insert/delete functions catch this. > > Of course. I didn't think it was important to mention this, > since any decent binary tree package will do some sort of > balancing. > > >> Index next = 0; > >> Tree tree = root; > >> > >> while( tree || next > 0 ){ > >> if( tree ){ > >> stack[ next++ ] = tree; > >> tree = tree->left; > >> } else { > >> tree = stack[ --next ]; > >> printf( " %d", tree->value ); > >> tree = tree->right; > >> } > >> } > >> printf( "\n" ); > >> > >> free( stack ); > >> } > > > > I think one of the lessons here is that parent pointers are pretty > > much superfluous to binary tree algorithms, and that recursion is > > mostly avoidable. > > Whether parent pointers are useful depends I think on what > operations need to be supported. As for recursion, I think > that's the wrong takeaway - binary trees are one area where > recursion is an excellent fit in terms of both ease of coding > and performance. I think you are probably correct. My binary tree package suffers from the defect that it depends on a descriptor which identifies the tree root (and describes tree properties), and therfore treating a subtree as a tree introduces additional complexity. > I'm wondering why you didn't have any comments on the function > shown, after your earlier comments about finding a solution > without goto. Ah, but I did not find a solution without goto, only the one I posted. Actually, nearly all loops use 'goto' but it is hidden by the C compiler. At any rate, I will concede that your algorithm is clearer and more compact. Regards, Steve Thompson -- "If I had a nickel for every time some idiot called me about a computer problem that turned out to be user error, I would be able to retire and spend the rest of my days cultivating clues in my backyard hillside garden." -- MysteryDog in 24hoursupport.helpdesk.