Popular recipes tagged "tree"http://code.activestate.com/recipes/tags/tree/popular/2015-12-18T18:15:18-08:00ActiveState Code RecipesSimple breadth-first, depth-first tree traversal (Python) 2015-12-18T18:15:18-08:00Jack Trainorhttp://code.activestate.com/recipes/users/4076953/http://code.activestate.com/recipes/579138-simple-breadth-first-depth-first-tree-traversal/ <p style="color: grey"> Python recipe 579138 by <a href="/recipes/users/4076953/">Jack Trainor</a> (<a href="/recipes/tags/tree/">tree</a>). </p> <p>When you want to avoid recursion with a tree, you read the tree nodes into a stack, which is organized either breadth-first or depth-first.</p> <p>Here are two dead simple routines for doing so. Most of the recipe is just a test bed for those functions.</p> Highly branched Trees (Python) 2014-05-14T19:16:04-07:00Chris Eckerhttp://code.activestate.com/recipes/users/4180203/http://code.activestate.com/recipes/578879-highly-branched-trees/ <p style="color: grey"> Python recipe 578879 by <a href="/recipes/users/4180203/">Chris Ecker</a> (<a href="/recipes/tags/tree/">tree</a>). Revision 2. </p> <p>Trees are very common data structures and are usually considered to be very efficient. However, this is only true if the tree is balanced, meaning that all branches have roughly the same number of nodes. </p> <p>There are good balancing trees, such as rb-trees or avl-trees. Unfortunately they are quite difficult to implement. An alternative tree structure is the highly branched b-tree (<a href="https://en.wikipedia.org/wiki/B-tree" rel="nofollow">https://en.wikipedia.org/wiki/B-tree</a>). In the c language, binary trees are preferable in most cases. However, in python things are different. This recipe shows how simple it is to implement a b-tree in python. The example is a sorted dict.</p> Monte Carlo Engine : How to find the optimised wager for next bet, following a recent loss. (Python) 2014-04-28T08:41:49-07:00alexander bakerhttp://code.activestate.com/recipes/users/4166679/http://code.activestate.com/recipes/578869-monte-carlo-engine-how-to-find-the-optimised-wager/ <p style="color: grey"> Python recipe 578869 by <a href="/recipes/users/4166679/">alexander baker</a> (<a href="/recipes/tags/finance/">finance</a>, <a href="/recipes/tags/optimise/">optimise</a>, <a href="/recipes/tags/python/">python</a>, <a href="/recipes/tags/tree/">tree</a>). </p> <p>Simple Engine to help understand how to best wager your next bet, given that you just made a loss. The engine uses the modified Powell method to optimise the weight to apply to your wager on the next position.</p> <p>{'My Simple Heads And Tails Model': &lt;BackTest.Simulation object at 0x0583D410&gt;} participants [100] survivors [90.0%] losers [10.0%] weight [0.073858] solving for r: [ 0.07385806] simulations 100, trials 100 starting pot 1000 calling initialise {'My Simple Heads And Tails Model': &lt;BackTest.Simulation object at 0x0583D430&gt;} participants [100] survivors [86.0%] losers [14.0%] weight [0.072220] solving for r: [ 0.07221954] Optimization terminated successfully. Current function value: 8.000000 Iterations: 2 Function evaluations: 30 highest survivability following loss, multiply wager by 7.2949 %</p> <h5 id="">.</h5> <p>Ran 2 tests in 25.545s</p> <p>OK</p> Tri-nary Tree: insertion and deletion (C++) 2014-02-07T04:21:50-08:00Chenhttp://code.activestate.com/recipes/users/4189170/http://code.activestate.com/recipes/578825-tri-nary-tree-insertion-and-deletion/ <p style="color: grey"> C++ recipe 578825 by <a href="/recipes/users/4189170/">Chen</a> (<a href="/recipes/tags/tree/">tree</a>). </p> <p>This contains the insertion and deletion implement for the tri-nary tree data structure.</p> Directories tree (Bash) 2013-10-11T07:11:24-07:00greg zakharovhttp://code.activestate.com/recipes/users/4184115/http://code.activestate.com/recipes/578684-directories-tree/ <p style="color: grey"> Bash recipe 578684 by <a href="/recipes/users/4184115/">greg zakharov</a> (<a href="/recipes/tags/tree/">tree</a>). </p> <p>Imitation of tree -d command.</p> Python Exception Chains (or Trees) (Python) 2013-02-04T15:15:22-08:00Alfehttp://code.activestate.com/recipes/users/4182236/http://code.activestate.com/recipes/578252-python-exception-chains-or-trees/ <p style="color: grey"> Python recipe 578252 by <a href="/recipes/users/4182236/">Alfe</a> (<a href="/recipes/tags/cause/">cause</a>, <a href="/recipes/tags/chain/">chain</a>, <a href="/recipes/tags/exception/">exception</a>, <a href="/recipes/tags/python/">python</a>, <a href="/recipes/tags/reason/">reason</a>, <a href="/recipes/tags/reraise/">reraise</a>, <a href="/recipes/tags/tree/">tree</a>). Revision 2. </p> <p>I have here an approach for chaining exceptions in case a lower layer (<em>library</em>) raises an exception which is caught in an upper layer (<em>application</em>) and later given as <em>cause</em> when a different exception is raised. Passing this <em>cause</em> exception is meant to offer access to the stack trace of the inner exception for debugging.</p> <p>This approach is implemented in Python 3 and in Java, so it definitely makes sense; you also quickly find questions on <a href="http://stackoverflow.com">Stackoverflow</a> concerning it.</p> <p>I even extended this feature by not only using chains of exceptions but also trees. Trees, why trees? Because I had situations in which my application layer tried various approaches using the library layer. If all failed (raised an exception), my application layer also raised an exception; this is the case in which I wanted to pass more than one cause exception into my own exception (hence the tree of causes).</p> <p>My approach uses a special Exception class from which all my exceptions will inherit; standard exception must be wrapped (directly after catching, to preserve the exception stack trace). Please see the examples contained in the code below. The exception itself is rather small.</p> <p>I'd be happy to hear any comments regarding memory leaks (I didn't find any but one never knows), usability, enhancements or similar.</p> Sharing-aware tree transformations (Python) 2012-05-07T08:20:58-07:00Sander Evershttp://code.activestate.com/recipes/users/4173111/http://code.activestate.com/recipes/578117-sharing-aware-tree-transformations/ <p style="color: grey"> Python recipe 578117 by <a href="/recipes/users/4173111/">Sander Evers</a> (<a href="/recipes/tags/fold/">fold</a>, <a href="/recipes/tags/reduce/">reduce</a>, <a href="/recipes/tags/sharing/">sharing</a>, <a href="/recipes/tags/tree/">tree</a>, <a href="/recipes/tags/yaml/">yaml</a>). Revision 2. </p> <p>The function <code>foldsh</code> in this recipe is a general purpose tool for transforming tree-like recursive data structures while keeping track of shared subtrees.</p> <pre class="prettyprint"><code># By default, a branch is encoded as a list of subtrees; each subtree can be a # branch or a leaf (=anything non-iterable). Subtrees can be shared: &gt;&gt;&gt; subtree = [42,44] &gt;&gt;&gt; tree = [subtree,[subtree]] # We can apply a function to all leaves: &gt;&gt;&gt; foldsh(tree, leaf= lambda x: x+1) [[43, 45], [[43, 45]]] # Or apply a function to the branches: &gt;&gt;&gt; foldsh(tree, branch= lambda t,c: list(reversed(c))) [[[44, 42]], [44, 42]] # The sharing is preserved: &gt;&gt;&gt; _[0][0] is _[1] True # Summing up the leaves without double counting of shared subtrees: &gt;&gt;&gt; foldsh(tree, branch= lambda t,c: sum(c), shared= lambda x: 0) 86 </code></pre> <p>In particular, it is useful for transforming YAML documents. An example of this is given below.</p> Simple directory tree view generator (Python) 2012-03-09T09:02:21-08:00ajaymenon.khttp://code.activestate.com/recipes/users/4181225/http://code.activestate.com/recipes/578065-simple-directory-tree-view-generator/ <p style="color: grey"> Python recipe 578065 by <a href="/recipes/users/4181225/">ajaymenon.k</a> (<a href="/recipes/tags/directory/">directory</a>, <a href="/recipes/tags/tree/">tree</a>). </p> <p>An extremely simple tree-view generator for a directory</p> 2-3 Tree (Python) 2011-10-08T21:46:03-07:00Borishttp://code.activestate.com/recipes/users/4179529/http://code.activestate.com/recipes/577898-2-3-tree/ <p style="color: grey"> Python recipe 577898 by <a href="/recipes/users/4179529/">Boris</a> (<a href="/recipes/tags/2_3tree/">2_3tree</a>, <a href="/recipes/tags/algorithms/">algorithms</a>, <a href="/recipes/tags/data/">data</a>, <a href="/recipes/tags/python/">python</a>, <a href="/recipes/tags/structure/">structure</a>, <a href="/recipes/tags/tree/">tree</a>). </p> <p>My implementation of 2-3 Trees on python</p> Text Model (Python) 2015-01-13T22:56:53-08:00Chris Eckerhttp://code.activestate.com/recipes/users/4180203/http://code.activestate.com/recipes/577978-text-model/ <p style="color: grey"> Python recipe 577978 by <a href="/recipes/users/4180203/">Chris Ecker</a> (<a href="/recipes/tags/datastuctures/">datastuctures</a>, <a href="/recipes/tags/text_processing/">text_processing</a>, <a href="/recipes/tags/tree/">tree</a>). Revision 3. </p> <p>A tree data type holding text data together with styling information. </p> Printing breadth First Levels of a graph (Or) Tree (Python) 2011-09-28T12:06:25-07:00Venkateshhttp://code.activestate.com/recipes/users/4179376/http://code.activestate.com/recipes/577876-printing-breadth-first-levels-of-a-graph-or-tree/ <p style="color: grey"> Python recipe 577876 by <a href="/recipes/users/4179376/">Venkatesh</a> (<a href="/recipes/tags/bfs/">bfs</a>, <a href="/recipes/tags/level/">level</a>, <a href="/recipes/tags/tree/">tree</a>). Revision 4. </p> <p>Prints the breadth first Levels of a graph (Or) Tree, by performing Breadth First Search</p> Directory Size (GUI) (Python) 2011-02-09T13:47:54-08:00Stephen Chappellhttp://code.activestate.com/recipes/users/2608421/http://code.activestate.com/recipes/577567-directory-size-gui/ <p style="color: grey"> Python recipe 577567 by <a href="/recipes/users/2608421/">Stephen Chappell</a> (<a href="/recipes/tags/application/">application</a>, <a href="/recipes/tags/directory/">directory</a>, <a href="/recipes/tags/gui/">gui</a>, <a href="/recipes/tags/sizeof/">sizeof</a>, <a href="/recipes/tags/tree/">tree</a>). Revision 2. </p> <p>Have you ever wanted to find out how much room a particular directory was taking up on your hard drive? A roommate of mine in college was having trouble keeping track of where his hard drive space is going, so the following program provided a solution that allows a brief overview of a directory's size along with all of its children. A tree view is created using tkinter and is populated with the directory's name, cumulative size, immediate total file size, and full path. The search button is disabled during a search, and the directory listing with its children is automatically updated.</p> Directory Size (Console) (Python) 2011-02-09T13:29:56-08:00Stephen Chappellhttp://code.activestate.com/recipes/users/2608421/http://code.activestate.com/recipes/577566-directory-size-console/ <p style="color: grey"> Python recipe 577566 by <a href="/recipes/users/2608421/">Stephen Chappell</a> (<a href="/recipes/tags/commandline/">commandline</a>, <a href="/recipes/tags/directory/">directory</a>, <a href="/recipes/tags/sizeof/">sizeof</a>, <a href="/recipes/tags/tree/">tree</a>). </p> <p>Have you ever wanted to find out how much room a particular directory was taking up on your hard drive? A roommate of mine in college was having trouble keeping track of where his hard drive space is going, so the following program provided a solution that allows a brief overview of a directory's size along with all of its children. A tree view is printed out in ASCII characters showing the relationship of each directory along with its size in a format easily readable to humans. The output can always be redirected to a text file if it needs to be saved for viewing later on.</p> kd-tree for nearest neighbor search in a k-dimensional space (Python) 2010-12-17T15:49:08-08:00Matteo Dell'Amicohttp://code.activestate.com/recipes/users/2433284/http://code.activestate.com/recipes/577497-kd-tree-for-nearest-neighbor-search-in-a-k-dimensi/ <p style="color: grey"> Python recipe 577497 by <a href="/recipes/users/2433284/">Matteo Dell'Amico</a> (<a href="/recipes/tags/nearest/">nearest</a>, <a href="/recipes/tags/neighbor/">neighbor</a>, <a href="/recipes/tags/search/">search</a>, <a href="/recipes/tags/tree/">tree</a>). Revision 5. </p> <p>The kd-tree can be used to organize efficient search for nearest neighbors in a k-dimensional space.</p> Windows TREE Emulator (Python) 2010-03-08T12:57:10-08:00Stephen Chappellhttp://code.activestate.com/recipes/users/2608421/http://code.activestate.com/recipes/577091-windows-tree-emulator/ <p style="color: grey"> Python recipe 577091 by <a href="/recipes/users/2608421/">Stephen Chappell</a> (<a href="/recipes/tags/directory/">directory</a>, <a href="/recipes/tags/listing/">listing</a>, <a href="/recipes/tags/tree/">tree</a>, <a href="/recipes/tags/utility/">utility</a>). Revision 2. </p> <p>Windows has a nice command line program capable of printing out a tree of the the folders, sub-folders, and possibly the files of a directory. The tool below mimics a behavioral subset of TREE, Microsoft's inspiring utility. This version is designed to output a similar tree and should be compatible on Windows, Linux, and Macintosh. In case it is not used correctly, a simple usage message will be printed (without notes on the optional "/F" switch). ASCII characters are used.</p> DnTree (Python) 2011-05-04T19:58:38-07:00Andrew Grigorevhttp://code.activestate.com/recipes/users/4172098/http://code.activestate.com/recipes/576966-dntree/ <p style="color: grey"> Python recipe 576966 by <a href="/recipes/users/4172098/">Andrew Grigorev</a> (<a href="/recipes/tags/ldap/">ldap</a>, <a href="/recipes/tags/tree/">tree</a>). Revision 5. </p> <p>Represent hierarchy of Internet domain names or LDAP distinguished names.</p> A Tree Finder (Python) 2009-09-26T09:36:58-07:00Shao-chuan Wanghttp://code.activestate.com/recipes/users/4168519/http://code.activestate.com/recipes/576912-a-tree-finder/ <p style="color: grey"> Python recipe 576912 by <a href="/recipes/users/4168519/">Shao-chuan Wang</a> (<a href="/recipes/tags/algorithm/">algorithm</a>, <a href="/recipes/tags/tree/">tree</a>). </p> <p>This python script is for solving the ACM problem Q1308: Is It A Tree? <a href="http://acm.pku.edu.cn/JudgeOnline/problem?id=1308" rel="nofollow">http://acm.pku.edu.cn/JudgeOnline/problem?id=1308</a></p> Red black tree (Python) 2009-06-20T03:11:59-07:00John Reidhttp://code.activestate.com/recipes/users/4023487/http://code.activestate.com/recipes/576817-red-black-tree/ <p style="color: grey"> Python recipe 576817 by <a href="/recipes/users/4023487/">John Reid</a> (<a href="/recipes/tags/red_black/">red_black</a>, <a href="/recipes/tags/tree/">tree</a>). </p> <p>A straightforward red-black tree implementation based on the algorithms in the "Introduction to Algorithms" book by Cormen, Leiserson, Rivest, Stein. Unfortunately I have not needed delete functionality so this is not implemented yet.</p> Matlab code for displaying 'struct' details (Python) 2008-09-05T13:31:54-07:00Kaushik Ghosehttp://code.activestate.com/recipes/users/4166965/http://code.activestate.com/recipes/576489-matlab-code-for-displaying-struct-details/ <p style="color: grey"> Python recipe 576489 by <a href="/recipes/users/4166965/">Kaushik Ghose</a> (<a href="/recipes/tags/matlab/">matlab</a>, <a href="/recipes/tags/recursion/">recursion</a>, <a href="/recipes/tags/structure/">structure</a>, <a href="/recipes/tags/tree/">tree</a>). </p> <p>This code, when passed a MATLAB structure, will recursively go into it and print out the form of the struct.</p>