[校招-演算法題] 二叉樹基礎演算法1
二叉樹是面試中常考的資料結構，因為涉及大量指標操作，因此可以考察思維的嚴謹性和靈活性。但是校招中的二叉樹題規律性很強，因此需要總結一下。
各種常見的二叉樹概念
二叉樹：每個結點最多有兩個子樹（左子樹和右子樹）的樹結構。
節點的層次：一個結點的層次直觀上來說就是其所在的行，其中根結點層次為1。
二叉樹的深度：二叉樹的深度指二叉樹的最大葉子結點所在的層。二叉樹的深度求解可用遞迴方式實現，等於max（左子樹深度，右子樹深度）+1。
結點的度：二叉樹結點的度指該結點分支的個數，取值為0、1或2。
結點種類：
根結點：第一層的結點
葉子結點：度為0的結點
分支結點：度不為0的結點
孩子結點：結點的子樹的根稱為該結點的孩子結點
兄弟結點：同一雙親的孩子結點
祖先結點：從根到該結點上所經分支的所有結點
子孫節點：以某結點為根的子樹中任一結點都稱為該結點的子孫節點
建立一棵二叉樹
class
Node
：
“”“
節點類
”“”
def
__init__
（
self
，
value
=
None
，
left
=
None
，
right
=
None
）：
self
。
val
=
value
self
。
left
=
left
self
。
right
=
right
class
Tree
：
“”“
樹類
”“”
def
__init__
（
self
）：
self
。
root
=
Node
（）
self
。
queue
=
［］
def
add
（
self
，
val
）：
“”“
為樹新增節點
”“”
node
=
Node
（
value
=
val
）
if
self
。
root
。
val
is
None
：
# 如果樹是空的，則對根節點賦值
self
。
root
=
node
self
。
queue
。
append
（
self
。
root
）
else
：
treeNode
=
self
。
queue
［
0
］
# 此節點的子樹還沒有齊
if
treeNode
。
left
is
None
：
treeNode
。
left
=
node
self
。
queue
。
append
（
treeNode
。
left
）
else
：
treeNode
。
right
=
node
self
。
queue
。
append
（
treeNode
。
right
）
self
。
queue
。
pop
（
0
）
# 如果該節點存在左右子樹，將此節點丟棄
if
__name__
==
‘__main__’
：
vals
=
range
（
10
）
# 生成十個資料作為樹節點
tree
=
Tree
（）
# 新建一個樹物件
for
val
in
vals
：
tree
。
add
（
val
）
# 逐個新增樹的節點
![[校招-演算法題] 二叉樹基礎演算法1](https://img.heatask.com/upload/website_attach/fiU511GvNc9qeMOC0q=v8WgvFHPT1U9Q1K4uGUSaaxgqzomye17zEGuo9RxePSd7g7ctmUAoZnAhdxCa00=6rw-Rb.jpeg)
程式碼構造的二叉樹
二叉樹的分類
滿二叉樹：
除葉結點外每一個結點都有左右子結點並且葉子結點都處在最底層的二叉樹。
完全二叉樹：
除最後一層外，其他各層的結點數都達到最大，最後一層的葉子結點都是從左往右依次排布。
二叉排序樹（BST）：
或者是一棵空樹，或者具有如下性質：（1）若左子樹不為空，則左子樹上所有結點的值均小於它的根結點的值；（2）若右子樹不為空，則右子樹上所有結點的值均大於它的根結點的值；（3）左右子樹也分別為二叉排序樹；（4）沒有值相等的結點。
平衡二叉樹（AVL）：
一種二叉排序樹，其中每個結點的左子樹和右子樹的高度差至多等於1。要麼它是一棵空樹，要麼它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值不超過1。
二叉樹的遍歷
二叉樹最重要的是四種遍歷演算法：前序遍歷（遞迴和非遞迴）、中序遍歷（遞迴和非遞迴）、後序遍歷（遞迴和非遞迴）和層次遍歷。
前序遍歷（根左右）
先訪問根結點，然後訪問左子樹，再訪問右子樹。
遞迴演算法：
def
pre_order
（
root
）：
if
root
：
（
root
。
val
，
end
=
“ ”
）
pre_order
（
root
。
left
）
pre_order
（
root
。
right
）
非遞迴演算法：
使用棧來臨時儲存節點：（1）列印根結點資料；（2）把根結點的right入棧，遍歷左子樹；（3）遍歷完左子樹返回時，棧頂元素應為right，出棧，遍歷以該結點為根的子樹
def
pre_order_stack
（
root
）：
p
=
root
s
=
［］
# stack
while
p
or
s
：
while
p
：
（
p
。
val
，
end
=
“ ”
）
s
。
append
（
p
。
right
）
p
=
p
。
left
if
s
：
# 注意這裡是if，不是while
p
=
s
。
pop
（
-
1
）
中序遍歷（左根右）
遞迴演算法：
def
in_order
（
root
）：
if
root
：
in_order
（
root
。
left
）
（
root
。
val
，
end
=
“ ”
）
in_order
（
root
。
right
）
非遞迴演算法：
使用棧來儲存臨時節點，（1）先將根節點入棧，遍歷左子樹；（2）遍歷完左子樹返回時，棧頂元素應為根節點，此時出棧，並列印節點資料；（3）再中序遍歷右子樹。
def
in_order_stack
（
root
）：
p
=
root
s
=
［］
# stack
while
p
or
s
：
while
p
：
s
。
append
（
p
）
p
=
p
。
left
if
s
：
p
=
s
。
pop
（
-
1
）
（
p
。
val
，
end
=
“ ”
）
p
=
p
。
right
後序遍歷（左右根）
遞迴演算法：
def
post_order
（
root
）：
if
root
：
post_order
（
root
。
left
）
post_order
（
root
。
right
）
（
root
。
val
，
end
=
“ ”
）
非遞迴演算法：
使用棧來儲存臨時節點，使用雜湊表來記錄狀態。
假設root時遍歷樹的根指標，後序遍歷要求在遍歷完左、右子樹後再訪問根，需要判斷根結點的左、右子樹是否均遍歷過。使用標記法，節點入棧時，將該結點存入雜湊表，值為0表示遍歷左子樹前的現場保護，值為1表示遍歷右子樹前的現場保護。
首先將root，遍歷左子樹；返回後，修改雜湊表中該結點的值為1，遍歷右子樹，最後訪問根節點。
def
post_order_stack
（
root
）：
p
=
root
s
=
［］
# stack
d
=
{}
while
p
or
s
：
while
p
：
s
。
append
（
p
）
d
［
p
］
=
0
p
=
p
。
left
if
s
：
p
=
s
［
-
1
］
if
d
［
p
］
==
1
：
# 如果該結點的右子樹遍歷過了，則列印該結點的值
（
p
。
val
，
end
=
“ ”
）
s
。
pop
（
-
1
）
p
=
None
else
：
d
［
p
］
=
1
p
=
p
。
right
層次遍歷
層次遍歷需要使用一個輔助佇列，初始元素是根結點。當佇列不為空時，每次列印佇列最前端結點的值，然後判斷該結點左子結點是否存在，存在就壓入佇列；再判斷該結點右子節點是否存在，存在就壓入佇列。
def
level_order
（
root
）：
if
root
is
None
：
return
None
my_queue
=
［
root
］
node
=
root
while
my_queue
：
node
=
my_queue
。
pop
（
0
）
（
node
。
val
，
end
=
“ ”
）
if
node
。
left
：
my_queue
。
append
（
node
。
left
）
if
node
。
right
：
my_queue
。
append
（
node
。
right
）
二叉樹遍歷的應用
分層列印二叉樹
在層次遍歷的基礎上，使用兩個額外的變數分別儲存當前層需要列印的結點數和下一層的結點數。
def
level_print
（
root
）：
if
root
is
None
：
return
None
my_queue
=
［
root
］
node
=
root
to_be_printed
=
1
next_level
=
0
while
my_queue
：
node
=
my_queue
。
pop
（
0
）
if
to_be_printed
：
（
node
。
val
，
end
=
“ ”
）
to_be_printed
-=
1
else
：
to_be_printed
=
next_level
next_level
=
0
（）
（
node
。
val
，
end
=
“ ”
）
to_be_printed
-=
1
if
node
。
left
：
my_queue
。
append
（
node
。
left
）
next_level
+=
1
if
node
。
right
：
my_queue
。
append
（
node
。
right
）
next_level
+=
1
之字形列印二叉樹
def
level_print2
（
root
）：
“”“之字形列印二叉樹，在分行列印的基礎上新增一個記錄本層順序的值，之前列印的地方換成壓到一個列表”“”
if
root
is
None
：
return
None
my_queue
=
［］
node
=
root
my_queue
。
append
（
node
）
to_be_printed
=
1
next_level_num
=
0
all
=
［［］，
］
level_num
=
0
while
my_queue
：
node
=
my_queue
。
pop
（
0
）
if
to_be_printed
>
0
：
# print（node。elem， end=“ ”）
all
［
level_num
］
。
append
（
node
。
val
）
to_be_printed
-=
1
else
：
（）
to_be_printed
=
next_level_num
next_level_num
=
0
level_num
+=
1
all
。
append
（［］）
all
［
level_num
］
。
append
（
node
。
val
）
to_be_printed
-=
1
if
node
。
left
is
not
None
：
my_queue
。
append
（
node
。
left
）
next_level_num
+=
1
if
node
。
right
is
not
None
：
my_queue
。
append
（
node
。
right
）
next_level_num
+=
1
for
i
in
range
（
len
（
all
））：
if
i
%
2
==
0
：
for
j
in
all
［
i
］：
（
j
，
end
=
“ ”
）
if
i
！=
len
（
all
）
-
1
：
（）
else
：
all
［
i
］
。
reverse
（）
for
j
in
all
［
i
］：
（
j
，
end
=
“ ”
）
if
i
！=
len
（
all
）
-
1
：
（）
判斷二叉樹是否為完全二叉樹
演算法：
如果為空樹，直接返回True；
採用層次遍歷，使用一個變數leaf（預設為0）；
如果當前結點有右孩子，且沒有左孩子，直接返回False；
如果當前結點沒有兩個孩子，那麼leaf=1，之後的節點必須都為葉節點，即不能有孩子，否則返回False；
遍歷結束後沒有返回，那麼返回True。
def
is_complete_binary_tree
（
root
）：
if
not
root
：
return
True
my_queue
=
［
root
］
node
=
root
leaf
=
0
while
my_queue
：
node
=
my_queue
。
pop
（
0
）
if
node
。
left
is
None
and
node
。
right
is
not
None
：
# 沒有左孩子，但有右孩子
return
False
if
leaf
==
1
and
（
node
。
left
is
not
None
or
node
。
right
is
not
None
）：
# 不應該有孩子的結點有孩子存在
return
False
if
leaf
==
0
and
node
。
left
is
not
None
and
node
。
right
is
not
None
：
my_queue
。
append
（
node
。
left
）
my_queue
。
append
（
node
。
right
）
elif
leaf
==
0
and
node
。
left
is
not
None
and
node
。
right
is
None
：
my_queue
。
append
（
node
。
left
）
leaf
=
1
elif
leaf
==
0
and
node
。
left
is
None
and
node
。
right
is
None
：
leaf
=
1
return
True
上一篇:有木有好的搜題軟體？
