二叉樹的概念：

二叉樹是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹的樹結(jié)構(gòu)。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）

二叉樹的鏈?zhǔn)酱鎯?chǔ)：

將二叉樹的節(jié)點(diǎn)定義為一個(gè)對(duì)象，節(jié)點(diǎn)之間通過類似鏈表的鏈接方式來連接。

樹的定義與基本術(shù)語

樹型結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，其中以樹和二叉樹最為常用，是以分支關(guān)系定義的層次結(jié)構(gòu)。樹結(jié)構(gòu)在客觀世界中廣泛存在，如人類社會(huì)的族譜和各種社會(huì)組織機(jī)構(gòu)；在計(jì)算機(jī)領(lǐng)域中也有廣泛應(yīng)用，如在編譯程序中，可用樹來表示源程序的語法結(jié)構(gòu)；在數(shù)據(jù)庫系統(tǒng)中，樹型結(jié)構(gòu)也是信息的重要組織形式之一；在機(jī)器學(xué)習(xí)中，決策樹，隨機(jī)森林，GBDT等是常見的樹模型。樹（Tree）是n(n>=0)個(gè)結(jié)點(diǎn)的有限集。在任意一棵樹中：（1）有且僅有一個(gè)特定的稱為根（Root）的節(jié)點(diǎn)；（2）當(dāng)n>1時(shí)，其余節(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集，其中每一個(gè)集合本身又是一棵樹，并且稱為根的子樹（SubTree）。

圖1 樹型結(jié)構(gòu)

在圖1，該樹一共有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的子樹，且本身也是一顆樹。

例如T1，其根為B，其余節(jié)點(diǎn)分為兩個(gè)互不相交的子集；T11={E,K,L},T12={F}。T11和T12都是B的子樹。而在T11中E是根，{K}和{L}是E的兩棵互不相交的子樹，其本身又是只有一個(gè)根節(jié)點(diǎn)的樹。

樹的基本術(shù)語

樹的結(jié)點(diǎn)包含一個(gè)數(shù)據(jù)元素及若干指向其子樹的分支。

節(jié)點(diǎn)擁有的子樹數(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都是該樹的葉子。度不為0的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)。

樹的度是指樹內(nèi)個(gè)結(jié)點(diǎn)的度的最大值。

結(jié)點(diǎn)的子樹的根稱為該結(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)為根的子樹中的任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫。B的子孫為E,F,K,L。

樹的層次(Level)是從根開始，根為第一層，根的孩子為第二層等。雙親在同一層的結(jié)點(diǎn)互為同兄弟。圖1中，K,L,M互為堂兄弟。樹中結(jié)點(diǎn)的最大層次稱為樹的深度(Depth)或高度，樹的深度為4。

如果將樹中結(jié)點(diǎn)的各子樹看成從左到右是有次序的（即不能交換），則稱該樹為有序樹，否則為無序樹。

森林（Forest）是m(m>=0)棵互不相交的樹的集合。對(duì)樹中每個(gè)結(jié)點(diǎn)而言，其子樹的集合即為森林。

在機(jī)器學(xué)習(xí)模型中，決策樹為樹型結(jié)構(gòu)，而隨機(jī)森林為森林，是由若干決策樹組成的森林。

性質(zhì)

性質(zhì)1: 在二叉樹的第i層上至多有2^(i-1)個(gè)結(jié)點(diǎn)（i>0）

性質(zhì)2: 深度為k的二叉樹至多有2^k - 1個(gè)結(jié)點(diǎn)（k>0）

性質(zhì)3：對(duì)于任意一棵二叉樹，如果其葉結(jié)點(diǎn)數(shù)為N0，而度數(shù)為2的結(jié)點(diǎn)總數(shù)為N2，則N0=N2+1;

性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 log2(n+1)

性質(zhì)5：對(duì)完全二叉樹，若從上至下、從左至右編號(hào)，則編號(hào)為i 的結(jié)點(diǎn)，其左孩子編號(hào)必為2i，其右孩子編號(hào)必為2i＋1；其雙親的編號(hào)必須為i/2（i＝1 時(shí)為根,除外）

分類

1.完全二叉樹——若設(shè)二叉樹的高度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第h層有葉子結(jié)點(diǎn)，并且葉子結(jié)點(diǎn)都是從左到右依次排布。

2.滿二叉樹——除了葉結(jié)點(diǎn)外每一個(gè)結(jié)點(diǎn)都有左右子葉且葉子結(jié)點(diǎn)都處在最底層的二叉樹。

二叉樹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):?"""樹類"""?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: ?# 遍歷樹?cur = queue.pop(0) ?# 首先彈出了根節(jié)點(diǎn)?if cur.lchild == None: ?# 如果沒有做孩子的話?cur.lchild = node ?# 添加node?return?elif cur.rchild == None: ?# 如果沒有有孩子的話?cur.rchild = node? ? ? ? ? ? ? ? ? ?return?else: ?# 如果左右子樹都不為空，加入隊(duì)列繼續(xù)判斷?queue.append(cur.lchild)?queue.append(cur.rchild)

二叉樹的遍歷：

常見的遍歷方法有：先序遍歷，中序遍歷，后序遍歷，層序遍歷。這些遍歷方法一般使用遞歸算法實(shí)現(xiàn)。

前序遍歷：EACBDGF

前序遍歷的操作定義為：若二叉樹為空，為空操作；否則（1）訪問根節(jié)點(diǎn)；（2）先序遍歷左子樹；（3）先序遍歷右子樹。

遞歸實(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

中序遍歷的操作定義為：若二叉樹為空，為空操作；否則（1）中序遍歷左子樹；（2）訪問根結(jié)點(diǎn)；（3）中序遍歷右子樹。

遞歸實(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

后序遍歷的操作定義為：若二叉樹為空，為空操作；否則（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結(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

層序遍歷的操作定義為：若二叉樹為空，為空操作；否則從上到下、從左到右按層次進(jì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è)二叉樹結(jié)果，并進(jì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")# 構(gòu)造節(jié)點(diǎn)關(guān)系e.child_l = ae.child_r = ga.child_r = cc.child_l = bc.child_r = dg.child_r = f# 設(shè)置根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?使用隊(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)

二叉樹的最大深度

基本思路就是遞歸，當(dāng)前樹的最大深度等于（1+max(左子樹最大深度，右子樹最大深度)）。代碼如下：

def maxDepth(root):?if not root:?return 0?return 1+max(maxDepth(root.left),maxDepth(root.right))

二叉樹的最小深度

最小深度是從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)量?？梢酝ㄟ^遞歸求左右節(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

二叉樹的所有路徑

根節(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