-
Notifications
You must be signed in to change notification settings - Fork 3
/
Copy pathtrees.html
179 lines (179 loc) · 12.9 KB
/
trees.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
<!doctype html>
<html lang="en">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1, minimum-scale=1" />
<meta name="generator" content="pdoc 0.10.0" />
<title>dalpy.trees API documentation</title>
<meta name="description" content="Module that holds classes and functions related to trees …" />
<link rel="preload stylesheet" as="style" href="https://cdnjs.cloudflare.com/ajax/libs/10up-sanitize.css/11.0.1/sanitize.min.css" integrity="sha256-PK9q560IAAa6WVRRh76LtCaI8pjTJ2z11v0miyNNjrs=" crossorigin>
<link rel="preload stylesheet" as="style" href="https://cdnjs.cloudflare.com/ajax/libs/10up-sanitize.css/11.0.1/typography.min.css" integrity="sha256-7l/o7C8jubJiy74VsKTidCy1yBkRtiUGbVkYBylBqUg=" crossorigin>
<link rel="stylesheet preload" as="style" href="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/10.1.1/styles/github.min.css" crossorigin>
<style>:root{--highlight-color:#fe9}.flex{display:flex !important}body{line-height:1.5em}#content{padding:20px}#sidebar{padding:30px;overflow:hidden}#sidebar > *:last-child{margin-bottom:2cm}.http-server-breadcrumbs{font-size:130%;margin:0 0 15px 0}#footer{font-size:.75em;padding:5px 30px;border-top:1px solid #ddd;text-align:right}#footer p{margin:0 0 0 1em;display:inline-block}#footer p:last-child{margin-right:30px}h1,h2,h3,h4,h5{font-weight:300}h1{font-size:2.5em;line-height:1.1em}h2{font-size:1.75em;margin:1em 0 .50em 0}h3{font-size:1.4em;margin:25px 0 10px 0}h4{margin:0;font-size:105%}h1:target,h2:target,h3:target,h4:target,h5:target,h6:target{background:var(--highlight-color);padding:.2em 0}a{color:#058;text-decoration:none;transition:color .3s ease-in-out}a:hover{color:#e82}.title code{font-weight:bold}h2[id^="header-"]{margin-top:2em}.ident{color:#900}pre code{background:#f8f8f8;font-size:.8em;line-height:1.4em}code{background:#f2f2f1;padding:1px 4px;overflow-wrap:break-word}h1 code{background:transparent}pre{background:#f8f8f8;border:0;border-top:1px solid #ccc;border-bottom:1px solid #ccc;margin:1em 0;padding:1ex}#http-server-module-list{display:flex;flex-flow:column}#http-server-module-list div{display:flex}#http-server-module-list dt{min-width:10%}#http-server-module-list p{margin-top:0}.toc ul,#index{list-style-type:none;margin:0;padding:0}#index code{background:transparent}#index h3{border-bottom:1px solid #ddd}#index ul{padding:0}#index h4{margin-top:.6em;font-weight:bold}@media (min-width:200ex){#index .two-column{column-count:2}}@media (min-width:300ex){#index .two-column{column-count:3}}dl{margin-bottom:2em}dl dl:last-child{margin-bottom:4em}dd{margin:0 0 1em 3em}#header-classes + dl > dd{margin-bottom:3em}dd dd{margin-left:2em}dd p{margin:10px 0}.name{background:#eee;font-weight:bold;font-size:.85em;padding:5px 10px;display:inline-block;min-width:40%}.name:hover{background:#e0e0e0}dt:target .name{background:var(--highlight-color)}.name > span:first-child{white-space:nowrap}.name.class > span:nth-child(2){margin-left:.4em}.inherited{color:#999;border-left:5px solid #eee;padding-left:1em}.inheritance em{font-style:normal;font-weight:bold}.desc h2{font-weight:400;font-size:1.25em}.desc h3{font-size:1em}.desc dt code{background:inherit}.source summary,.git-link-div{color:#666;text-align:right;font-weight:400;font-size:.8em;text-transform:uppercase}.source summary > *{white-space:nowrap;cursor:pointer}.git-link{color:inherit;margin-left:1em}.source pre{max-height:500px;overflow:auto;margin:0}.source pre code{font-size:12px;overflow:visible}.hlist{list-style:none}.hlist li{display:inline}.hlist li:after{content:',\2002'}.hlist li:last-child:after{content:none}.hlist .hlist{display:inline;padding-left:1em}img{max-width:100%}td{padding:0 .5em}.admonition{padding:.1em .5em;margin-bottom:1em}.admonition-title{font-weight:bold}.admonition.note,.admonition.info,.admonition.important{background:#aef}.admonition.todo,.admonition.versionadded,.admonition.tip,.admonition.hint{background:#dfd}.admonition.warning,.admonition.versionchanged,.admonition.deprecated{background:#fd4}.admonition.error,.admonition.danger,.admonition.caution{background:lightpink}</style>
<style media="screen and (min-width: 700px)">@media screen and (min-width:700px){#sidebar{width:30%;height:100vh;overflow:auto;position:sticky;top:0}#content{width:70%;max-width:100ch;padding:3em 4em;border-left:1px solid #ddd}pre code{font-size:1em}.item .name{font-size:1em}main{display:flex;flex-direction:row-reverse;justify-content:flex-end}.toc ul ul,#index ul{padding-left:1.5em}.toc > ul > li{margin-top:.5em}}</style>
<style media="print">@media print{#sidebar h1{page-break-before:always}.source{display:none}}@media print{*{background:transparent !important;color:#000 !important;box-shadow:none !important;text-shadow:none !important}a[href]:after{content:" (" attr(href) ")";font-size:90%}a[href][title]:after{content:none}abbr[title]:after{content:" (" attr(title) ")"}.ir a:after,a[href^="javascript:"]:after,a[href^="#"]:after{content:""}pre,blockquote{border:1px solid #999;page-break-inside:avoid}thead{display:table-header-group}tr,img{page-break-inside:avoid}img{max-width:100% !important}@page{margin:0.5cm}p,h2,h3{orphans:3;widows:3}h1,h2,h3,h4,h5,h6{page-break-after:avoid}}</style>
<script defer src="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/10.1.1/highlight.min.js" integrity="sha256-Uv3H6lx7dJmRfRvH8TH6kJD1TSK1aFcwgx+mdg3epi8=" crossorigin></script>
<script>window.addEventListener('DOMContentLoaded', () => hljs.initHighlighting())</script>
</head>
<body>
<main>
<article id="content">
<header>
<h1 class="title">Module <code>dalpy.trees</code></h1>
</header>
<section id="section-intro">
<p>Module that holds classes and functions related to trees.</p>
<p>This module contains the <code><a title="dalpy.trees.BinaryTreeNode" href="#dalpy.trees.BinaryTreeNode">BinaryTreeNode</a></code> and <code><a title="dalpy.trees.NaryTreeNode" href="#dalpy.trees.NaryTreeNode">NaryTreeNode</a></code> classes. <code><a title="dalpy.trees.BinaryTreeNode" href="#dalpy.trees.BinaryTreeNode">BinaryTreeNode</a></code> can be used to recursively define
a binary tree. <code><a title="dalpy.trees.NaryTreeNode" href="#dalpy.trees.NaryTreeNode">NaryTreeNode</a></code> can be used to recursively define a doubly linked list. Problems or algorithms that
operate on trees should take an object of either of these classes. This module also contains the <code><a title="dalpy.trees.depth" href="#dalpy.trees.depth">depth()</a></code> function which
computes the depth of an <code><a title="dalpy.trees.NaryTreeNode" href="#dalpy.trees.NaryTreeNode">NaryTreeNode</a></code> in a tree.</p>
<h2 id="examples">Examples</h2>
<p>A binary tree can be created as follows:</p>
<pre><code>bt = BinaryTreeNode(1)
bt.left = BinaryTreeNode(2)
bt.right = BinaryTreeNode(3)
</code></pre>
<p>An n-ary tree can be created as follows, where one can also get the depth of one of the children:</p>
<pre><code>nt = NaryTreeNode(1)
c1 = NaryTreeNode(2)
c2 = NaryTreeNode(3)
c3 = NaryTreeNode(4)
c1.parent = nt
c2.parent = nt
c3.parent = nt
nt.leftmost_child = c1
c1.right_sibling = c2
c2.right_sibling = c3
x = depth(c3)
</code></pre>
</section>
<section>
</section>
<section>
</section>
<section>
<h2 class="section-title" id="header-functions">Functions</h2>
<dl>
<dt id="dalpy.trees.depth"><code class="name flex">
<span>def <span class="ident">depth</span></span>(<span>node)</span>
</code></dt>
<dd>
<div class="desc"><p>Computes the depth of a n-ary tree node.</p>
<p>The depth of a node <code>v</code> is the number of edges on the path from the root to the node. This function runs in <code>O(h)</code>
time where <code>h</code> is the height of tree the input node is contained in.</p>
<h2 id="args">Args</h2>
<dl>
<dt><strong><code>node</code></strong></dt>
<dd>an <code><a title="dalpy.trees.NaryTreeNode" href="#dalpy.trees.NaryTreeNode">NaryTreeNode</a></code>.</dd>
</dl>
<h2 id="returns">Returns</h2>
<p>The integer depth of node in the tree its contained in.</p>
<h2 id="raises">Raises</h2>
<dl>
<dt><code>TypeError</code></dt>
<dd>If <code>node</code> is not an <code><a title="dalpy.trees.NaryTreeNode" href="#dalpy.trees.NaryTreeNode">NaryTreeNode</a></code>.</dd>
</dl></div>
</dd>
</dl>
</section>
<section>
<h2 class="section-title" id="header-classes">Classes</h2>
<dl>
<dt id="dalpy.trees.BinaryTreeNode"><code class="flex name class">
<span>class <span class="ident">BinaryTreeNode</span></span>
<span>(</span><span>data=None, left=None, right=None)</span>
</code></dt>
<dd>
<div class="desc"><p>Represents a binary tree node.</p>
<h2 id="attributes">Attributes</h2>
<dl>
<dt><strong><code>data</code></strong></dt>
<dd>The data stored in the node. This can be any type.</dd>
<dt><strong><code>left</code></strong></dt>
<dd>A <code><a title="dalpy.trees.BinaryTreeNode" href="#dalpy.trees.BinaryTreeNode">BinaryTreeNode</a></code> representing the node that is to the left of this node in a tree.</dd>
<dt><strong><code>right</code></strong></dt>
<dd>A <code><a title="dalpy.trees.BinaryTreeNode" href="#dalpy.trees.BinaryTreeNode">BinaryTreeNode</a></code> representing the node that is to the right of this node in a tree.</dd>
</dl>
<p>Initializes a <code><a title="dalpy.trees.BinaryTreeNode" href="#dalpy.trees.BinaryTreeNode">BinaryTreeNode</a></code> in <code>O(1)</code> time.</p>
<h2 id="args">Args</h2>
<dl>
<dt><strong><code>data</code></strong></dt>
<dd>The data to be stored in the node. This can be of any type. By default, this is <code>None</code>.</dd>
<dt><strong><code>left</code></strong></dt>
<dd>A <code><a title="dalpy.trees.BinaryTreeNode" href="#dalpy.trees.BinaryTreeNode">BinaryTreeNode</a></code> representing the node that is to the left of this node in a tree. By default this
is <code>None</code>.</dd>
<dt><strong><code>right</code></strong></dt>
<dd>A <code><a title="dalpy.trees.BinaryTreeNode" href="#dalpy.trees.BinaryTreeNode">BinaryTreeNode</a></code> representing the node that is to the right of this node in a tree. By default this
is <code>None</code>.</dd>
</dl></div>
</dd>
<dt id="dalpy.trees.NaryTreeNode"><code class="flex name class">
<span>class <span class="ident">NaryTreeNode</span></span>
<span>(</span><span>data=None, parent=None, leftmost_child=None, right_sibling=None)</span>
</code></dt>
<dd>
<div class="desc"><p>Represents a n-ary tree node.</p>
<h2 id="attributes">Attributes</h2>
<dl>
<dt><strong><code>data</code></strong></dt>
<dd>The data stored in the node. This can be any type.</dd>
<dt><strong><code>parent</code></strong></dt>
<dd>A <code><a title="dalpy.trees.NaryTreeNode" href="#dalpy.trees.NaryTreeNode">NaryTreeNode</a></code> representing the node that is the parent of this node in a tree.</dd>
<dt><strong><code>leftmost_child</code></strong></dt>
<dd>A <code><a title="dalpy.trees.NaryTreeNode" href="#dalpy.trees.NaryTreeNode">NaryTreeNode</a></code> representing the node that is the leftmost child of this node in a tree.</dd>
<dt><strong><code>right_sibling</code></strong></dt>
<dd>A <code><a title="dalpy.trees.NaryTreeNode" href="#dalpy.trees.NaryTreeNode">NaryTreeNode</a></code> representing the node that is the right sibling of this node in a tree.</dd>
</dl>
<p>Initializes a <code><a title="dalpy.trees.NaryTreeNode" href="#dalpy.trees.NaryTreeNode">NaryTreeNode</a></code> in <code>O(1)</code> time.</p>
<h2 id="args">Args</h2>
<dl>
<dt><strong><code>data</code></strong></dt>
<dd>The data to be stored in the node. This can be of any type. By default, this is <code>None</code>.</dd>
<dt><strong><code>parent</code></strong></dt>
<dd>A <code><a title="dalpy.trees.NaryTreeNode" href="#dalpy.trees.NaryTreeNode">NaryTreeNode</a></code> representing the node that is the parent of this node in a tree. By default, this
is <code>None</code>.</dd>
<dt><strong><code>leftmost_child</code></strong></dt>
<dd>A <code><a title="dalpy.trees.NaryTreeNode" href="#dalpy.trees.NaryTreeNode">NaryTreeNode</a></code> representing the node that is the leftmost child of this node in a tree. By
default, this is <code>None</code>.</dd>
<dt><strong><code>right_sibling</code></strong></dt>
<dd>A <code><a title="dalpy.trees.NaryTreeNode" href="#dalpy.trees.NaryTreeNode">NaryTreeNode</a></code> representing the node that is the right sibling of this node in a tree. By
default, this is <code>None</code>.</dd>
</dl></div>
</dd>
</dl>
</section>
</article>
<nav id="sidebar">
<h1>Index</h1>
<div class="toc">
<ul></ul>
</div>
<ul id="index">
<li><h3>Super-module</h3>
<ul>
<li><code><a title="dalpy" href="index.html">dalpy</a></code></li>
</ul>
</li>
<li><h3><a href="#header-functions">Functions</a></h3>
<ul class="">
<li><code><a title="dalpy.trees.depth" href="#dalpy.trees.depth">depth</a></code></li>
</ul>
</li>
<li><h3><a href="#header-classes">Classes</a></h3>
<ul>
<li>
<h4><code><a title="dalpy.trees.BinaryTreeNode" href="#dalpy.trees.BinaryTreeNode">BinaryTreeNode</a></code></h4>
</li>
<li>
<h4><code><a title="dalpy.trees.NaryTreeNode" href="#dalpy.trees.NaryTreeNode">NaryTreeNode</a></code></h4>
</li>
</ul>
</li>
</ul>
</nav>
</main>
<footer id="footer">
<p>Generated by <a href="https://pdoc3.github.io/pdoc" title="pdoc: Python API documentation generator"><cite>pdoc</cite> 0.10.0</a>.</p>
</footer>
</body>
</html>