-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathbinary-tree.html
318 lines (318 loc) · 75.8 KB
/
binary-tree.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
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
<!DOCTYPE html><html lang="zh-CN"><head><meta charset="UTF-8"><meta name="viewport" content="width=device-width,initial-scale=1,maximum-scale=2"><meta name="theme-color" content="#222"><meta http-equiv="X-UA-COMPATIBLE" content="IE=edge,chrome=1"><meta name="renderer" content="webkit"><link rel="icon" type="image/ico" sizes="32x32" href="/assets/favicon.ico"><link rel="apple-touch-icon" sizes="180x180" href="/assets/apple-touch-icon.png"><link rel="alternate" href="/rss.xml" title="Jiankychen's Blog" type="application/rss+xml"><link rel="alternate" href="/atom.xml" title="Jiankychen's Blog" type="application/atom+xml"><link rel="alternate" type="application/json" title="Jiankychen's Blog" href="https://jiankychen.github.io/feed.json"><link rel="preconnect" href="https://lf9-cdn-tos.bytecdntp.com"><link rel="preconnect" href="https://at.alicdn.com"><link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Mulish:400,400italic,700,700italic%7CFredericka%20the%20Great:400,400italic,700,700italic%7CNoto%20Serif%20JP:400,400italic,700,700italic%7CNoto%20Serif%20SC:400,400italic,700,700italic%7CInconsolata:400,400italic,700,700italic&display=swap&subset=latin,latin-ext" media="none" onload="this.media='all'"><link rel="stylesheet" href="/css/app.css?v=0.4.2"><link rel="modulepreload" href="/js/chunk-7IVLRIQ3.js"><link rel="modulepreload" href="/js/chunk-IXT6LZJL.js"><link rel="modulepreload" href="/js/chunk-PHSEV26P.js"><link rel="modulepreload" href="/js/chunk-XHQGHZCW.js"><link rel="modulepreload" href="/js/comments-TUWNDU5I.js"><link rel="modulepreload" href="/js/post-P6IN2S3Y.js"><link rel="modulepreload" href="/js/quicklink-HAJEHOPK.js"><link rel="modulepreload" href="/js/search-WFXK2K66.js"><link rel="modulepreload" href="/js/siteInit.js"><link rel="stylesheet" href="https://npm.webcache.cn/@waline/[email protected]/dist/waline.css" media="none" onload="this.media='all'"><link rel="preload" href="https://img.timelessq.com/images/2022/07/26/2aabaeb8aca379b991071d1c41632741.jpg" as="image" fetchpriority="high"><link rel="preload" href="https://i.imgtg.com/2023/03/09/YS2LU.jpg" as="image" fetchpriority="high"><link rel="preload" href="https://i.imgtg.com/2023/03/09/YSj7p.jpg" as="image" fetchpriority="high"><link rel="preload" href="https://i.imgtg.com/2023/03/09/YSIlc.jpg" as="image" fetchpriority="high"><link rel="preload" href="https://img.timelessq.com/images/2022/07/26/99fb5ff897a82984470abf5e2a235d94.jpg" as="image" fetchpriority="high"><link rel="preload" href="https://img.timelessq.com/images/2022/07/26/8fe50780c15461b629c9aeab5a7f2acd.jpg" as="image" fetchpriority="high"><meta name="keywords" content="二叉树"><link rel="canonical" href="https://jiankychen.github.io/binary-tree"><title>二叉树</title><meta name="generator" content="Hexo 7.0.0"></head><body itemscope="" itemtype="http://schema.org/WebPage"><div id="loading"><div class="cat"><div class="body"></div><div class="head"><div class="face"></div></div><div class="foot"><div class="tummy-end"></div><div class="bottom"></div><div class="legs left"></div><div class="legs right"></div></div><div class="paw"><div class="hands left"></div><div class="hands right"></div></div></div></div><div id="container"><header id="header" itemscope="" itemtype="http://schema.org/WPHeader"><div class="inner"><div id="brand"><div class="pjax"><h1 itemprop="name headline">二叉树</h1><div class="meta"><span class="item" title="创建时间：2022-03-23 19:59:16"><span class="icon"><i class="ic i-calendar"></i></span><span class="text">发表于</span><time itemprop="dateCreated datePublished" datetime="2022-03-23T19:59:16+08:00">2022-03-23</time></span><span class="item" title="本文字数"><span class="icon"><i class="ic i-pen"></i></span><span class="text">本文字数</span><span>13k</span><span class="text">字</span></span><span class="item" title="阅读时长"><span class="icon"><i class="ic i-clock"></i></span><span class="text">阅读时长</span><span>12 分钟</span></span></div></div></div><nav id="nav"><div class="inner"><div class="toggle"><div class="lines" aria-label="切换导航栏"><span class="line"></span><span class="line"></span><span class="line"></span></div></div><ul class="menu"><li class="item title"><a href="/" rel="start">Jiankychen</a></li></ul><ul class="right" id="rightNav"><li class="item theme"><i class="ic i-sun"></i></li><li class="item search"><i class="ic i-search"></i></li></ul></div></nav></div><div class="pjax" id="imgs"><ul><li class="item" style="background-image: url("https://img.timelessq.com/images/2022/07/26/2aabaeb8aca379b991071d1c41632741.jpg");"></li><li class="item" style="background-image: url("https://i.imgtg.com/2023/03/09/YS2LU.jpg");"></li><li class="item" style="background-image: url("https://i.imgtg.com/2023/03/09/YSj7p.jpg");"></li><li class="item" style="background-image: url("https://i.imgtg.com/2023/03/09/YSIlc.jpg");"></li><li class="item" style="background-image: url("https://img.timelessq.com/images/2022/07/26/99fb5ff897a82984470abf5e2a235d94.jpg");"></li><li class="item" style="background-image: url("https://img.timelessq.com/images/2022/07/26/8fe50780c15461b629c9aeab5a7f2acd.jpg");"></li></ul></div></header><div id="waves"><svg class="waves" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" viewBox="0 24 150 28" preserveAspectRatio="none" shape-rendering="auto"><defs><path id="gentle-wave" d="M-160 44c30 0 58-18 88-18s 58 18 88 18 58-18 88-18 58 18 88 18 v44h-352z"></path></defs><g class="parallax"><use xlink:href="#gentle-wave" x="48" y="0"></use><use xlink:href="#gentle-wave" x="48" y="3"></use><use xlink:href="#gentle-wave" x="48" y="5"></use><use xlink:href="#gentle-wave" x="48" y="7"></use></g></svg></div><main><div class="inner"><div class="pjax" id="main"><div class="article wrap"><div class="breadcrumb" itemlistelement="" itemscope="" itemtype="https://schema.org/BreadcrumbList"><i class="ic i-home"></i><span><a href="/">首页</a></span><i class="ic i-angle-right"></i><span class="current" itemprop="itemListElement" itemscope="itemscope" itemtype="https://schema.org/ListItem"><a href="/categories/Data-Structure/" itemprop="item" rel="index" title="分类于Data Structure"><span itemprop="name">Data Structure<meta itemprop="position" content="0"></span></a></span></div><article class="post block" itemscope="itemscope" itemtype="http://schema.org/Article" lang="zh-CN"><link itemprop="mainEntityOfPage" href="https://jiankychen.github.io/binary-tree.html"><span hidden="hidden" itemprop="author" itemscope="itemscope" itemtype="http://schema.org/Person"><meta itemprop="image" content="/assets/avatar.jpg"><meta itemprop="name" content="Jiankychen"><meta itemprop="description" content="Never put off till tomorrow what you can do today, "></span><span hidden="hidden" itemprop="publisher" itemscope="itemscope" itemtype="http://schema.org/Organization"><meta itemprop="name" content="Jiankychen's Blog"></span><div class="body md" itemprop="articleBody"><p>树：用来模拟具有树状结构性质的数据集合</p>
<p>二叉树 （Binary Tree）：每个节点 最多有两个子树 的树结构，通常子树被称作 “左子树” 和 “右子树”</p>
<blockquote>
<p>注意：二叉树必须严格区分左右子树，即使只有一棵子树，也要说明它是左子树还是右子树</p>
</blockquote>
<h1 id="二叉树的种类"><a class="anchor" href="#二叉树的种类">#</a> 二叉树的种类</h1>
<h2 id="满二叉树"><a class="anchor" href="#满二叉树">#</a> 满二叉树</h2>
<p>满二叉树：一棵高度为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>k</mi></mrow><annotation encoding="application/x-tex">k</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6944em;"></span><span class="mord mathnormal" style="margin-right:0.03148em;">k</span></span></span></span> 并具有 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mn>2</mn><mi>k</mi></msup><mo>−</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">2^k - 1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.9324em;vertical-align:-0.0833em;"></span><span class="mord"><span class="mord">2</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8491em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight" style="margin-right:0.03148em;">k</span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">1</span></span></span></span> 个节点的二叉树</p>
<p><img loading="lazy" data-src="https://img-blog.csdnimg.cn/20200806185805576.png" alt=""></p>
<h2 id="完全二叉树"><a class="anchor" href="#完全二叉树">#</a> 完全二叉树</h2>
<p>完全二叉树：在满二叉树的最底层自右至左依次（注意：不能跳过任何一个节点）去掉若干个节点得到的二叉树</p>
<p><img loading="lazy" data-src="https://img-blog.csdnimg.cn/20200920221638903.png" alt="完全二叉树的示例"></p>
<p>完全二叉树的特点：</p>
<ul>
<li>所有的叶节点都出现在最低的两层上</li>
<li>对任一节点，如果其右子树的高度为 k ，则其左子树的高度为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>k</mi></mrow><annotation encoding="application/x-tex">k</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6944em;"></span><span class="mord mathnormal" style="margin-right:0.03148em;">k</span></span></span></span> 或 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>k</mi><mo>+</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">k + 1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7778em;vertical-align:-0.0833em;"></span><span class="mord mathnormal" style="margin-right:0.03148em;">k</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">1</span></span></span></span></li>
</ul>
<blockquote>
<p>满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树</p>
</blockquote>
<p>优先队列（堆）就是一棵完全二叉树，并保证了父子节点的顺序关系</p>
<h2 id="二叉搜索树"><a class="anchor" href="#二叉搜索树">#</a> 二叉搜索树</h2>
<p>二叉搜索树，也叫作 二叉树查找树 或者 二叉排序树</p>
<p>二叉搜索树的性质：</p>
<ul>
<li>若左子树不空，则左子树上所有结点的值均小于它的根结点的值</li>
<li>若右子树不空，则右子树上所有结点的值均大于它的根结点的值</li>
<li>左、右子树也分别为二叉排序树</li>
</ul>
<p>即，在二叉搜索树中，左子树都比其根节点小，右子树都比其根节点大，递归定义</p>
<p>二叉搜索树 的 <strong>中序遍历</strong> 一定是 <strong>从小到大排序</strong> 的</p>
<p><img loading="lazy" data-src="https://img-blog.csdnimg.cn/20200806190304693.png" alt="二叉搜索树"></p>
<p>二叉搜索树的搜索性能：</p>
<ul>
<li>最好情况下，二叉搜索树的查找效率比较高，是 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>log</mi><mo></mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(\log{n})</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mop">lo<span style="margin-right:0.01389em;">g</span></span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord"><span class="mord mathnormal">n</span></span><span class="mclose">)</span></span></span></span> ，其访问性能近似于二分法</li>
<li>最差情况下，例如插入的元素有序时，生成的二叉搜索树将会是一个链表，搜索的时间复杂度为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathnormal">n</span><span class="mclose">)</span></span></span></span></li>
</ul>
<h2 id="平衡二叉树"><a class="anchor" href="#平衡二叉树">#</a> 平衡二叉树</h2>
<p>平衡二叉树，又被称为 AVL（Adelson-Velsky and Landis）树，是二叉搜索树的一种实现</p>
<p>平衡二叉树要么是一棵空树，要么保证左右子树的高度差不超过 1，并且左右子树也都必须是一棵平衡二叉树</p>
<p>平衡二叉树的提出就是为了避免二叉搜索树出现极端情况</p>
<p><img loading="lazy" data-src="https://img-blog.csdnimg.cn/20200806190511967.png" alt="平衡二叉树"></p>
<p>平衡二叉树的性能：平衡二叉树在添加和删除时需要进行复杂的旋转保持整个树的平衡，最终，插入、查找的时间复杂度都是 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>log</mi><mo></mo><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(\log{n})</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mop">lo<span style="margin-right:0.01389em;">g</span></span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord"><span class="mord mathnormal">n</span></span><span class="mclose">)</span></span></span></span></p>
<p>著名的红黑树就是一种平衡二叉树</p>
<p>C++ 中， <code>map</code> 、 <code>set</code> 、 <code>multimap</code> 、 <code>multiset</code> 的底层实现都是平衡二叉树</p>
<h1 id="二叉树的遍历"><a class="anchor" href="#二叉树的遍历">#</a> 二叉树的遍历</h1>
<p>二叉树有两类遍历方式：深度优先遍历 与 广度优先遍历</p>
<h2 id="深度优先遍历"><a class="anchor" href="#深度优先遍历">#</a> 深度优先遍历</h2>
<p>深度优先遍历 可分为：前序遍历、中序遍历、后序遍历</p>
<ul>
<li>
<p><strong>前序遍历</strong> ：首先访问 / 处理根节点，然后访问 / 处理左子树，最后访问 / 处理右子树</p>
</li>
<li>
<p><strong>中序遍历</strong> ：先访问 / 处理左子树，然后处理根节点，然后访问 / 处理右子树</p>
</li>
<li>
<p><strong>后序遍历</strong> ：先访问 / 处理左子树，然后访问 / 处理右子树，最后处理树的根节点</p>
</li>
</ul>
<blockquote>
<p>严格来说，遍历时一定是先访问根节点，然后根据根节点访问左子节点、右子节点，所谓的 前序、中序、后序遍历 讲的是处理根节点（即，do something with root）的顺序。例如，对于中序遍历，根节点的处理是在处理完左子节点之后才进行的。可参考 <a target="_blank" rel="noopener" href="https://leetcode.cn/problems/binary-tree-paths/solution/tu-jie-er-cha-shu-de-suo-you-lu-jing-by-xiao_ben_z/">前、中、后序遍历的区别</a></p>
</blockquote>
<p>前、中、后序遍历只针对于根节点，而左右子节点永远都是先左后右的顺序</p>
<ul>
<li>前序：根左右</li>
<li>中序：左根右</li>
<li>后序：左右根</li>
</ul>
<p>以下图为例</p>
<p><img loading="lazy" data-src="AL-%E4%BA%8C%E5%8F%89%E6%A0%91/1.webp" alt=""></p>
<p>其遍历的结果为：</p>
<table>
<thead>
<tr>
<th style="text-align:center">遍历方式</th>
<th style="text-align:center">0</th>
<th style="text-align:center">1</th>
<th style="text-align:center">2</th>
<th style="text-align:center">3</th>
<th style="text-align:center">4</th>
<th style="text-align:center">5</th>
<th style="text-align:center">6</th>
<th style="text-align:center">7</th>
<th style="text-align:center">8</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center">前序遍历</td>
<td style="text-align:center">F</td>
<td style="text-align:center">B</td>
<td style="text-align:center">A</td>
<td style="text-align:center">D</td>
<td style="text-align:center">C</td>
<td style="text-align:center">E</td>
<td style="text-align:center">G</td>
<td style="text-align:center">I</td>
<td style="text-align:center">H</td>
</tr>
<tr>
<td style="text-align:center">中序遍历</td>
<td style="text-align:center">A</td>
<td style="text-align:center">B</td>
<td style="text-align:center">C</td>
<td style="text-align:center">D</td>
<td style="text-align:center">E</td>
<td style="text-align:center">F</td>
<td style="text-align:center">G</td>
<td style="text-align:center">H</td>
<td style="text-align:center">I</td>
</tr>
<tr>
<td style="text-align:center">后序遍历</td>
<td style="text-align:center">A</td>
<td style="text-align:center">C</td>
<td style="text-align:center">E</td>
<td style="text-align:center">D</td>
<td style="text-align:center">B</td>
<td style="text-align:center">H</td>
<td style="text-align:center">I</td>
<td style="text-align:center">G</td>
<td style="text-align:center">F</td>
</tr>
</tbody>
</table>
<p>使用：</p>
<ul>
<li>
<p>中序常用来在二叉搜索树中得到递增的有序序列</p>
</li>
<li>
<p>删除节点的过程将按照后序遍历的顺序进行</p>
</li>
<li>
<p>后序可用于数学中的后缀表示法，结合栈处理表达式，每遇到一个操作符，就可以从栈中弹出栈顶的两个元素，计算并将结果返回到栈中</p>
</li>
</ul>
<p>深度优先遍历 通常可以用 <strong>递归法</strong> 和 <strong>迭代法</strong> 实现（如果采用迭代法，则需要借助 <strong>栈</strong> 这一数据结构）</p>
<p>具体实现：</p>
<ul>
<li>LeetCode 144. 二叉树的前序遍历</li>
<li>LeetCode 94. 二叉树的中序遍历</li>
<li>LeetCode 145. 二叉树的后序遍历</li>
</ul>
<h2 id="广度优先遍历"><a class="anchor" href="#广度优先遍历">#</a> 广度优先遍历</h2>
<p>二叉树的广度优先遍历是指 层次遍历</p>
<p>即，逐层地、从左到右访问所有节点</p>
<p>上述例子的层序遍历结果为：</p>
<table>
<thead>
<tr>
<th style="text-align:center">遍历方式</th>
<th style="text-align:center">0</th>
<th style="text-align:center">1</th>
<th style="text-align:center">2</th>
<th style="text-align:center">3</th>
<th style="text-align:center">4</th>
<th style="text-align:center">5</th>
<th style="text-align:center">6</th>
<th style="text-align:center">7</th>
<th style="text-align:center">8</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center">层序遍历</td>
<td style="text-align:center">F</td>
<td style="text-align:center">B</td>
<td style="text-align:center">G</td>
<td style="text-align:center">A</td>
<td style="text-align:center">D</td>
<td style="text-align:center">I</td>
<td style="text-align:center">C</td>
<td style="text-align:center">E</td>
<td style="text-align:center">H</td>
</tr>
</tbody>
</table>
<p>广度优先遍历 一般借助 <strong>队列</strong> 这一数据结构、采用 <strong>迭代法</strong> 实现</p>
<p>具体实现：LeetCode 102. 二叉树的层序遍历</p>
<h1 id="二叉树的定义"><a class="anchor" href="#二叉树的定义">#</a> 二叉树的定义</h1>
<p>已知二叉树的前序遍历序列和中序遍历序列，可以确定一棵二叉树</p>
<ul>
<li>根据前序遍历序列找出根节点，再根据中序遍历序列区分左右子树</li>
<li>分别找出左右子树的前序、中序遍历序列</li>
<li>分别对左右子树重复这个过程</li>
</ul>
<p>例：</p>
<p>前序序列：A B D E F C<br>
中序序列：D B E F A C</p>
<p>根据前序序列确定二叉树的根节点为 A ，在中序序列中找到 A ，此时，中序序列中 A 左边的 D B E F 即为 A 的左子树，A 右边的 C 为 A 的右子树</p>
<ul>
<li>针对 A 的左子树，一共包含 D B E F 四个节点，其对应的前序遍历为 B D E F ，中序遍历为 D B E F 。因此， A 的左子树的根节点为 B ，节点 B 的左子树为 D ，右子树为 E F
<ul>
<li>针对 B 的右子树，一共包含 E F 两个节点，其前序遍历为 E F ，中序遍历为 E F
<ul>
<li>根节点为 E ，右子树为 F</li>
</ul>
</li>
</ul>
</li>
<li>针对 A 的右子树，前序遍历和中序遍历均为 C，故 C 为叶节点</li>
</ul>
<p><img loading="lazy" data-src="AL-%E4%BA%8C%E5%8F%89%E6%A0%91/2.webp" alt=""></p>
<p>已知二叉树的中序遍历序列和后序遍历序列，可以确定一棵二叉树</p>
<ul>
<li>根据后序遍历确定根节点，根据中序遍历确定其左右子树</li>
</ul>
<p>已知二叉树的前序遍历序列和后序遍历序列，无法唯一确定一棵二叉树</p>
<ul>
<li>可以根据前序遍历序列确定根节点，但无法分清其左子树和右子树</li>
</ul>
<h1 id="二叉树的性质"><a class="anchor" href="#二叉树的性质">#</a> 二叉树的性质</h1>
<ol>
<li>
<p>一棵非空二叉树的第 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6595em;"></span><span class="mord mathnormal">i</span></span></span></span> 层上最多有 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mn>2</mn><mrow><mi>i</mi><mo>−</mo><mn>1</mn></mrow></msup></mrow><annotation encoding="application/x-tex">2^{i - 1}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8247em;"></span><span class="mord"><span class="mord">2</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8247em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathnormal mtight">i</span><span class="mbin mtight">−</span><span class="mord mtight">1</span></span></span></span></span></span></span></span></span></span></span></span> 个节点 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">(</mo><mi>i</mi><mo>≥</mo><mn>1</mn><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">(i \ge 1)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">(</span><span class="mord mathnormal">i</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">≥</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord">1</span><span class="mclose">)</span></span></span></span></p>
</li>
<li>
<p>一棵高度为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>k</mi></mrow><annotation encoding="application/x-tex">k</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6944em;"></span><span class="mord mathnormal" style="margin-right:0.03148em;">k</span></span></span></span> 的二叉树，最多具有 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mn>2</mn><mi>k</mi></msup><mo>−</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">2^k - 1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.9324em;vertical-align:-0.0833em;"></span><span class="mord"><span class="mord">2</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8491em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight" style="margin-right:0.03148em;">k</span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">1</span></span></span></span> 个节点</p>
</li>
<li>
<p>一棵非空二叉树，如果叶节点数为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mi>n</mi><mn>0</mn></msub></mrow><annotation encoding="application/x-tex">n_0</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.5806em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathnormal">n</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3011em;"><span style="top:-2.55em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">0</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span> ，度数为 2 的节点数为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mi>n</mi><mn>2</mn></msub></mrow><annotation encoding="application/x-tex">n_2</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.5806em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathnormal">n</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3011em;"><span style="top:-2.55em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span> ，则有 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mi>n</mi><mn>0</mn></msub><mo>=</mo><msub><mi>n</mi><mn>2</mn></msub><mo>+</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">n_0 = n_2 + 1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.5806em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathnormal">n</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3011em;"><span style="top:-2.55em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">0</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.7333em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathnormal">n</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3011em;"><span style="top:-2.55em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">1</span></span></span></span> 成立</p>
<ul>
<li>二叉树所有节点的度数均小于或等于 2，所以有 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi><mo>=</mo><msub><mi>n</mi><mn>0</mn></msub><mo>+</mo><msub><mi>n</mi><mn>1</mn></msub><mo>+</mo><msub><mi>n</mi><mn>2</mn></msub></mrow><annotation encoding="application/x-tex">n = n_0 + n_1 + n_2</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.7333em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathnormal">n</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3011em;"><span style="top:-2.55em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">0</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:0.7333em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathnormal">n</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3011em;"><span style="top:-2.55em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">1</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:0.5806em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathnormal">n</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3011em;"><span style="top:-2.55em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span></li>
<li>除根节点外，每个节点都有唯一的一个树枝（父节点与子节点之间的线段）进入本节点，则二叉树的树枝总数 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>B</mi><mo>=</mo><mi>n</mi><mo>−</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">B = n - 1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6833em;"></span><span class="mord mathnormal" style="margin-right:0.05017em;">B</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6667em;vertical-align:-0.0833em;"></span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">1</span></span></span></span></li>
<li>度为 1 的节点发出一个树枝，度为 2 的节点发出两个树枝，所以 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>B</mi><mo>=</mo><msub><mi>n</mi><mn>1</mn></msub><mo>+</mo><mn>2</mn><msub><mi>n</mi><mn>2</mn></msub></mrow><annotation encoding="application/x-tex">B = n_1 + 2 n_2</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6833em;"></span><span class="mord mathnormal" style="margin-right:0.05017em;">B</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.7333em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathnormal">n</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3011em;"><span style="top:-2.55em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">1</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:0.7944em;vertical-align:-0.15em;"></span><span class="mord">2</span><span class="mord"><span class="mord mathnormal">n</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3011em;"><span style="top:-2.55em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span></li>
<li>联立以上三式，得 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mi>n</mi><mn>0</mn></msub><mo>=</mo><msub><mi>n</mi><mn>2</mn></msub><mo>+</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">n_0 = n_2 + 1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.5806em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathnormal">n</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3011em;"><span style="top:-2.55em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">0</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.7333em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathnormal">n</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3011em;"><span style="top:-2.55em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">1</span></span></span></span></li>
</ul>
</li>
<li>
<p>具有 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">n</span></span></span></span> 个节点的完全二叉树的高度 $ k = \lfloor \log_2 {n} \rfloor + 1$</p>
<ul>
<li>高度为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>k</mi></mrow><annotation encoding="application/x-tex">k</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6944em;"></span><span class="mord mathnormal" style="margin-right:0.03148em;">k</span></span></span></span> 的完全二叉树，其节点总数满足 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msup><mn>2</mn><mrow><mi>k</mi><mo>−</mo><mn>1</mn></mrow></msup><mo>−</mo><mn>1</mn><mo><</mo><mi>n</mi><mo>≤</mo><msup><mn>2</mn><mi>k</mi></msup><mo>−</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">2^{k-1} - 1 < n \le 2^k - 1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.9324em;vertical-align:-0.0833em;"></span><span class="mord"><span class="mord">2</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8491em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathnormal mtight" style="margin-right:0.03148em;">k</span><span class="mbin mtight">−</span><span class="mord mtight">1</span></span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:0.6835em;vertical-align:-0.0391em;"></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel"><</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.7719em;vertical-align:-0.136em;"></span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.9324em;vertical-align:-0.0833em;"></span><span class="mord"><span class="mord">2</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8491em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight" style="margin-right:0.03148em;">k</span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">1</span></span></span></span> ，化简得 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>k</mi><mo>−</mo><mn>1</mn><mo>≤</mo><msub><mrow><mi>log</mi><mo></mo></mrow><mn>2</mn></msub><mi>n</mi><mo><</mo><mi>k</mi></mrow><annotation encoding="application/x-tex">k - 1 \le \log_2{n} < k</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7778em;vertical-align:-0.0833em;"></span><span class="mord mathnormal" style="margin-right:0.03148em;">k</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:0.7804em;vertical-align:-0.136em;"></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">≤</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.9386em;vertical-align:-0.2441em;"></span><span class="mop"><span class="mop">lo<span style="margin-right:0.01389em;">g</span></span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.207em;"><span style="top:-2.4559em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.2441em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord"><span class="mord mathnormal">n</span></span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel"><</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6944em;"></span><span class="mord mathnormal" style="margin-right:0.03148em;">k</span></span></span></span> ，由于 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>k</mi></mrow><annotation encoding="application/x-tex">k</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6944em;"></span><span class="mord mathnormal" style="margin-right:0.03148em;">k</span></span></span></span> 是整数，所以有 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>k</mi><mo>=</mo><mo stretchy="false">⌊</mo><msub><mrow><mi>log</mi><mo></mo></mrow><mn>2</mn></msub><mi>n</mi><mo stretchy="false">⌋</mo><mo>+</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">k = \lfloor \log_2{n} \rfloor + 1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6944em;"></span><span class="mord mathnormal" style="margin-right:0.03148em;">k</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">⌊</span><span class="mop"><span class="mop">lo<span style="margin-right:0.01389em;">g</span></span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.207em;"><span style="top:-2.4559em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.2441em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord"><span class="mord mathnormal">n</span></span><span class="mclose">⌋</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">1</span></span></span></span></li>
</ul>
</li>
<li>
<p><strong>完全二叉树的按层编号</strong>：对一棵有 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">n</span></span></span></span> 个节点的完全二叉树中的节点按层自上而下（从第 1 层到第 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">⌊</mo><msub><mrow><mi>log</mi><mo></mo></mrow><mn>2</mn></msub><mi>n</mi><mo stretchy="false">⌋</mo><mo>+</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">\lfloor \log_2{n} \rfloor + 1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">⌊</span><span class="mop"><span class="mop">lo<span style="margin-right:0.01389em;">g</span></span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.207em;"><span style="top:-2.4559em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist" style="height:0.2441em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord"><span class="mord mathnormal">n</span></span><span class="mclose">⌋</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">1</span></span></span></span> 层）、每一层层按自左至右依次编号，若设根节点的编号为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>1</mn></mrow><annotation encoding="application/x-tex">1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">1</span></span></span></span> ，则对任一编号为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6595em;"></span><span class="mord mathnormal">i</span></span></span></span> 的节点，有：</p>
<ul>
<li>若 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">i = 1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6595em;"></span><span class="mord mathnormal">i</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">1</span></span></span></span> ，则节点为二叉树的根节点；若 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>i</mi><mo>></mo><mn>1</mn></mrow><annotation encoding="application/x-tex">i > 1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6986em;vertical-align:-0.0391em;"></span><span class="mord mathnormal">i</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">></span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">1</span></span></span></span> ，则其父节点的编号为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">⌊</mo><mi>i</mi><mi mathvariant="normal">/</mi><mn>2</mn><mo stretchy="false">⌋</mo></mrow><annotation encoding="application/x-tex">\lfloor i/2 \rfloor</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">⌊</span><span class="mord mathnormal">i</span><span class="mord">/2</span><span class="mclose">⌋</span></span></span></span></li>
<li>若 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>2</mn><mi>i</mi><mo>></mo><mi>n</mi></mrow><annotation encoding="application/x-tex">2 i > n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6986em;vertical-align:-0.0391em;"></span><span class="mord">2</span><span class="mord mathnormal">i</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">></span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">n</span></span></span></span>，则编号为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6595em;"></span><span class="mord mathnormal">i</span></span></span></span> 的节点为叶节点，没有子节点；否则，其左子节点编号为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>2</mn><mi>i</mi></mrow><annotation encoding="application/x-tex">2 i</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6595em;"></span><span class="mord">2</span><span class="mord mathnormal">i</span></span></span></span></li>
<li>若 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>2</mn><mi>i</mi><mo>+</mo><mn>1</mn><mo>></mo><mi>n</mi></mrow><annotation encoding="application/x-tex">2 i + 1 > n</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7429em;vertical-align:-0.0833em;"></span><span class="mord">2</span><span class="mord mathnormal">i</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:0.6835em;vertical-align:-0.0391em;"></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">></span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">n</span></span></span></span>，则编号为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6595em;"></span><span class="mord mathnormal">i</span></span></span></span> 的节点无右子节点；否则，其右子节点编号为 <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mn>2</mn><mi>i</mi><mo>+</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">2 i + 1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7429em;vertical-align:-0.0833em;"></span><span class="mord">2</span><span class="mord mathnormal">i</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">1</span></span></span></span></li>
</ul>
</li>
</ol>
<h1 id="二叉树的存储"><a class="anchor" href="#二叉树的存储">#</a> 二叉树的存储</h1>
<h2 id="顺序存储"><a class="anchor" href="#顺序存储">#</a> 顺序存储</h2>
<h3 id="完全二叉树的顺序存储"><a class="anchor" href="#完全二叉树的顺序存储">#</a> 完全二叉树的顺序存储</h3>
<p>按层编号，把节点的层次关系映射到线性关系</p>
<p>并且，根据 完全二叉树的按层编号 性质，可以得知各节点的父节点和子节点</p>
<p>例如：</p>
<p><img loading="lazy" data-src="AL-%E4%BA%8C%E5%8F%89%E6%A0%91/3.webp" alt="完全二叉树的顺序存储"></p>
<h3 id="非完全二叉树的顺序存储"><a class="anchor" href="#非完全二叉树的顺序存储">#</a> 非完全二叉树的顺序存储</h3>
<p>将非完全二叉树修补成完全二叉树</p>
<ul>
<li>用特殊标记 （对应于类定义中的 <code>flag</code> ）表示虚拟节点</li>
</ul>
<p>然后按层编号</p>
<p>例如：</p>
<p><img loading="lazy" data-src="AL-%E4%BA%8C%E5%8F%89%E6%A0%91/4.webp" alt="非完全二叉树的顺序存储"></p>
<p>非完全二叉树顺序存储的特点：浪费空间（极端情况：只有右子节点的高为 3 的二叉树，其需要 7 个节点的存储空间，但是有效的节点只有 3 个）</p>
<p>一般只用于一些特殊的场合，如静态的并且节点个数已知的完全二叉树或接近完全二叉树的二叉树</p>
<h2 id="链接存储"><a class="anchor" href="#链接存储">#</a> 链接存储</h2>
<h3 id="二叉链表"><a class="anchor" href="#二叉链表">#</a> 二叉链表</h3>
<p>指明子节点，类似于单链表</p>
<p>每个节点存储 数据元素、指向左子节点的指针、指向右子节点的指针</p>
<p>例如：</p>
<p><img loading="lazy" data-src="AL-%E4%BA%8C%E5%8F%89%E6%A0%91/5.webp" alt="二叉链表"></p>
<h3 id="三叉链表"><a class="anchor" href="#三叉链表">#</a> 三叉链表：</h3>
<p>同时指明父节点和子节点，类似于双链表</p>
<p>每个节点存储 数据元素、指向左子节点的指针、指向右子节点的指针、指向父节点的指针</p>
<p><img loading="lazy" data-src="AL-%E4%BA%8C%E5%8F%89%E6%A0%91/6.webp" alt="三叉链表"></p>
<p>由于在二叉树中很少通过子节点找父节点，因此，我们<strong>常使用二叉链表进行存储</strong>，二叉链表也被称作二叉树的标准存储方式</p>
<h1 id="二叉树节点的定义"><a class="anchor" href="#二叉树节点的定义">#</a> 二叉树节点的定义</h1>
<p>使用二叉链表来定义二叉树</p>
<figure class="highlight cpp"><figcaption data-lang="C++"></figcaption><table><tbody><tr><td data-num="1"></td><td><pre><span class="token keyword">struct</span> <span class="token class-name">TreeNode</span> <span class="token punctuation">{</span></pre></td></tr><tr><td data-num="2"></td><td><pre> <span class="token keyword">int</span> val<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="3"></td><td><pre> TreeNode <span class="token operator">*</span>left<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="4"></td><td><pre> TreeNode <span class="token operator">*</span>right<span class="token punctuation">;</span></pre></td></tr><tr><td data-num="5"></td><td><pre> <span class="token function">TreeNode</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">:</span> <span class="token function">val</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">,</span> <span class="token function">left</span><span class="token punctuation">(</span><span class="token keyword">nullptr</span><span class="token punctuation">)</span><span class="token punctuation">,</span> <span class="token function">right</span><span class="token punctuation">(</span><span class="token keyword">nullptr</span><span class="token punctuation">)</span> <span class="token punctuation">{</span><span class="token punctuation">}</span></pre></td></tr><tr><td data-num="6"></td><td><pre> <span class="token function">TreeNode</span><span class="token punctuation">(</span><span class="token keyword">int</span> x<span class="token punctuation">)</span> <span class="token operator">:</span> <span class="token function">val</span><span class="token punctuation">(</span>x<span class="token punctuation">)</span><span class="token punctuation">,</span> <span class="token function">left</span><span class="token punctuation">(</span><span class="token keyword">nullptr</span><span class="token punctuation">)</span><span class="token punctuation">,</span> <span class="token function">right</span><span class="token punctuation">(</span><span class="token keyword">nullptr</span><span class="token punctuation">)</span> <span class="token punctuation">{</span><span class="token punctuation">}</span></pre></td></tr><tr><td data-num="7"></td><td><pre> <span class="token function">TreeNode</span><span class="token punctuation">(</span><span class="token keyword">int</span> x<span class="token punctuation">,</span> TreeNode <span class="token operator">*</span>left<span class="token punctuation">,</span> TreeNode <span class="token operator">*</span>right<span class="token punctuation">)</span> <span class="token operator">:</span> <span class="token function">val</span><span class="token punctuation">(</span>x<span class="token punctuation">)</span><span class="token punctuation">,</span> <span class="token function">left</span><span class="token punctuation">(</span>left<span class="token punctuation">)</span><span class="token punctuation">,</span> <span class="token function">right</span><span class="token punctuation">(</span>right<span class="token punctuation">)</span> <span class="token punctuation">{</span><span class="token punctuation">}</span></pre></td></tr><tr><td data-num="8"></td><td><pre><span class="token punctuation">}</span><span class="token punctuation">;</span></pre></td></tr></tbody></table></figure><p>注意，在 Leetcode 中，数据结构都是定义了的，而在笔试 / 面试时可能需要自行定义数据结构，例如，链表、二叉树等</p>
<p>因此，一定要掌握数据结构的定义</p>
<p>参考：</p>
<ul>
<li><a target="_blank" rel="noopener" href="https://www.boyuai.com/learn/courses/152/lessons/2363/steps/0?from=qz">青州智学</a></li>
<li><a target="_blank" rel="noopener" href="https://www.programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html">代码随想录</a></li>
<li><a target="_blank" rel="noopener" href="https://leetcode.cn/leetbook/read/illustration-of-algorithm/50e446/">图解算法数据结构</a></li>
</ul>
<div class="tags"><a href="/tags/%E4%BA%8C%E5%8F%89%E6%A0%91/" rel="tag"><i class="ic i-tag"></i>二叉树</a></div></div><footer><div class="meta"><span class="item"><span class="icon"><i class="ic i-calendar-check"></i></span><span class="text">更新于</span><time title="修改时间：2024-06-08 16:40:56" itemprop="dateModified" datetime="2024-06-08T16:40:56+08:00">2024-06-08</time></span></div><div id="copyright"><ul><li class="author"><strong>本文作者：</strong>Jiankychen<i class="ic i-at"><em>@</em></i>Jiankychen's Blog</li><li class="link"><strong>本文链接：</strong><a href="https://jiankychen.github.io/binary-tree.html" title="二叉树">https://jiankychen.github.io/binary-tree.html</a></li><li class="license"><strong>版权声明：</strong>本站所有文章除特别声明外，均采用 <a target="_blank" rel="noopener" href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh"><i class="ic i-creative-commons"><em>(CC)</em></i>BY-NC-SA</a> 许可协议。转载请注明出处！</li></ul></div></footer></article></div><div class="post-nav"><div class="item left"><a href="/cpp-experssions.html" rel="prev" itemprop="url" data-background-image="https://img.timelessq.com/images/2022/07/26/9b626c5ba21d7cb4dbcba2b507688bbb.jpg" title="C++ 表达式"><span class="type">上一篇</span><span class="category"><i class="ic i-flag"></i>C++</span><h3>C++ 表达式</h3></a></div><div class="item right"><a href="/algorithm-complexity.html" rel="next" itemprop="url" data-background-image="https://img.timelessq.com/images/2022/07/26/8fe50780c15461b629c9aeab5a7f2acd.jpg" title="算法复杂度"><span class="type">下一篇</span><span class="category"><i class="ic i-flag"></i>Data Structure</span><h3>算法复杂度</h3></a></div></div><div class="wrap" id="comments"></div></div><div id="sidebar"><div class="inner"><div class="panels"><div class="inner"><div class="contents panel pjax" data-title="文章目录"><ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E7%A7%8D%E7%B1%BB"><span class="toc-number">1.</span> <span class="toc-text"> 二叉树的种类</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%BB%A1%E4%BA%8C%E5%8F%89%E6%A0%91"><span class="toc-number">1.1.</span> <span class="toc-text"> 满二叉树</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91"><span class="toc-number">1.2.</span> <span class="toc-text"> 完全二叉树</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91"><span class="toc-number">1.3.</span> <span class="toc-text"> 二叉搜索树</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91"><span class="toc-number">1.4.</span> <span class="toc-text"> 平衡二叉树</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%81%8D%E5%8E%86"><span class="toc-number">2.</span> <span class="toc-text"> 二叉树的遍历</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E9%81%8D%E5%8E%86"><span class="toc-number">2.1.</span> <span class="toc-text"> 深度优先遍历</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E9%81%8D%E5%8E%86"><span class="toc-number">2.2.</span> <span class="toc-text"> 广度优先遍历</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%AE%9A%E4%B9%89"><span class="toc-number">3.</span> <span class="toc-text"> 二叉树的定义</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%80%A7%E8%B4%A8"><span class="toc-number">4.</span> <span class="toc-text"> 二叉树的性质</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%AD%98%E5%82%A8"><span class="toc-number">5.</span> <span class="toc-text"> 二叉树的存储</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E9%A1%BA%E5%BA%8F%E5%AD%98%E5%82%A8"><span class="toc-number">5.1.</span> <span class="toc-text"> 顺序存储</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%A1%BA%E5%BA%8F%E5%AD%98%E5%82%A8"><span class="toc-number">5.1.1.</span> <span class="toc-text"> 完全二叉树的顺序存储</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E9%9D%9E%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%A1%BA%E5%BA%8F%E5%AD%98%E5%82%A8"><span class="toc-number">5.1.2.</span> <span class="toc-text"> 非完全二叉树的顺序存储</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E9%93%BE%E6%8E%A5%E5%AD%98%E5%82%A8"><span class="toc-number">5.2.</span> <span class="toc-text"> 链接存储</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%BA%8C%E5%8F%89%E9%93%BE%E8%A1%A8"><span class="toc-number">5.2.1.</span> <span class="toc-text"> 二叉链表</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%B8%89%E5%8F%89%E9%93%BE%E8%A1%A8"><span class="toc-number">5.2.2.</span> <span class="toc-text"> 三叉链表：</span></a></li></ol></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E4%BA%8C%E5%8F%89%E6%A0%91%E8%8A%82%E7%82%B9%E7%9A%84%E5%AE%9A%E4%B9%89"><span class="toc-number">6.</span> <span class="toc-text"> 二叉树节点的定义</span></a></li></ol></div><div class="related panel pjax" data-title="系列文章"><ul><li><a href="/binary-search.html" rel="bookmark" title="二分查找">二分查找</a></li><li class="active"><a href="/binary-tree.html" rel="bookmark" title="二叉树">二叉树</a></li><li><a href="/algorithm-complexity.html" rel="bookmark" title="算法复杂度">算法复杂度</a></li><li><a href="/date-structure.html" rel="bookmark" title="数据结构简介">数据结构简介</a></li><li><a href="/sort-algorithm.html" rel="bookmark" title="排序">排序</a></li><li><a href="/recursive.html" rel="bookmark" title="递推与递归">递推与递归</a></li><li><a href="/dynamic-programming.html" rel="bookmark" title="动态规划">动态规划</a></li><li><a href="/priority-queue.html" rel="bookmark" title="优先级队列">优先级队列</a></li><li><a href="/hash-table.html" rel="bookmark" title="哈希表">哈希表</a></li><li><a href="/graphics-theory.html" rel="bookmark" title="图">图</a></li><li><a href="/KMP.html" rel="bookmark" title="KMP 算法">KMP 算法</a></li><li><a href="/traverse.html" rel="bookmark" title="回溯">回溯</a></li><li><a href="/Dijkstra.html" rel="bookmark" title="Dijkstra">Dijkstra</a></li></ul></div><div class="overview panel" data-title="站点概览"><div class="author" itemprop="author" itemscope="itemscope" itemtype="http://schema.org/Person"><img class="image" loading="lazy" decoding="async" itemprop="image" alt="Jiankychen" src="/assets/avatar.webp"><p class="name" itemprop="name">Jiankychen</p><div class="description" itemprop="description"></div></div><nav class="state"><div class="item posts"><a href="/archives/"><span class="count">51</span><span class="name">文章</span></a></div><div class="item categories"><a href="/categories/"><span class="count">8</span><span class="name">分类</span></a></div><div class="item tags"><a href="/tags/"><span class="count">20</span><span class="name">标签</span></a></div></nav><div class="social"><a target="_blank" rel="noopener" href="https://github.com/jiankychen" class="item github" title="https://github.com/jiankychen"><i class="ic i-github"></i></a><a href="mailto:[email protected]" class="item email" title="mailto:[email protected]"><i class="ic i-envelope"></i></a><a target="_blank" rel="noopener" href="https://music.163.com/#/user/home?id=447771275" class="item music" title="https://music.163.com/#/user/home?id=447771275"><i class="ic i-cloud-music"></i></a><a target="_blank" rel="noopener" href="https://www.zhihu.com/people/jiankychen" class="item zhihu" title="https://www.zhihu.com/people/jiankychen"><i class="ic i-zhihu"></i></a></div><div class="menu"><li class="item"><a href="/" rel="section"><i class="ic i-home"></i>首页</a></li><li class="item dropdown"><a href="#" onclick="return false;"><i class="ic i-feather"></i>文章</a><ul class="submenu"><li class="item"><a href="/archives/" rel="section"><i class="ic i-list-alt"></i>归档</a></li><li class="item"><a href="/categories/" rel="section"><i class="ic i-th"></i>分类</a></li><li class="item"><a href="/tags/" rel="section"><i class="ic i-tags"></i>标签</a></li></ul></li><li class="item dropdown"><a href="#" onclick="return false;"><i class="ic i-feather"></i>链接</a><ul class="submenu"><li class="item"><a href="/peers/" rel="section"><i class="ic i-magic"></i>链环</a></li><li class="item"><a href="/friends/" rel="section"><i class="ic i-heart"></i>友链</a></li></ul></li><li class="item dropdown"><a href="#" onclick="return false;"><i class="ic i-stars"></i>关于</a><ul class="submenu"><li class="item"><a href="/owner/" rel="section"><i class="ic i-user"></i>关于博主</a></li><li class="item"><a href="/site/" rel="section"><i class="ic i-paw"></i>关于本站</a></li><li class="item"><a href="/update/" rel="section"><i class="ic i-cloud"></i>更新日志</a></li></ul></li></div></div></div></div><ul id="quick"><li class="prev pjax"><a href="/algorithm-complexity.html" rel="prev" title="上一篇"><i class="ic i-chevron-left"></i></a></li><li class="up"><i class="ic i-arrow-up"></i></li><li class="down"><i class="ic i-arrow-down"></i></li><li class="next pjax"><a href="/cpp-experssions.html" rel="next" title="下一篇"><i class="ic i-chevron-right"></i></a></li><li class="percent"></li></ul></div></div><div class="dimmer"></div></div></main><footer id="footer"><div class="inner"><div class="widgets"><div class="rpost pjax"><h2>随机文章</h2><ul><li class="item"><div class="breadcrumb"><a href="/categories/Data-Structure/" title="分类于Data Structure">Data Structure</a></div><span><a href="/graphics-theory.html">图</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Coding/" title="分类于Coding">Coding</a></div><span><a href="/leetcode-search.html">LeetCode - 搜索专题</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Coding/" title="分类于Coding">Coding</a></div><span><a href="/leetcode-vectors.html">LeetCode - 数组专题</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Coding/" title="分类于Coding">Coding</a></div><span><a href="/leetcode-binarytree.html">LeetCode - 二叉树专题</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Python/" title="分类于Python">Python</a></div><span><a href="/python-oop.html">Python 面向对象</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Data-Structure/" title="分类于Data Structure">Data Structure</a></div><span><a href="/recursive.html">递推与递归</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Python/" title="分类于Python">Python</a></div><span><a href="/python-modules.html">Python 异常、模块、包</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Coding/" title="分类于Coding">Coding</a></div><span><a href="/leetcode-string.html">LeetCode - 字符串专题</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/C/" title="分类于C++">C++</a></div><span><a href="/cpp-experssions.html">C++ 表达式</a></span></li><li class="item"><div class="breadcrumb"><a href="/categories/Coding/" title="分类于Coding">Coding</a></div><span><a href="/leetcode-input&output.html">常见输入输出</a></span></li></ul></div><div class="rpost pjax"><h2>最新评论</h2><ul class="leancloud-recent-comment" id="new-comment"></ul></div></div><div class="status"><div class="copyright">© 2021 -<span itemprop="copyrightYear">2024</span><span class="with-love"><i class="ic i-sakura rotate"></i></span><span class="author" itemprop="copyrightHolder">Jiankychen @ Jiankychen</span></div><div class="count"><span class="post-meta-item-icon"><i class="ic i-chart-area"></i></span><span title="站点总字数">955k 字</span><span class="post-meta-divider"> | </span><span class="post-meta-item-icon"><i class="ic i-coffee"></i></span><span title="站点阅读时长">14:28</span></div><div class="powered-by">基于 <a target="_blank" rel="noopener" href="https://hexo.io/">Hexo</a> & Theme.<a target="_blank" rel="noopener" href="https://github.com/theme-shoka-x/hexo-theme-shokaX/">ShokaX</a></div></div><script src="https://unpkg.com/[email protected]/bsz.pure.mini.js"></script><div id="busuanzi-wrap"><span class="ic i-eye"></span><span id="busuanzi_container_site_pv">本站总访问量 <span id="busuanzi_value_site_pv"></span> 次</span> | <span class="ic i-user"></span><span id="busuanzi_container_site_uv">本站总访客量 <span id="busuanzi_value_site_uv"></span> 次</span></div></div></footer></div><script data-config="" type="text/javascript">var LOCAL = {
ispost: true,
path: `/binary-tree`,
favicon: {
show: `Jiankychen`,
hide: `Jiankychen`
},
search: {
placeholder: "文章搜索",
empty: "关于 「 ${query} 」，什么也没搜到",
stats: "${time} ms 内找到 ${hits} 条结果"
},
copy_tex: true,
katex: true,
mermaid: false,
audio: undefined,
fancybox: true,
nocopy: false,
outime: true,
template: `<div class="note warning"><p><span class="label warning">文章时效性提示</span><br>这是一篇发布于 {{publish}} 天前，最后一次更新在 {{updated}} 天前的文章，部分信息可能已经发生改变，请注意甄别。</p></div>`,
quiz: {
choice: `单选题`,
multiple: `多选题`,
true_false: `判断题`,
essay: `问答题`,
gap_fill: `填空题`,
mistake: `错题备注`
},
ignores: [
(uri) => uri.includes('#'),
(uri) => new RegExp(LOCAL.path + '$').test(uri),
[]
]
};
</script><script src="https://lf9-cdn-tos.bytecdntp.com/cdn/expire-6-M/pace/1.2.4/pace.min.js" async=""></script><script src="https://polyfill.io/v3/polyfill.min.js?features=default,fetch" defer=""></script><script src="/js/siteInit.js?v=0.4.2" type="module" fetchpriority="high" defer=""></script></body></html>