CINXE.COM

<!DOCTYPE html><html> <head> <title>complete binary tree</title>  <meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> <link rel="stylesheet" href="LaTeXML.css" type="text/css"> <link rel="stylesheet" href="ltx-article.css" type="text/css"> <link rel="stylesheet" href="https://cdn.rawgit.com/holtzermann17/3f71ceeb3b055e1ddc3b6c11fb1f074c/raw/2bb23e3b173ff96840797fc0c3bcb8c54085df8e/LaTeXML.css" type="text/css"> <link rel="stylesheet" href="https://cdn.rawgit.com/holtzermann17/4bda0365b30858ac2fb83623185fe3ec/raw/cedd84ed3e3ad597c5d293f443ecfe4803741c6b/ltx-article.css" type="text/css"> <script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-MML-AM_CHTML" type="text/javascript"></script> </head> <body> <div class="ltx_page_main"> <div class="ltx_page_content"> <article class="ltx_document ltx_authors_1line"> <h1 class="ltx_title ltx_title_document">complete binary tree</h1> <div id="p1" class="ltx_para"> <br class="ltx_break"> <p class="ltx_p">A <em class="ltx_emph ltx_font_italic"><a class="nnexus_concepts" href="javascript:void(0)" onclick="this.nextSibling.style.display='inline'">complete binary tree</a><sup style="display: none;"><a class="nnexus_concept" href="http://mathworld.wolfram.com/CompleteBinaryTree.html"><img src="http://mathworld.wolfram.com/favicon_mathworld.png" alt="Mathworld"></img></a><a class="nnexus_concept" href="http://planetmath.org/paradoxofthebinarytree"><img src="http://planetmath.org/sites/default/files/fab-favicon.ico" alt="Planetmath"></img></a><a class="nnexus_concept" href="http://planetmath.org/completebinarytree"><img src="http://planetmath.org/sites/default/files/fab-favicon.ico" alt="Planetmath"></img></a></sup></em> is a <a class="nnexus_concepts" href="javascript:void(0)" onclick="this.nextSibling.style.display='inline'">binary tree</a><sup style="display: none;"><a class="nnexus_concept" href="http://mathworld.wolfram.com/BinaryTree.html"><img src="http://mathworld.wolfram.com/favicon_mathworld.png" alt="Mathworld"></img></a><a class="nnexus_concept" href="http://planetmath.org/binarytree"><img src="http://planetmath.org/sites/default/files/fab-favicon.ico" alt="Planetmath"></img></a></sup> with the additional <a class="nnexus_concept" href="http://planetmath.org/property">property</a> that every node must have exactly two “<a class="nnexus_concept" href="http://planetmath.org/treesettheoretic">children</a>” if an <a class="nnexus_concepts" href="javascript:void(0)" onclick="this.nextSibling.style.display='inline'">internal node</a><sup style="display: none;"><a class="nnexus_concept" href="http://planetmath.org/internalnodeofatree"><img src="http://planetmath.org/sites/default/files/fab-favicon.ico" alt="Planetmath"></img></a><a class="nnexus_concept" href="http://planetmath.org/extendedbinarytree"><img src="http://planetmath.org/sites/default/files/fab-favicon.ico" alt="Planetmath"></img></a></sup>, and zero children if a <a class="nnexus_concept" href="http://planetmath.org/leafnodeofatree">leaf node</a>.</p> </div> <div id="p2" class="ltx_para"> <p class="ltx_p">More precisely: for our <a class="nnexus_concept" href="http://planetmath.org/principleoffiniteinduction">base case</a>, the complete binary tree of exactly one node is simply the tree consisting of that node by itself. The property of being “<a class="nnexus_concepts" href="javascript:void(0)" onclick="this.nextSibling.style.display='inline'">complete</a><sup style="display: none;"><a class="nnexus_concept" href="http://planetmath.org/soundcomplete"><img src="http://planetmath.org/sites/default/files/fab-favicon.ico" alt="Planetmath"></img></a><a class="nnexus_concept" href="http://planetmath.org/completegraph"><img src="http://planetmath.org/sites/default/files/fab-favicon.ico" alt="Planetmath"></img></a><a class="nnexus_concept" href="http://planetmath.org/kripkesemantics"><img src="http://planetmath.org/sites/default/files/fab-favicon.ico" alt="Planetmath"></img></a><a class="nnexus_concept" href="http://planetmath.org/maximallyconsistent"><img src="http://planetmath.org/sites/default/files/fab-favicon.ico" alt="Planetmath"></img></a></sup>” is preserved if, at each step, we expand the tree by connecting exactly zero or two <a class="nnexus_concept" href="http://mathworld.wolfram.com/Individual.html">individual</a> nodes (or complete binary trees) to any node in the tree (but both must be <a class="nnexus_concept" href="http://planetmath.org/connectedgraph">connected</a> to the same node.) </p> <table class="ltx_tabular ltx_align_right ltx_guessed_headers ltx_align_middle"> <tbody class="ltx_tbody"> <tr class="ltx_tr"> <th class="ltx_td ltx_align_left ltx_th ltx_th_row ltx_border_l ltx_border_t">Title</th> <td class="ltx_td ltx_align_left ltx_border_r ltx_border_t">complete binary tree</td> </tr> <tr class="ltx_tr"> <th class="ltx_td ltx_align_left ltx_th ltx_th_row ltx_border_l"><a class="nnexus_concept" href="http://planetmath.org/canonical">Canonical</a> name</th> <td class="ltx_td ltx_align_left ltx_border_r">CompleteBinaryTree</td> </tr> <tr class="ltx_tr"> <th class="ltx_td ltx_align_left ltx_th ltx_th_row ltx_border_l">Date of creation</th> <td class="ltx_td ltx_align_left ltx_border_r">2013-03-22 12:30:14</td> </tr> <tr class="ltx_tr"> <th class="ltx_td ltx_align_left ltx_th ltx_th_row ltx_border_l">Last modified on</th> <td class="ltx_td ltx_align_left ltx_border_r">2013-03-22 12:30:14</td> </tr> <tr class="ltx_tr"> <th class="ltx_td ltx_align_left ltx_th ltx_th_row ltx_border_l">Owner</th> <td class="ltx_td ltx_align_left ltx_border_r">akrowne (2)</td> </tr> <tr class="ltx_tr"> <th class="ltx_td ltx_align_left ltx_th ltx_th_row ltx_border_l">Last modified by</th> <td class="ltx_td ltx_align_left ltx_border_r">akrowne (2)</td> </tr> <tr class="ltx_tr"> <th class="ltx_td ltx_align_left ltx_th ltx_th_row ltx_border_l">Numerical id</th> <td class="ltx_td ltx_align_left ltx_border_r">7</td> </tr> <tr class="ltx_tr"> <th class="ltx_td ltx_align_left ltx_th ltx_th_row ltx_border_l">Author</th> <td class="ltx_td ltx_align_left ltx_border_r">akrowne (2)</td> </tr> <tr class="ltx_tr"> <th class="ltx_td ltx_align_left ltx_th ltx_th_row ltx_border_l">Entry type</th> <td class="ltx_td ltx_align_left ltx_border_r"><a class="nnexus_concept" href="http://planetmath.org/definition">Definition</a></td> </tr> <tr class="ltx_tr"> <th class="ltx_td ltx_align_left ltx_th ltx_th_row ltx_border_l"><a class="nnexus_concept" href="http://mathworld.wolfram.com/Classification.html">Classification</a></th> <td class="ltx_td ltx_align_left ltx_border_r">msc 05C05</td> </tr> <tr class="ltx_tr"> <th class="ltx_td ltx_align_left ltx_th ltx_th_row ltx_border_l">Synonym</th> <td class="ltx_td ltx_align_left ltx_border_r">complete</td> </tr> <tr class="ltx_tr"> <th class="ltx_td ltx_align_left ltx_th ltx_th_row ltx_border_b ltx_border_l">Related topic</th> <td class="ltx_td ltx_align_left ltx_border_b ltx_border_r">ExtendedBinaryTree</td> </tr> </tbody> </table> </div> </article> </div> <footer class="ltx_page_footer"> <div class="ltx_page_logo">Generated on Thu Feb 8 20:40:15 2018 by <a href="http://dlmf.nist.gov/LaTeXML/">LaTeXML <img src="data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAsAAAAOCAYAAAD5YeaVAAAAAXNSR0IArs4c6QAAAAZiS0dEAP8A/wD/oL2nkwAAAAlwSFlzAAALEwAACxMBAJqcGAAAAAd0SU1FB9wKExQZLWTEaOUAAAAddEVYdENvbW1lbnQAQ3JlYXRlZCB3aXRoIFRoZSBHSU1Q72QlbgAAAdpJREFUKM9tkL+L2nAARz9fPZNCKFapUn8kyI0e4iRHSR1Kb8ng0lJw6FYHFwv2LwhOpcWxTjeUunYqOmqd6hEoRDhtDWdA8ApRYsSUCDHNt5ul13vz4w0vWCgUnnEc975arX6ORqN3VqtVZbfbTQC4uEHANM3jSqXymFI6yWazP2KxWAXAL9zCUa1Wy2tXVxheKA9YNoR8Pt+aTqe4FVVVvz05O6MBhqUIBGk8Hn8HAOVy+T+XLJfLS4ZhTiRJgqIoVBRFIoric47jPnmeB1mW/9rr9ZpSSn3Lsmir1fJZlqWlUonKsvwWwD8ymc/nXwVBeLjf7xEKhdBut9Hr9WgmkyGEkJwsy5eHG5vN5g0AKIoCAEgkEkin0wQAfN9/cXPdheu6P33fBwB4ngcAcByHJpPJl+fn54mD3Gg0NrquXxeLRQAAwzAYj8cwTZPwPH9/sVg8PXweDAauqqr2cDjEer1GJBLBZDJBs9mE4zjwfZ85lAGg2+06hmGgXq+j3+/DsixYlgVN03a9Xu8jgCNCyIegIAgx13Vfd7vdu+FweG8YRkjXdWy329+dTgeSJD3ieZ7RNO0VAXAPwDEAO5VKndi2fWrb9jWl9Esul6PZbDY9Go1OZ7PZ9z/lyuD3OozU2wAAAABJRU5ErkJggg==" alt="[LOGO]"></a> </div></footer> </div> </body> </html>