0.前言
一直以來(lái)都在做Android開(kāi)發(fā)，感覺(jué)算法這些都不是很好规阀，所以準(zhǔn)備從基本的數(shù)據(jù)結(jié)構(gòu)開(kāi)始學(xué)習(xí)魔熏，也相當(dāng)于自己的學(xué)習(xí)筆記吧衷咽。
1.什么是二叉樹(shù)
二叉樹(shù)是樹(shù)的一種，每個(gè)節(jié)點(diǎn)最多可具有兩個(gè)子樹(shù)蒜绽，即結(jié)點(diǎn)的度最大為2（結(jié)點(diǎn)度：結(jié)點(diǎn)擁有的子樹(shù)數(shù)）镶骗。
例：
2.二叉樹(shù)的種類
2.1 斜樹(shù)
所有結(jié)點(diǎn)都只有左子樹(shù)，或者右子樹(shù)躲雅。
2.2 滿二叉樹(shù)
所有的分支節(jié)點(diǎn)都具有左右節(jié)點(diǎn)鼎姊。
2.3 完全二叉樹(shù)
若設(shè)二叉樹(shù)的深度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)相寇，第 h 層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊慰于，這就是完全二叉樹(shù)。
3.二叉樹(shù)的一些性質(zhì)
- 二叉樹(shù)第i層上的結(jié)點(diǎn)數(shù)目最多為 2^(i-1) (i≥1)
- 深度為h的二叉樹(shù)至多有2^h-1個(gè)結(jié)點(diǎn)(h≥1)
- 包含n個(gè)結(jié)點(diǎn)的二叉樹(shù)的高度至少為log2 (n+1)
- 在任意一棵二叉樹(shù)中唤衫，若終端結(jié)點(diǎn)的個(gè)數(shù)為n0婆赠，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1
4.二叉樹(shù)的遍歷方式
二叉樹(shù)的遍歷方式佳励，一般分為前序遍歷休里，中序遍歷，后續(xù)遍歷赃承，層次遍歷妙黍。
前、中瞧剖、后序遍歷是針對(duì)中間（父親）節(jié)點(diǎn)來(lái)說(shuō)的拭嫁，如前序遍歷，即先遍歷中間（父親）節(jié)點(diǎn)筒繁；中序遍歷噩凹，就是第二個(gè)遍歷中間（父親）節(jié)點(diǎn)。這么說(shuō)也許還是有點(diǎn)抽象毡咏，下面就舉個(gè)栗子吧驮宴。
- 前序遍歷(中-左-右):1-2-4-8-9-5-10-3-6-7
- 中序遍歷:(左-中-右):8-4-9-2-10-5-1-6-3-7
- 后序遍歷(左-右-中):8-9-4-10-5-2-6-7-3-1
層次遍歷就更簡(jiǎn)單了，也就是逐層遍歷呕缭，接著上面例圖堵泽，它的層次遍歷結(jié)果為:1-2-3-4-5-6-7-8-9-10。值得一提的是恢总，二叉樹(shù)的層次遍歷其實(shí)是利用了隊(duì)列這個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)的迎罗。
光談理論總覺(jué)得差點(diǎn)什么，讓人提不起興趣片仿。接下來(lái)就看看各個(gè)遍歷方法如何用代碼實(shí)現(xiàn)吧纹安。正好最近在python，所以以下代碼均為python實(shí)現(xiàn)砂豌。
不過(guò)在此之前厢岂，我們還是看看如何來(lái)創(chuàng)建一棵二叉樹(shù)吧.
4.1 二叉樹(shù)的創(chuàng)建
class node:
def __init__(self, k=None, l=None, r=None) -> None:
super().__init__()
self.key = k
self.left = l
self.right = r
# 生成二叉樹(shù)
def createBinaryTree():
key = input("enter a value(# is the end of a leaf):")
if key is "#":
root = None
else:
root = node(key, createBinaryTree(), createBinaryTree())
return root
首先定義了一個(gè)node類，只有三個(gè)屬性阳距，key表示鍵值塔粒，left表示左孩子，right表示右孩子筐摘，當(dāng)然也可以加上父親節(jié)點(diǎn),不過(guò)這里還用不到父親節(jié)點(diǎn)卒茬，所以就不用加上了船老。
接著寫(xiě)了一個(gè)createBinaryTree的方法，鍵入key的值圃酵，如果key的值為'#'柳畔，則代表一個(gè)左節(jié)點(diǎn)（右節(jié)點(diǎn)）的結(jié)束。如果不是'#'辜昵，那么就創(chuàng)建一個(gè)新的節(jié)點(diǎn)荸镊，利用遞歸思想繼續(xù)創(chuàng)建。
還是老規(guī)矩堪置，舉個(gè)栗子，如果我們要?jiǎng)?chuàng)建以下這個(gè)二叉樹(shù)张惹，如果鍵入呢?
答案是:A-B-D-#-#-#-C-#-#舀锨。怎么樣，是不是很簡(jiǎn)單呢宛逗。
好了知道如何創(chuàng)建一個(gè)二叉樹(shù)坎匿，就該正式講解如何遍歷二叉樹(shù)了。
4.2前序遍歷
# 前序遍歷
def pre_order(node):
if node is None:
return None
else:
print(node.key)
pre_order(node.left)
pre_order(node.right)
代碼依然很簡(jiǎn)單雷激，主要還是利用了遞歸的思想替蔬，拿上圖來(lái)分析，A節(jié)點(diǎn)被傳入屎暇，首先判斷A是不是None承桥，顯然不是，所以我們打印A節(jié)點(diǎn)的鍵值根悼，接著將A的左孩子傳入凶异，同樣的B不是None，所以我們打印B挤巡，又將B的左孩子傳入...剩彬，當(dāng)D遍歷然后，返回到B矿卑，B的右孩子為空喉恋，所以返回到A，傳入A的右孩子C...母廷。所以最后的遍歷結(jié)果是:A-B-D-C
4.3 中序遍歷
# 中序遍歷
def in_order(node):
if node is None:
return None
else:
in_order(node.left)
print(node.key)
in_order(node.right)
分析同上轻黑，這里就不贅述了。遍歷結(jié)果:D-B-A-C
4.4 后續(xù)遍歷
# 后序遍歷
def post_order(node):
if node is None:
return None
else:
post_order(node.left)
post_order(node.right)
print(node.key)
分析還是同上,遍歷結(jié)果：D-B-C-A
其實(shí)徘意，很容易發(fā)現(xiàn)苔悦，采用何種遍歷方式，就是講print(node.key)這句代碼放在哪個(gè)位置椎咧。
4.5 層次遍歷
# 層次遍歷
def levelOrderTravel(node):
if node is None:
return
q = [node]
while len(q):
print(q[0].key)
node = q.pop(0)
if node.left is not None:
q.append(node.left)
if node.right is not None:
q.append(node.right)
上文中曾提到玖详，二叉樹(shù)的層次遍歷其實(shí)是運(yùn)用到了隊(duì)列把介，我們還是用上面那個(gè)簡(jiǎn)單的二叉樹(shù)來(lái)作分析，它的遍歷結(jié)果為:A-B-C-D蟋座。代碼是如何實(shí)現(xiàn)的呢拗踢？其實(shí)是首先將A入隊(duì)，然后然后讀取隊(duì)首向臀，判斷其是否有左孩子巢墅，有則入隊(duì)，然后判斷右孩子券膀，有則入隊(duì)君纫，最后將隊(duì)首彈出，注意芹彬，隊(duì)列的彈出順序就是層次遍歷的順序蓄髓。
5.寫(xiě)在后面
二叉樹(shù)的一些基本內(nèi)容差不多就介紹這么多，之后準(zhǔn)備寫(xiě)一點(diǎn)二叉樹(shù)的應(yīng)用舒帮。比如会喝，二叉堆（堆排序），二叉搜索樹(shù)等玩郊。
持續(xù)更新中...
二叉樹(shù)（二）-二叉堆
