<!doctype html>
<html lang="en">
<head>
 <meta charset="utf-8">

 <title>sage_worksheets/binary_tree_sort.sagews</title>
 <meta name="description" content="automatically generated from 'f351622c-d261-4717-abee-4c0bfa210e88:sage_worksheets/binary_tree_sort.sagews' on SageMathCloud">
 <meta name="date" content="2017-02-06T15:13:40">
 <meta data-name="smc-generated" content="version:2">

 <style>
 html {
 font-family: sans-serif;
 display: flex;
 align-items: center;
 justify-content: center;
 margin: 0; padding: 0;
 }
 body {
 width: 50rem;
 counter-reset: line;
 padding: .5rem;
 }
 @media print {
 body { width: 100%; margin: 1rem 1rem 1rem 6rem; font-size: 10pt; }
 }
 pre { margin: 0; }
 div.output + pre.input { margin-top: 1rem; }
 div.output {
 border-left: .2rem solid #33a;
 padding: .3rem;
 margin-left: -.5rem;
 line-height: 1.5;
 }
 div.output img {
 max-width: 70%;
 width: auto;
 height: auto;
 }
 div.output.stdout,
 div.output.stderr,
 div.output.javascript { font-family: monospace; white-space: pre-wrap; }
 div.output.stderr { color: #F00; border-color: #F33; }

 span.sagews-output-image > img,
 span.sagews-output-html > img
 { vertical-align: top; }

 pre.input {
 border-left: .2rem solid #3a3;
 padding: .5rem;
 margin-left: -.5rem;
 }
 pre.input > code {
 display: block;
 line-height: 1.1rem;
 }
 pre.input > code:before {
 margin-left: -3rem;
 counter-increment: line;
 content: counter(line);
 display: inline-block;
 padding: 0 .3rem 0 0;
 margin-right: .5rem;
 color: #888;
 min-width: 2rem;
 text-align: right;
 user-select: none;
 }
 div.header { margin-bottom: 1rem; }
 table.header td { border: 0; }
 table.header tr>td:nth-child(2) {
 font-weight: bold;
 font-family: monospace;
 }
 table {
 border-spacing: 0;
 border-collapse: collapse;
 margin-top: .5rem;
 margin-bottom: .5rem;
 border-color: #888;
 }
 table td, table th {
 padding: .5rem;
 }
 table tr>td {
 vertical-align: top;
 border-top: .05rem solid #888;
 }
 table tr>th {
 vertical-align: bottom;
 border-bottom: .1rem solid #888;
 }
 footer {
 margin-top: 1rem;
 border-top: .1rem solid #888;
 font-size: 70%;
 color: #888;
 text-align: center;
 }
 </style>


 
 <style>
 .cm-keyword { font-weight: bold; color: #339; }
 .cm-atom { color: #666; }
 .cm-number { color: #333; }
 .cm-def { color: #333; font-weight: bold; }
 .cm-variable { color: black; }
 .cm-variable-2 { color:black; }
 .cm-variable-3 { color: black; }
 .cm-property { color: black; }
 .cm-operator { color: black; font-weight: bold; }
 .cm-comment { color: #777; }
 .cm-string { color: #333; }
 .cm-meta { color: #039; }
 .cm-qualifier { color: #666; }
 .cm-builtin { color: #393; font-weight: bold; }
 .cm-bracket { color: #666; }
 .cm-tag { color: #444; font-weight: bold; }
 .cm-attribute { color: #777; }
 .cm-error { color: #000; }
 .cm-header { font-weight: bold; }
 .cm-header-1 { font-size: 1.2rem; }
 .cm-header-2 { font-size: 1.15rem; }
 .cm-header-3 { font-size: 1.12rem; }
 .cm-header-4 { font-size: 1.1rem; }
 .cm-header-5 { font-size: 1rem; }
 .cm-em { font-style: italic; }
 .cm-strong { font-weight: bold; }
 </style>

 <script type="text/javascript">window.MathJax = {"skipStartupTypeset":false,"extensions":["tex2jax.js","asciimath2jax.js"],"jax":["input/TeX","input/AsciiMath","output/SVG"],"tex2jax":{"inlineMath":[["$","$"],["\$","\$"]],"displayMath":[["$$","$$"],["\\[","\\]"]],"processEscapes":true,"ignoreClass":"tex2jax_ignore","skipTags":["script","noscript","style","textarea","pre","code"]},"TeX":{"extensions":["autoload-all.js"],"Macros":{"Bold":["\\mathbb{#1}",1],"ZZ":["\\Bold{Z}",0],"NN":["\\Bold{N}",0],"RR":["\\Bold{R}",0],"CC":["\\Bold{C}",0],"FF":["\\Bold{F}",0],"QQ":["\\Bold{Q}",0],"QQbar":["\\overline{\\QQ}",0],"CDF":["\\Bold{C}",0],"CIF":["\\Bold{C}",0],"CLF":["\\Bold{C}",0],"RDF":["\\Bold{R}",0],"RIF":["\\Bold{I} \\Bold{R}",0],"RLF":["\\Bold{R}",0],"CFF":["\\Bold{CFF}",0],"GF":["\\Bold{F}_{#1}",1],"Zp":["\\ZZ_{#1}",1],"Qp":["\\QQ_{#1}",1],"Zmod":["\\ZZ/#1\\ZZ",1]}},"HTML-CSS":{"linebreaks":{"automatic":true},"scale":80},"SVG":{"linebreaks":{"automatic":true}},"showProcessingMessages":true,"CommonHTML":{"scale":80}};</script>
 <script type="text/javascript" async
 src="https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS_HTML">
 </script>
</head>

<body>
<div class="header">
 <h1>sage_worksheets/binary_tree_sort.sagews</h1>
 <table class="header">
 <tr><td>Author</td><td>Ken Levasseur</td></tr>
 <tr><td>Date</td><td>2017-02-06T15:13:40</td></tr>
 <tr><td>Project</td><td>f351622c-d261-4717-abee-4c0bfa210e88</td></tr>
 <tr><td>Location</td><td><a href="https://sagemathcloud.com/projects/f351622c-d261-4717-abee-4c0bfa210e88/files/sage_worksheets/binary_tree_sort.sagews">sage_worksheets/binary_tree_sort.sagews</a></td></tr>
 <tr><td>Original file</td><td><a href="data:application/octet-stream;base64,77igYzQ4MjA5OTAtZTNlMi00ZGY4LTg4MDgtMzMzYWI3MWFjYjJkae+4oAolaHRtbApXZSBpbXBsZW1lbnQgdGhlIGJpbmFyeSB0cmVlIHNvcnQgYWxnb3J0aG0gaW4gU2FnZU1hdGggYnkgZmlyc3QgZGVmaW5pbmcgYSA8Y29kZT5Ob2RlPC9jb2RlPiBpbiB0aGUgdGhlIHRyZWUgdG8gY29udGFpbiB0aHJlZSBjb21wb25lbnRzLCBhIGtleSB2YWx1ZSwgYSBsZWZ0IGNoaWxkIGFuZCBhIHJpZ2h0IGNoaWxkLiAgVGhpcyBpcyBhY2NvbXBsaXNoZWQgd2l0aCB0aGUgZm9sbG93aW5nIGNvZGUuIEFuIGV4cHJlc3Npb24gb2YgdGhlIGZvcm0gPGNvZGU+Tm9kZShrKTwvY29kZT4gY3JlYXRlcyBhIG5vZGUgd2l0aCBrZXkgPGNvZGU+azwvY29kZT4gYW5kIG5vIGNoaWxkcmVuLgrvuKE3ODVmYWEwNC04YjBiLTQ3MjktYTJlYi05MWRlMjIxNjA5YWXvuKF7ImRvbmUiOnRydWUsImh0bWwiOiJXZSBpbXBsZW1lbnQgdGhlIGJpbmFyeSB0cmVlIHNvcnQgYWxnb3J0aG0gaW4gU2FnZU1hdGggYnkgZmlyc3QgZGVmaW5pbmcgYSA8Y29kZT5Ob2RlPC9jb2RlPiBpbiB0aGUgdGhlIHRyZWUgdG8gY29udGFpbiB0aHJlZSBjb21wb25lbnRzLCBhIGtleSB2YWx1ZSwgYSBsZWZ0IGNoaWxkIGFuZCBhIHJpZ2h0IGNoaWxkLiAgVGhpcyBpcyBhY2NvbXBsaXNoZWQgd2l0aCB0aGUgZm9sbG93aW5nIGNvZGUuIEFuIGV4cHJlc3Npb24gb2YgdGhlIGZvcm0gPGNvZGU+Tm9kZShrKTwvY29kZT4gY3JlYXRlcyBhIG5vZGUgd2l0aCBrZXkgPGNvZGU+azwvY29kZT4gYW5kIG5vIGNoaWxkcmVuLiJ9Cu+4oDJjOWQ1NDdlLWQ0NzQtNDNkZS1hOWE2LWQ4MTA1NGVkMDRhZXPvuKAKY2xhc3MgTm9kZToKICBkZWYgX19pbml0X18oc2VsZiwga2V5dmFsPU5vbmUsTGNoaWxkPU5vbmUsUmNoaWxkPU5vbmUpOgogICAgc2VsZi5rZXkgPSBrZXl2YWwKICAgIHNlbGYubGVmdCA9IExjaGlsZAogICAgc2VsZi5yaWdodCA9IFJjaGlsZArvuKEzYjgyNzI0Ny0yMWZkLTQ2M2EtOTI5Zi1iMGZkN2QzZDNmNDfvuKF7ImRvbmUiOnRydWV977ihCu+4oDhkZjEyYzlmLTM4MDUtNDIwNi05Yjk3LWYyNDljZWJjN2JiNmnvuKAKJWh0bWwKV2UgZGVmaW5lIHRoZSBmdW5jdGlvbiA8Y29kZT5pbnNlcnRfc29ydDwvY29kZT4gdG8gcmVjdXJzaXZlbHkgaW5zZXJ0IGEga2V5IHZhbHVlLCA8Y29kZT5iPC9jb2RlPiwgaW50byBhIHRyZWUgcm9vdGVkIGF0IDxjb2RlPnI8L2NvZGU+LiBXZSB3aWxsIHVzZSB0aGlzIGZ1bmN0aW9uIHRvIGJ1aWxkIGEgYmluYXJ5IHRyZWUuICBTbWFsbGVyIGtleSB2YWx1ZXMgYXJlIHN0ZWVyZWQgdG8gdGhlIGxlZnQgYW5kIGxhcmdlciBvbmVzIHRvIHRoZSByaWdodC4K77ihN2IyZWVmOTItOGQyMi00ZjdmLTk2YjMtYTk4MTg1Y2EzNmY077iheyJkb25lIjp0cnVlLCJodG1sIjoiV2UgZGVmaW5lIHRoZSBmdW5jdGlvbiA8Y29kZT5pbnNlcnRfc29ydDwvY29kZT4gdG8gcmVjdXJzaXZlbHkgaW5zZXJ0IGEga2V5IHZhbHVlLCA8Y29kZT5iPC9jb2RlPiwgaW50byBhIHRyZWUgcm9vdGVkIGF0IDxjb2RlPnI8L2NvZGU+LiBXZSB3aWxsIHVzZSB0aGlzIGZ1bmN0aW9uIHRvIGJ1aWxkIGEgYmluYXJ5IHRyZWUuICBTbWFsbGVyIGtleSB2YWx1ZXMgYXJlIHN0ZWVyZWQgdG8gdGhlIGxlZnQgYW5kIGxhcmdlciBvbmVzIHRvIHRoZSByaWdodC4ifQrvuKA2NWJlMGI4NS1lMWMxLTRlYzItOTcxNS01MzM0NDlmMmQwY2Jz77igCmRlZiBpbnNlcnRfc29ydChyLGIpOgogICAgaWYgYjxyLmtleToKICAgICAgICBpZiByLmxlZnQ9PU5vbmU6CiAgICAgICAgICAgIHIubGVmdD1Ob2RlKGIpCiAgICAgICAgZWxzZToKICAgICAgICAgICAgaW5zZXJ0X3NvcnQoci5sZWZ0LGIpCiAgICBlbHNlOgogICAgICAgIGlmIHIucmlnaHQ9PU5vbmU6CiAgICAgICAgICAgIHIucmlnaHQ9Tm9kZShiKQogICAgICAgIGVsc2U6CiAgICAgICAgICAgIGluc2VydF9zb3J0KHIucmlnaHQsYikK77ihOWMyODJmNzktOWU4YS00MjI0LWJhOGMtYzg2YTZmYTljMmYy77iheyJkb25lIjp0cnVlfe+4oQrvuKAyOTdmZDQ5My00NTczLTQ4NGYtOTM4OS1iMjY1NzZlZmJhNDFp77igCiVodG1sCk9uY2UgdGhlIHRyZWUgaXMgYnVpbHQsIHdlIHRyYXZlcnNlIGl0IHdpdGggdGhlIGZ1bmN0aW9uIDxjb2RlPmlub3JkZXJfdHJhdmVyc2U8L2NvZGU+LCB3aGljaCBhc3NlbWJsZXMgYSBzb3J0ZWQgbGlzdC4K77ihNzc1MTg4MTEtNGRiZC00ZWQ4LWJhN2EtMmY4YmMyNDczNjIy77iheyJkb25lIjp0cnVlLCJodG1sIjoiT25jZSB0aGUgdHJlZSBpcyBidWlsdCwgd2UgdHJhdmVyc2UgaXQgd2l0aCB0aGUgZnVuY3Rpb24gPGNvZGU+aW5vcmRlcl90cmF2ZXJzZTwvY29kZT4sIHdoaWNoIGFzc2VtYmxlcyBhIHNvcnRlZCBsaXN0LiJ9Cu+4oDhiNGE5MjAyLTcwNDAtNDIzOC1hNWZkLTI2Y2FmOGI1NWI4N3PvuKAKZGVmIGlub3JkZXJfdHJhdmVyc2Uocik6CiAgICBpZiByLmxlZnQhPU5vbmU6CiAgICAgICAgbHM9aW5vcmRlcl90cmF2ZXJzZShyLmxlZnQpCiAgICBlbHNlOgogICAgICAgIGxzPVtdCiAgICBtPXIua2V5CiAgICBpZiByLnJpZ2h0IT1Ob25lOgogICAgICAgIHJzPWlub3JkZXJfdHJhdmVyc2Uoci5yaWdodCkKICAgIGVsc2U6CiAgICAgICAgcnM9W10KICAgIHJldHVybiBscytbbV0rcnMKCu+4oTMwNTMwM2ZjLTYyYjktNDI5NC1iZmQwLTgxNzEwODRhMjkxOe+4oXsiZG9uZSI6dHJ1ZX3vuKEK77igYzY0ZjRiYTktOWFjMy00NzAxLTkyZmItZjgzM2IxODg1N2Eyae+4oAolaHRtbCBXZSBkZW1vbnN0cmF0ZSB0aGUgcHJvY2VzcyB3aXRoIGEgbGlzdCBvZiBpbnRlZ2Vycy4K77ihYWVkNDBmZTMtMDUxOS00MTk1LTkxNWQtNTVjYzFlNWEwNTZl77iheyJodG1sIjoiV2UgZGVtb25zdHJhdGUgdGhlIHByb2Nlc3Mgd2l0aCBhIGxpc3Qgb2YgaW50ZWdlcnMuIn3vuKF7ImRvbmUiOnRydWV977ihCu+4oGIzY2MzMjU1LWE0OTMtNDIzZS1iZjkwLTNkNTc4YzE3M2Q4N3PvuKAKYT1bNjk1Myw4MTEsMjMyNCwxODg0LDg5NDUsMTk0MywyOTIzLDc5MDksMzM5MCw4MjI5LDgzMzcsOTY1Niw0NTQ1LDcwODIsNzMzMyw2NDYxLDUzMDYsMjk0NSw4NDE0LDkzNTIsMjk5Myw4NjYzLDgyNjAsNjgxMCw0MjYzXQrvuKE1ZmViOWFkNC1iYTMxLTRhYzgtYTlmMS00MDc0ZTgyN2Q3N2XvuKF7ImRvbmUiOnRydWV977ihCu+4oDVlZjVmYjUyLWIxY2EtNDY0OC1hMWMxLTI0NjMwYzljNTgwNGnvuKAKJWh0bWwgIFRoZSBmaXJzdCBudW1iZXIgaW4gdGhlIGxpc3QgaXMgcGxhY2VkIGF0IHRoZSByb290IG9mIG91ciB0cmVlIGFuZCB0aGVuIHRoZSByZXN0IGFyZSBpbnNlcnRlZCB1c2luZyA8Y29kZT5pbnNlcnRfc29ydDwvY29kZT4uIE5vdGU6IEluIFB5dGhvbiAoYW5kIGhlbmNlIGluIFNhZ2VNYXRoKSwgYWxsIGJ1dCB0aGUgZmlyc3QgZW50cnkgaW4gYSBsaXN0IDxjb2RlPmE8L2NvZGU+IGlzIG1vc3QgZWFzaWx5IHNwZWNpZmllZCB1c2luZyA8cT5zbGljZTwvcT4gbm90YXRpb24sIDxjb2RlPmFbMTpdPC9jb2RlPi4K77ihNDY0MWJlOTctMGNiZi00Nzc4LWI1Y2YtOGNkYTAwZWEzMzlk77iheyJodG1sIjoiIFRoZSBmaXJzdCBudW1iZXIgaW4gdGhlIGxpc3QgaXMgcGxhY2VkIGF0IHRoZSByb290IG9mIG91ciB0cmVlIGFuZCB0aGVuIHRoZSByZXN0IGFyZSBpbnNlcnRlZCB1c2luZyA8Y29kZT5pbnNlcnRfc29ydDwvY29kZT4uIE5vdGU6IEluIFB5dGhvbiAoYW5kIGhlbmNlIGluIFNhZ2VNYXRoKSwgYWxsIGJ1dCB0aGUgZmlyc3QgZW50cnkgaW4gYSBsaXN0IDxjb2RlPmE8L2NvZGU+IGlzIG1vc3QgZWFzaWx5IHNwZWNpZmllZCB1c2luZyA8cT5zbGljZTwvcT4gbm90YXRpb24sIDxjb2RlPmFbMTpdPC9jb2RlPi4ife+4oXsiZG9uZSI6dHJ1ZX3vuKEK77igYWEzOWU2ZTAtYTYxYi00NDFiLWI5N2ItYjg5OTU5ODZlZmYwc++4oApyb290PU5vZGUoYVswXSkKZm9yIGIgaW4gYVsxOl06CiAgICBpbnNlcnRfc29ydChyb290LGIpCu+4oTIzMmNmODA3LTU1OTQtNGE5ZC04YzU4LTE3YjM0MWM0MDQ5Me+4oXsiZG9uZSI6dHJ1ZX3vuKEK77igMWMwZWVhYjItMjY3Yi00MWQ5LTgzOTEtNmE3NTM5ZDJmNzcxae+4oAolaHRtbApOb3cgd2UgdHJhdmVyc2UgdGhlIHRyZWUgdG8gZ2V0IG91ciBzb3J0ZWQgbGlzdC4K77ihYjBiYmI2ZGItOTk2MC00ODcwLTkxYjYtZmY1ZDA1ZmQ1MGZk77iheyJkb25lIjp0cnVlLCJodG1sIjoiTm93IHdlIHRyYXZlcnNlIHRoZSB0cmVlIHRvIGdldCBvdXIgc29ydGVkIGxpc3QuIn0K77igMmU0ZGY5MGEtNTQ4Yy00Y2E3LTljN2YtOGU4NzU3M2U5MzU4c++4oAppbm9yZGVyX3RyYXZlcnNlKHJvb3QpCu+4oTlmYTc5ZTFmLWI4MmMtNDQzMi05OTc5LTc5ODZmMTJhMjU3Yu+4oXsic3Rkb3V0IjoiWzgxMSwgMTg4NCwgMTk0MywgMjMyNCwgMjkyMywgMjk0NSwgMjk5MywgMzM5MCwgNDI2MywgNDU0NSwgNTMwNiwgNjQ2MSwgNjgxMCwgNjk1MywgNzA4MiwgNzMzMywgNzkwOSwgODIyOSwgODI2MCwgODMzNywgODQxNCwgODY2MywgODk0NSwgOTM1MiwgOTY1Nl1cbiJ977iheyJkb25lIjp0cnVlfe+4oQoKCgoKCgoKCgo=" download="binary_tree_sort.sagews">binary_tree_sort.sagews</td></tr>
 <script type="text/javascript">
 var is_chrome = navigator.userAgent.indexOf('Chrome') > -1;
 var is_safari = navigator.userAgent.indexOf("Safari") > -1;
 if (is_safari && !is_chrome) {
 document.write("<tr><td colspan='2'>(when downloading, rename file to binary_tree_sort.sagews)</td></tr>");
 }
 </script>
 </table>
</div>
<div class="output html">We implement the binary tree sort algorthm in SageMath by first defining a <code>Node</code> in the the tree to contain three components, a key value, a left child and a right child. This is accomplished with the following code. An expression of the form <code>Node(k)</code> creates a node with key <code>k</code> and no children.</div>
<pre class="input"><code>class Node:</code><code> def __init__(self, keyval=None,Lchild=None,Rchild=None):</code><code> self.key = keyval</code><code> self.left = Lchild</code><code> self.right = Rchild</code></pre>
<div class="output html">We define the function <code>insert_sort</code> to recursively insert a key value, <code>b</code>, into a tree rooted at <code>r</code>. We will use this function to build a binary tree. Smaller key values are steered to the left and larger ones to the right.</div>
<pre class="input"><code>def insert_sort(r,b):</code><code> if b&lt;r.key:</code><code> if r.left==None:</code><code> r.left=Node(b)</code><code> else:</code><code> insert_sort(r.left,b)</code><code> else:</code><code> if r.right==None:</code><code> r.right=Node(b)</code><code> else:</code><code> insert_sort(r.right,b)</code></pre>
<div class="output html">Once the tree is built, we traverse it with the function <code>inorder_traverse</code>, which assembles a sorted list.</div>
<pre class="input"><code>def inorder_traverse(r):</code><code> if r.left!=None:</code><code> ls=inorder_traverse(r.left)</code><code> else:</code><code> ls=[]</code><code> m=r.key</code><code> if r.right!=None:</code><code> rs=inorder_traverse(r.right)</code><code> else:</code><code> rs=[]</code><code> return ls+[m]+rs</code><code></code></pre>
<div class="output html">We demonstrate the process with a list of integers.</div>
<pre class="input"><code>a=[6953,811,2324,1884,8945,1943,2923,7909,3390,8229,8337,9656,4545,7082,7333,6461,5306,2945,8414,9352,2993,8663,8260,6810,4263]</code></pre>
<div class="output html"> The first number in the list is placed at the root of our tree and then the rest are inserted using <code>insert_sort</code>. Note: In Python (and hence in SageMath), all but the first entry in a list <code>a</code> is most easily specified using <q>slice</q> notation, <code>a[1:]</code>.</div>
<pre class="input"><code>root=Node(a[0])</code><code>for b in a[1:]:</code><code> insert_sort(root,b)</code></pre>
<div class="output html">Now we traverse the tree to get our sorted list.</div>
<pre class="input"><code>inorder_traverse(root)</code></pre>
<div class="output stdout">[811, 1884, 1943, 2324, 2923, 2945, 2993, 3390, 4263, 4545, 5306, 6461, 6810, 6953, 7082, 7333, 7909, 8229, 8260, 8337, 8414, 8663, 8945, 9352, 9656]
</div>
<footer>
 <div>generated 2017-02-06T15:13:40 on
 <a href="https://sagemathcloud.com">SageMathCloud</a>
 </div>
</footer>
</body>
</html>

Collaborative Calculation and Data Science

colby

sagemath

cornellcollege

facebook

github

google

twitter

depaul

Worksheets related to Applied Discrete Structures