二叉樹的概念：
二叉樹是每個節(jié)點最多有兩個子樹的樹結構剪决。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）
二叉樹的鏈式存儲：
將二叉樹的節(jié)點定義為一個對象趁啸，節(jié)點之間通過類似鏈表的鏈接方式來連接。
樹的定義與基本術語
樹型結構是一類重要的非線性數(shù)據(jù)結構，其中以樹和二叉樹最為常用，是以分支關系定義的層次結構。樹結構在客觀世界中廣泛存在，如人類社會的族譜和各種社會組織機構窟感；在計算機領域中也有廣泛應用，如在編譯程序中歉井，可用樹來表示源程序的語法結構柿祈；在數(shù)據(jù)庫系統(tǒng)中，樹型結構也是信息的重要組織形式之一哩至；在機器學習中躏嚎，決策樹，隨機森林菩貌，GBDT等是常見的樹模型卢佣。樹（Tree）是n(n>=0)個結點的有限集。在任意一棵樹中：（1）有且僅有一個特定的稱為根（Root）的節(jié)點箭阶；（2）當n>1時虚茶，其余節(jié)點可分為m(m>0)個互不相交的有限集，其中每一個集合本身又是一棵樹仇参，并且稱為根的子樹（SubTree）嘹叫。
圖1 樹型結構
在圖1，該樹一共有13個節(jié)點诈乒，其中A是根罩扇，其余節(jié)點分成3個互不相交的子集：
T1={B,E,F,K,L}，T2={C,G}怕磨，T3={D,H,I,J,K}喂饥；T1,T2,T3都是根A的子樹消约，且本身也是一顆樹。
例如T1员帮，其根為B或粮，其余節(jié)點分為兩個互不相交的子集；T11={E,K,L},T12={F}集侯。T11和T12都是B的子樹。而在T11中E是根帜消，{K}和{L}是E的兩棵互不相交的子樹棠枉，其本身又是只有一個根節(jié)點的樹。
樹的基本術語
樹的結點包含一個數(shù)據(jù)元素及若干指向其子樹的分支泡挺。
節(jié)點擁有的子樹數(shù)量稱為節(jié)點的度（Degree）辈讶。
在圖1中，A的度為3娄猫，B的度為2贱除，C的度為1，F(xiàn)的度為0媳溺。
度為0的結點稱為葉子（Leaf）結點月幌。
在圖1中，K,L,F,G,M,I,J都是該樹的葉子悬蔽。度不為0的結點稱為分支結點扯躺。
樹的度是指樹內(nèi)個結點的度的最大值。
結點的子樹的根稱為該結點的孩子（Child）蝎困，相應地录语，該結點稱為孩子的雙親（Parent）
在圖1,中，D是A的孩子禾乘，A是D的雙親澎埠。同一個雙親的孩子之間互稱兄弟(Sibling)
H,I,J互為兄弟。結點的祖先是從根到該結點所經(jīng)分支上的所有結點始藕，M的祖先為A,D,H蒲稳。
對應地，以某結點為根的子樹中的任一結點都稱為該結點的子孫伍派。B的子孫為E,F,K,L弟塞。
樹的層次(Level)是從根開始，根為第一層拙已，根的孩子為第二層等决记。雙親在同一層的結點互為同兄弟。圖1中倍踪，K,L,M互為堂兄弟系宫。樹中結點的最大層次稱為樹的深度(Depth)或高度索昂，樹的深度為4。
如果將樹中結點的各子樹看成從左到右是有次序的（即不能交換）扩借，則稱該樹為有序樹椒惨，否則為無序樹。
森林（Forest）是m(m>=0)棵互不相交的樹的集合潮罪。對樹中每個結點而言康谆，其子樹的集合即為森林。
在機器學習模型中嫉到，決策樹為樹型結構沃暗，而隨機森林為森林，是由若干決策樹組成的森林何恶。
性質
性質1: 在二叉樹的第i層上至多有2^(i-1)個結點（i>0）
性質2: 深度為k的二叉樹至多有2^k - 1個結點（k>0）
性質3：對于任意一棵二叉樹孽锥，如果其葉結點數(shù)為N0，而度數(shù)為2的結點總數(shù)為N2细层，則N0=N2+1;
性質4：具有n個結點的完全二叉樹的深度為 log2(n+1)
性質5：對完全二叉樹惜辑，若從上至下、從左至右編號疫赎，則編號為i 的結點盛撑，其左孩子編號必為2i，其右孩子編號必為2i＋1捧搞；其雙親的編號必須為i/2（i＝1 時為根,除外）
分類
1.完全二叉樹——若設二叉樹的高度為h撵彻，除第 h 層外，其它各層 (1～h-1) 的結點數(shù)都達到最大個數(shù)实牡，第h層有葉子結點陌僵，并且葉子結點都是從左到右依次排布。
2.滿二叉樹——除了葉結點外每一個結點都有左右子葉且葉子結點都處在最底層的二叉樹创坞。
二叉樹Python實現(xiàn)
class Node(object):?"""節(jié)點類"""?def __init__(self, elem=-1, lchild=None, rchild=None):?self.elem = elem ?# 自身?self.lchild = lchild ?# 左孩子?self.rchild = rchild ?# 右孩子class Tree(object):?"""樹類"""?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é)點添加到隊列中?while queue: ?# 遍歷樹?cur = queue.pop(0) ?# 首先彈出了根節(jié)點?if cur.lchild == None: ?# 如果沒有做孩子的話?cur.lchild = node ?# 添加node?return?elif cur.rchild == None: ?# 如果沒有有孩子的話?cur.rchild = node? ? ? ? ? ? ? ? ? ?return?else: ?# 如果左右子樹都不為空碗短，加入隊列繼續(xù)判斷?queue.append(cur.lchild)?queue.append(cur.rchild)
二叉樹的遍歷：
常見的遍歷方法有：先序遍歷，中序遍歷题涨，后序遍歷偎谁，層序遍歷。這些遍歷方法一般使用遞歸算法實現(xiàn)纲堵。
前序遍歷：EACBDGF
前序遍歷的操作定義為：若二叉樹為空巡雨，為空操作；否則（1）訪問根節(jié)點席函；（2）先序遍歷左子樹铐望；（3）先序遍歷右子樹。
遞歸實現(xiàn)：
def preorder(root):?if not root:?return?print(root.val)?preorder(root.left)?preorder(root.right)
迭代實現(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
中序遍歷的操作定義為：若二叉樹為空，為空操作正蛙；否則（1）中序遍歷左子樹督弓；（2）訪問根結點；（3）中序遍歷右子樹乒验。
遞歸實現(xiàn)：
def inorder(root):?if not root:?return?inorder(root.left)?print(root.val)?inorder(root.right)
迭代實現(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
后序遍歷的操作定義為：若二叉樹為空愚隧，為空操作；否則（1）后序遍歷左子樹锻全；（2）后序遍歷右子樹狂塘；（3）訪問根結點。
遞歸實現(xiàn)：
def postorder(root):?if not root:?return?postorder(root.left)?postorder(root.right)?print(root.val)
迭代實現(xiàn)：
def postorder(root):?stack = []?while stack or root:?while root: ? ? ? ? ? ? ? ? # 下行循環(huán)鳄厌，直到找到第一個葉子節(jié)點?stack.append(root)?if root.left: ? ? ? ? ? # 能左就左荞胡，不能左就右?root = root.left?else:?root = root.right?s = stack.pop()?print(s.val)?#如果當前節(jié)點是上一節(jié)點的左子節(jié)點，則遍歷右子節(jié)點?if stack and s == stack[-1].left:?root = stack[-1].right?else:?root = None
層次遍歷：EAGCFBD
層序遍歷的操作定義為：若二叉樹為空部翘，為空操作硝训；否則從上到下响委、從左到右按層次進行訪問新思。
遞歸實現(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)
代碼實現(xiàn)：
# _*_ coding=utf-8 _*_"""實現(xiàn)一個二叉樹結果，并進行遍歷?E?/ ?\?A ? ?G?\ ? ?\?C ? ?F?/ \?B ? D"""from collections import dequeclass 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")# 構造節(jié)點關系e.child_l = ae.child_r = ga.child_r = cc.child_l = bc.child_r = dg.child_r = f# 設置根root = edef 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?使用隊列實現(xiàn)? ?:param tree:?:return:?"""?queue = deque()?queue.append(tree) ? ? ? ? ?# 先把根添加到隊列?while len(queue): ? ? ? ? ? # 隊列不為空?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)
二叉樹的最大深度
基本思路就是遞歸赘风，當前樹的最大深度等于（1+max(左子樹最大深度夹囚，右子樹最大深度)）。代碼如下：
def maxDepth(root):?if not root:?return 0?return 1+max(maxDepth(root.left),maxDepth(root.right))
二叉樹的最小深度
最小深度是從根節(jié)點到最近葉子節(jié)點的最短路徑上的節(jié)點數(shù)量邀窃≥┯矗可以通過遞歸求左右節(jié)點的最小深度的較小值，也可以層序遍歷找到第一個葉子節(jié)點所在的層數(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
二叉樹的所有路徑
根節(jié)點到葉子節(jié)點的所有路徑鞍历。
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
