二叉樹(shù)是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹(shù)的樹(shù)結(jié)構(gòu)。通常子樹(shù)被稱作“左子樹(shù)”（left subtree）和“右子樹(shù)”（right subtree）
打開(kāi)UC瀏覽器 查看更多精彩圖片
二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)：
將二叉樹(shù)的節(jié)點(diǎn)定義為一個(gè)對(duì)象，節(jié)點(diǎn)之間通過(guò)類似鏈表的鏈接方式來(lái)連接。
樹(shù)的定義與基本術(shù)語(yǔ)
樹(shù)型結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，其中以樹(shù)和二叉樹(shù)最為常用，是以分支關(guān)系定義的層次結(jié)構(gòu)。樹(shù)結(jié)構(gòu)在客觀世界中廣泛存在，如人類社會(huì)的族譜和各種社會(huì)組織機(jī)構(gòu)；在計(jì)算機(jī)領(lǐng)域中也有廣泛應(yīng)用，如在編譯程序中，可用樹(shù)來(lái)表示源程序的語(yǔ)法結(jié)構(gòu)；在數(shù)據(jù)庫(kù)系統(tǒng)中，樹(shù)型結(jié)構(gòu)也是信息的重要組織形式之一；在機(jī)器學(xué)習(xí)中，決策樹(shù)，隨機(jī)森林，GBDT等是常見(jiàn)的樹(shù)模型。
樹(shù)（Tree）是n(n>=0)個(gè)結(jié)點(diǎn)的有限集。在任意一棵樹(shù)中：（1）有且僅有一個(gè)特定的稱為根（Root）的節(jié)點(diǎn)；（2）當(dāng)n>1時(shí)，其余節(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集，其中每一個(gè)集合本身又是一棵樹(shù)，并且稱為根的子樹(shù)（SubTree）。
打開(kāi)UC瀏覽器 查看更多精彩圖片
圖1 樹(shù)型結(jié)構(gòu)
在圖1，該樹(shù)一共有13個(gè)節(jié)點(diǎn)，其中A是根，其余節(jié)點(diǎn)分成3個(gè)互不相交的子集：
T1={B,E,F,K,L}，T2={C,G}，T3={D,H,I,J,K}；T1,T2,T3都是根A的子樹(shù)，且本身也是一顆樹(shù)。
例如T1，其根為B，其余節(jié)點(diǎn)分為兩個(gè)互不相交的子集；T11={E,K,L},T12={F}。T11和T12都是B的子樹(shù)。而在T11中E是根，{K}和{L}是E的兩棵互不相交的子樹(shù)，其本身又是只有一個(gè)根節(jié)點(diǎn)的樹(shù)。
樹(shù)的基本術(shù)語(yǔ)
樹(shù)的結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)元素及若干指向其子樹(shù)的分支。
節(jié)點(diǎn)擁有的子樹(shù)數(shù)量稱為節(jié)點(diǎn)的度（Degree）。
在圖1中，A的度為3，B的度為2，C的度為1，F(xiàn)的度為0。
度為0的結(jié)點(diǎn)稱為葉子（Leaf）結(jié)點(diǎn)。
在圖1中，K,L,F,G,M,I,J都是該樹(shù)的葉子。度不為0的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)。
樹(shù)的度是指樹(shù)內(nèi)個(gè)結(jié)點(diǎn)的度的最大值。
結(jié)點(diǎn)的子樹(shù)的根稱為該結(jié)點(diǎn)的孩子（Child），相應(yīng)地，該結(jié)點(diǎn)稱為孩子的雙親（Parent）
在圖1,中，D是A的孩子，A是D的雙親。同一個(gè)雙親的孩子之間互稱兄弟(Sibling)
H,I,J互為兄弟。結(jié)點(diǎn)的祖先是從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)，M的祖先為A,D,H。
對(duì)應(yīng)地，以某結(jié)點(diǎn)為根的子樹(shù)中的任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫。B的子孫為E,F,K,L。
樹(shù)的層次(Level)是從根開(kāi)始，根為第一層，根的孩子為第二層等。雙親在同一層的結(jié)點(diǎn)互為同兄弟。圖1中，K,L,M互為堂兄弟。樹(shù)中結(jié)點(diǎn)的最大層次稱為樹(shù)的深度(Depth)或高度，樹(shù)的深度為4。
如果將樹(shù)中結(jié)點(diǎn)的各子樹(shù)看成從左到右是有次序的（即不能交換），則稱該樹(shù)為有序樹(shù)，否則為無(wú)序樹(shù)。
森林（Forest）是m(m>=0)棵互不相交的樹(shù)的集合。對(duì)樹(shù)中每個(gè)結(jié)點(diǎn)而言，其子樹(shù)的集合即為森林。
在機(jī)器學(xué)習(xí)模型中，決策樹(shù)為樹(shù)型結(jié)構(gòu)，而隨機(jī)森林為森林，是由若干決策樹(shù)組成的森林。
性質(zhì)
性質(zhì)1: 在二叉樹(shù)的第i層上至多有2^(i-1)個(gè)結(jié)點(diǎn)（i>0）
性質(zhì)2: 深度為k的二叉樹(shù)至多有2^k - 1個(gè)結(jié)點(diǎn)（k>0）
性質(zhì)3：對(duì)于任意一棵二叉樹(shù)，如果其葉結(jié)點(diǎn)數(shù)為N0，而度數(shù)為2的結(jié)點(diǎn)總數(shù)為N2，則N0=N2+1;
性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為 log2(n+1)
性質(zhì)5：對(duì)完全二叉樹(shù)，若從上至下、從左至右編號(hào)，則編號(hào)為i 的結(jié)點(diǎn)，其左孩子編號(hào)必為2i，其右孩子編號(hào)必為2i＋1；其雙親的編號(hào)必須為i/2（i＝1 時(shí)為根,除外）
分類
1.完全二叉樹(shù)——若設(shè)二叉樹(shù)的高度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第h層有葉子結(jié)點(diǎn)，并且葉子結(jié)點(diǎn)都是從左到右依次排布。
2.滿二叉樹(shù)——除了葉結(jié)點(diǎn)外每一個(gè)結(jié)點(diǎn)都有左右子葉且葉子結(jié)點(diǎn)都處在最底層的二叉樹(shù)。
二叉樹(shù)Python實(shí)現(xiàn)
class Node(object):
"""節(jié)點(diǎn)類"""
def init(self, elem=-1, lchild=None, rchild=None):
self.elem = elem # 自身
self.lchild = lchild # 左孩子
self.rchild = rchild # 右孩子
class Tree(object):
"""樹(shù)類"""
def init(self, root=None):
self.root = root
def add(self, elem):
node = Node(elem)
if self.root == None:
self.root = node
else:
queue = []
queue.append(self.root) # 先將根節(jié)點(diǎn)添加到隊(duì)列中
while queue: # 遍歷樹(shù)
cur = queue.pop(0) # 首先彈出了根節(jié)點(diǎn)
if cur.lchild == None: # 如果沒(méi)有做孩子的話
cur.lchild = node # 添加node
return
elif cur.rchild == None: # 如果沒(méi)有有孩子的話
cur.rchild = node
return
else: # 如果左右子樹(shù)都不為空，加入隊(duì)列繼續(xù)判斷
queue.append(cur.lchild)
queue.append(cur.rchild)
二叉樹(shù)的遍歷：
常見(jiàn)的遍歷方法有：先序遍歷，中序遍歷，后序遍歷，層序遍歷。這些遍歷方法一般使用遞歸算法實(shí)現(xiàn)。
前序遍歷：EACBDGF
前序遍歷的操作定義為：若二叉樹(shù)為空，為空操作；否則（1）訪問(wèn)根節(jié)點(diǎn)；（2）先序遍歷左子樹(shù)；（3）先序遍歷右子樹(shù)。
遞歸實(shí)現(xiàn)：
def preorder(root):
if not root:
return
print(root.val)
preorder(root.left)
preorder(root.right)
迭代實(shí)現(xiàn)：
def preorder(root):
stack = [root]
while stack:
s = stack.pop()
if s:
print(s.val)
stack.append(s.right)
stack.append(s.left)
中序遍歷：ABCDEGF
中序遍歷的操作定義為：若二叉樹(shù)為空，為空操作；否則（1）中序遍歷左子樹(shù)；（2）訪問(wèn)根結(jié)點(diǎn)；（3）中序遍歷右子樹(shù)。
遞歸實(shí)現(xiàn)：
def inorder(root):
if not root:
return
inorder(root.left)
print(root.val)
inorder(root.right)
迭代實(shí)現(xiàn)：
def inorder(root):
stack = []
while stack or root:
while root:
stack.append(root)
root = root.left
root = stack.pop()
print(root.val)
root = root.right
后序遍歷：BDCAFGE
后序遍歷的操作定義為：若二叉樹(shù)為空，為空操作；否則（1）后序遍歷左子樹(shù)；（2）后序遍歷右子樹(shù)；（3）訪問(wèn)根結(jié)點(diǎn)。
遞歸實(shí)現(xiàn)：
def postorder(root):
if not root:
return
postorder(root.left)
postorder(root.right)
print(root.val)
迭代實(shí)現(xiàn)：
def postorder(root):
stack = []
while stack or root:
while root: # 下行循環(huán)，直到找到第一個(gè)葉子節(jié)點(diǎn)
stack.append(root)
if root.left: # 能左就左，不能左就右
root = root.left
else:
root = root.right
s = stack.pop()
print(s.val)
#如果當(dāng)前節(jié)點(diǎn)是上一節(jié)點(diǎn)的左子節(jié)點(diǎn)，則遍歷右子節(jié)點(diǎn)
if stack and s == stack[-1].left:
root = stack[-1].right
else:
root = None
層次遍歷：EAGCFBD
層序遍歷的操作定義為：若二叉樹(shù)為空，為空操作；否則從上到下、從左到右按層次進(jìn)行訪問(wèn)。
遞歸實(shí)現(xiàn)：
def BFS(root):
queue = [root]
while queue:
n = len(queue)
for i in range(n):
q = queue.pop(0)
if q:
print(q.val)
queue.append(q.left if q.left else None)
queue.append(q.right if q.right else None)
代碼實(shí)現(xiàn)：
* coding=utf-8 *
"""
實(shí)現(xiàn)一個(gè)二叉樹(shù)結(jié)果，并進(jìn)行遍歷
E
/
A G
\
C F
/
B D
"""
from collections import deque
class BinaryTree(object):
def init(self, data):
self.data = data
self.child_l = None
self.child_r = None
創(chuàng)建
a = BinaryTree("A")
b = BinaryTree("B")
c = BinaryTree("C")
d = BinaryTree("D")
e = BinaryTree("E")
f = BinaryTree("F")
g = BinaryTree("G")
構(gòu)造節(jié)點(diǎn)關(guān)系
e.child_l = a
e.child_r = g
a.child_r = c
c.child_l = b
c.child_r = d
g.child_r = f
設(shè)置根
root = e
def pre_order(tree):
"""
前序遍歷:root -> child_l -> child_r
:param tree: the root of tree
:return:
"""
if tree:
print(tree.data, end=',')
# print("")
pre_order(tree.child_l)
pre_order(tree.child_r)
def in_order(tree):
"""
中序遍歷：child_l -> root -> child_r
:param tree:
:return:
"""
if tree:
in_order(tree.child_l)
print(tree.data, end=',')
in_order(tree.child_r)
def post_order(tree):
"""
后序遍歷：child_l -> child_r -> root
:param tree:
:return:
"""
if tree:
post_order(tree.child_l)
post_order(tree.child_r)
print(tree.data, end=',')
def level_order(tree):
"""
層次遍歷：E -> AG -> CF -> BD
使用隊(duì)列實(shí)現(xiàn)
:param tree:
:return:
"""
queue = deque()
queue.append(tree) # 先把根添加到隊(duì)列
while len(queue): # 隊(duì)列不為空
node = queue.popleft()
print(node.data, end=',')
if node.child_l:
queue.append(node.child_l)
if node.child_r:
queue.append(node.child_r)
pre_order(root)
print('')
in_order(root)
print('')
post_order(root)
print('')
level_order(root)
二叉樹(shù)的最大深度
基本思路就是遞歸，當(dāng)前樹(shù)的最大深度等于（1+max(左子樹(shù)最大深度，右子樹(shù)最大深度)）。代碼如下：
def maxDepth(root):
if not root:
return 0
return 1+max(maxDepth(root.left),maxDepth(root.right))
二叉樹(shù)的最小深度
最小深度是從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)量。可以通過(guò)遞歸求左右節(jié)點(diǎn)的最小深度的較小值，也可以層序遍歷找到第一個(gè)葉子節(jié)點(diǎn)所在的層數(shù)。
遞歸方法：
class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root:
return 0
if not root.left and not root.right:
return 1
if not root.right:
return 1+self.minDepth(root.left)
if not root.left:
return 1+self.minDepth(root.right)
return 1+min(self.minDepth(root.left),self.minDepth(root.right))
迭代方法：
class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root: return 0
ans,count = [root],1
while ans:
n = len(ans)
for i in range(n):
r = ans.pop(0)
if r:
if not r.left and not r.right:
return count
ans.append(r.left if r.left else [])
ans.append(r.right if r.right else [])
count+=1
二叉樹(shù)的所有路徑
根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的所有路徑。
def traverse(node):
if not node.left and not node.right:
return [str(node.val)]
left, right = [], []
if node.left:
left = [str(node.val) + x for x in traverse(node.left)]
if node.right:
right = [str(node.val) + x for x in traverse(node.right)]
return left + right
