Python二叉樹初識(新手也秒懂!)
樹
樹（Tree）是n(n≥0)個節(jié)點的有限集。
在任意一棵樹中：
（1）有且僅有一個特定的稱為根（Root）的節(jié)點；
（2）當n＞1時，其余節(jié)點可分m(m＞0)為個互不相交的有限集T1,T2,...,Tm；
其中每一個集合本身又是一棵樹，并且稱為根的子樹（SubTree）。
Tree:
--------------------
Height=4 Leves=5 Root
Degree=3 Size=26 ↙
___________________17____________ Node Level1
/ / \ ↙
26______ 2 ___9__ ←- Child Level2
/ \ \ / / \
___0 19 _3___ 6 ___21 15 Level3
/ / \ / \ / \
7 _16 _24 _8 10 4 23 Level4
/ \ / / \ / \ / \
5 11 28 13 1 27 29 18 22 Level5
↑ ↑
↑___↑_______↑... Leaf Left Child Right Child
術語
節(jié)點：包含一個數(shù)據(jù)元素及若干指向其子樹的分支，又的譯成“結點”（Node）
根：樹和子樹的“頂點”（Root）
度：節(jié)點擁有的子樹數(shù)量稱為節(jié)點的度（Degree）；樹的度是指樹內(nèi)個結點的度的最大值
分支節(jié)點：度不為0的節(jié)點
葉子：沒有子樹的節(jié)點，即它的度為0 （Leaf）
子節(jié)點：結點的子樹的根稱為該節(jié)點的孩子（Child）
父節(jié)點：對應子節(jié)點上一層(level)節(jié)點稱為該節(jié)點的雙親（Parent）
兄弟結點：同一父節(jié)點的子節(jié)點，互稱兄弟（Sibling）
節(jié)點的祖先：是從根到該結點所經(jīng)分支上的所有節(jié)點
節(jié)點的子孫：以某結點為根的子樹中的所有節(jié)點
層：從根開始，根為第一層，根的孩子為第二層...（Level）
深度：樹中結點的最大層次數(shù)，稱為樹的深度或高度 （Depth or Height）
森林：是很多互不相交的樹的集合（Forest）
無序樹：樹中任意節(jié)點的子節(jié)點之間沒有順序關系，這種樹稱為無序樹，也稱為自由樹
有序樹：樹中任意節(jié)點的子節(jié)點之間有順序關系，這種樹稱為有序樹
最大樹（最小樹）：每個結點的值都大于（小于）或等于其子結點（如果有的話）值的樹
二叉樹
二叉樹（Binary Tree）是一種特殊的有序樹型結構。
特點：
（1）每個節(jié)點至多有兩棵子樹；
（2）二叉樹的子樹有左右之分；
（3）子樹的次序不能任意顛倒（有序樹）。
性質(zhì)：
（1）在二叉樹的第i層上至多有2^(i-1)個節(jié)點(i>=1)；
（2）深度為k的二叉樹至多有2^k-1個節(jié)點(k>=1)；
（3）對任何一棵二叉樹，如果其葉子節(jié)點數(shù)為N0,度為2的結點數(shù)為N2，則N0=N2+1。
特殊二叉樹
滿二叉樹：
所有層的節(jié)點都達到最大數(shù)量，葉子除外的所有節(jié)點都有兩個子節(jié)點，所有葉子都在最底一層(k)且數(shù)目為2^(k - 1)。即深度k且有2^k - 1個節(jié)點(葉子“長”滿最后一層)，或稱完美二叉樹 （Perfect Binary Tree）
______12_______
/ \
__3__ __5__
/ \ / \
_7 6 _9 11
/ \ / \ / \ / \
13 8 1 4 10 2 0 14
完全二叉樹：
如果刪除最底一層的所有葉子它就是滿二叉樹，即除了最后一層，每層節(jié)點都達到最大數(shù)量 ，即有深度k的個節(jié)點數(shù)在左閉右開【2^(k-1)+1,2^k-1】區(qū)間內(nèi)。（Complete Binary Tree）
________3______
/ \
___11___ __4__
/ \ / \
14 7 9 13
/ \ / \ /
2 5 8 6 1
完全二叉樹性質(zhì)：
1. 具有N個節(jié)點的完全二叉樹的深度為[log2 N]+1，其中[x]為高斯函數(shù)，截尾取整。
2. 如果對一棵有n個節(jié)點的完全二叉樹的節(jié)點按層序編號（從第一層到最后一層，每層從左到右），則對任一節(jié)點，有：
（1）如果i=1，則節(jié)點i是二叉樹的根，無雙親；如果i>1,則其雙親節(jié)點為[i/2]；
（2）如果2i>n，則節(jié)點i無左孩子；否則其左孩子是節(jié)點2i；
（3）如果2i+1>n，則節(jié)點i無右孩子；否則其右孩子是節(jié)點2i+1。
其他特殊二叉樹
排序二叉樹
二叉查找樹（Binary Search Tree），也稱二叉搜索樹或有序二叉樹
平衡二叉樹
左右子樹的高度差不大于1的二叉樹，且一定有：它的左、右子樹也都是平衡二叉樹（Self-Balancing Binary Search Tree）
退化樹
退化樹是每個節(jié)點都只有一個孩子的樹，孩子或左或右，或稱病態(tài)樹
斜二叉樹
一種特殊的退化樹，其中全部節(jié)點只有左孩子或右孩子，分別稱左斜二叉樹和右斜二叉樹，功能基本上退化到和鏈表一樣了
霍夫曼樹
帶權路徑最短的二叉樹稱為哈夫曼樹或最優(yōu)二叉樹
B樹
一種對讀寫操作進行優(yōu)化的自平衡的二叉樹查找，能夠保持數(shù)據(jù)有序，擁有多余兩個子樹
堆 heap
binary heap 是一種完全二叉樹，除了最底層的葉子節(jié)點之外，是填滿的；而且最底層的葉子節(jié)點從左至右是連續(xù)的，不得有空隙。最大堆（最小堆）就是最大（最?。┑耐耆鏄?。
二叉樹的遍歷
指如何按某種搜索路徑巡防樹中的每個結點，使得每個結點均被訪問一次，而且僅被訪問一次。
常見的遍歷方法有：先序遍歷，中序遍歷，后序遍歷，層序遍歷；一般都使用遞歸算法來實現(xiàn)。
以滿二叉樹為例：
_______1________
/ \
__2__ ___3___
/ \ / \
4 5 _6 _7
/ \ / \ / \ / \
8 9 10 11 12 13 14 15
先序遍歷
若二叉樹為空，為空操作；
否則（1）訪問根節(jié)點；（2）先序遍歷左子樹；（3）先序遍歷右子樹。
遍歷結果： 1 [2 [4 8 9] [5 10 11]] [3 [6 12 13] [7 14 15] “根左右”
中序遍歷
若二叉樹為空，為空操作；
否則（1）中序遍歷左子樹；（2）訪問根結點；（3）中序遍歷右子樹。
遍歷結果： [[8 4 9] 2 [10 5 11]] 1 [[12 6 13] 3 [14 7 15]] “左根右”
后序遍歷
若二叉樹為空，為空操作；
否則（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結點。
遍歷結果： [[8 9 4] [10 11 5] 2] [[12 13 6] [14 15 7] 3] 1 “左右根”
層序遍歷
若二叉樹為空，為空操作；否則從上到下、從左到右按層次進行訪問。
遍歷結果： 1 [2 3] [4 5 6 7] [8 9 10 11 12 13 14 15]
非滿二叉樹的遍歷結果：
________1________
/ \
__2___ ___3
/ \ / \
4 _5 6 7
\ / \ / \
9 10 11 12 15
先序：1 [2 [4 ' 9] [5 10 11]] [3 [6 12 '] [7 ' 15]]
中序：[' 4 9] 2 [10 5 11] 1 [12 6 '] 3 [' 7 15]
后序：[[' 9 4] [10 11 5] 2] [[12 ' 6] [' 15 7] 3] 1
層序：1 [2 3] [4 5 6 7] [' 9 10 11 12 ' ' 15]
注：結果中 ' 只是標記相對于滿二叉樹缺失的子節(jié)點，實際結果并不展現(xiàn)。
Python 實現(xiàn)二叉樹
用Python簡單實現(xiàn)如下二叉樹的遍歷功能，并列出層數(shù)和所有葉子：
______A______
/ \
__B__ __C__
/ \ / \
D E F G
/ \ / \ \ \
H I J K L M
代碼如下：
class Node():
def __init__(self, data=None, left=None, right=None):
self.data = data
self.left = left
self.right = right
def Preorder(self):
if self.data is not None:
print(self.data, end=' ')
if self.left is not None:
self.left.Preorder()
if self.right is not None:
self.right.Preorder()
def Inorder(self):
if self.left is not None:
self.left.Inorder()
if self.data is not None:
print(self.data, end=' ')
if self.right is not None:
self.right.Inorder()
def Postorder(self):
if self.left is not None:
self.left.Postorder()
if self.right is not None:
self.right.Postorder()
if self.data is not None:
print(self.data, end=' ')
def Height(self):
if self.data is None:
return 0
elif not any([self.left, self.right]):
return 1
elif all([not self.left, self.right]):
return self.right.Height()+1
elif all([self.left, not self.right]):
return self.left.Height()+1
else:
return max(self.left.Height(), self.right.Height())+1
def Leaves(self):
if self.data is None:
return None
elif not any([self.left, self.right]):
print(self.data, end=' ')
elif all([not self.left, self.right]):
self.right.Leaves()
elif all([self.left, not self.right]):
self.left.Leaves()
else:
self.left.Leaves()
self.right.Leaves()
bt = Node('A')
bt.left = Node('B')
bt.right = Node('C')
bt.left.left = Node('D')
bt.left.right = Node('E')
bt.right.left = Node('F')
bt.right.right = Node('G')
bt.left.left.left = Node('H')
bt.left.left.right = Node('I')
bt.left.right.left = Node('J')
bt.left.right.right = Node('K')
bt.right.left.right = Node('L')
bt.right.right.right = Node('M')
print('Perorder:')
bt.Preorder()
print('\nInorder:')
bt.Inorder()
print('\nPostorder:')
bt.Postorder()
print('\nTree Height:\n',bt.Height())
print('\nLeaves:')
bt.Leaves()運行結果：
Perorder:
A B D H I E J K C F L G M
Inorder:
H D I B J E K A F L C G M
Postorder:
H I D J K E B L F M G C A
Tree Height: # 實為層數(shù)，相當于樓房高度地面一層從0計算高度
4
Leaves:
H I J K L M
要實現(xiàn)二叉樹完整的所有功能，代碼肯定巨長無比。還是找一個優(yōu)秀的第三方庫比較明智?。?！
二叉樹第三方庫 binarytree
使用環(huán)境與安裝
Requirements: Python 3.6+
Installation:
> pip install binarytreeFor conda users:
> conda install binarytree -c conda-forge
簡單實例
binarytree.Node() 二叉樹節(jié)點
from binarytree import Node root = Node(1) root.left = Node(2) root.right = Node(3) root.left.right = Node(4) print(root) # 或者： root.pprint() # # __1 # / \ # 2 3 # \ # 4 #
binarytree.tree() 隨機二叉樹
from binarytree import tree bt = tree(is_perfect=True) bt.pprint() # # _______14______ # / \ # ___13__ __8__ # / \ / \ # _9 0 6 3 # / \ / \ / \ / \ # 10 12 5 7 4 2 1 11 #
下一篇準備實戰(zhàn)這個第三方庫 binarytree ！
本文的續(xù)篇來了，請點以下鏈接：
總結
到此這篇關于Python二叉樹初識的文章就介紹到這了,更多相關Python二叉樹初識內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
Python動態(tài)導入模塊：__import__、importlib、動態(tài)導入的使用場景實例分析
這篇文章主要介紹了Python動態(tài)導入模塊：__import__、importlib、動態(tài)導入的使用場景,結合實例形式分析了Python動態(tài)導入模塊__import__、importlib基本概念、原理及動態(tài)導入的具體應用操作技巧,需要的朋友可以參考下2020-03-03
這篇文章主要介紹了Python基于numpy模塊實現(xiàn)回歸預測,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-05-05
這篇文章主要介紹了Python如何讀取、寫入JSON數(shù)據(jù)，文中講解非常細致，代碼幫助大家更好的理解和學習，感興趣的朋友可以了解下2020-07-07
這篇文章主要介紹了Python3中對range()逆序的解釋，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-05-05
Python是一門與php有點像的編輯語言了，下文來給各位在利用Python實現(xiàn)進度條了,對Python在Console下顯示文本進度條的方法相關知識感興趣的朋友一起學習吧2016-02-02
python中Tkinter 窗口之輸入框和文本框的實現(xiàn)
這篇文章主要介紹了python中Tkinter 窗口之輸入框和文本框的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-04-04
Python中的yeild關鍵字提高代碼執(zhí)行效率場景實例探究
在Python編程語言中,yeild是一個非常實用的關鍵字,它不僅可以幫助你編寫更加簡潔的代碼,還可以提高代碼的執(zhí)行效率,本文將詳細介紹yeild在Python中的使用方法,并通過示例代碼進行演示,讓我們一起來探索這個強大的關鍵字吧2024-01-01
web應用難免會截取字符串的需求,Python中截取英文很容易，但是截取utf-8的中文機會截取一半導致一些不是亂碼的亂碼.其實utf8截取很簡單,這里記下來分享給大家2015-06-06
python:刪除離群值操作(每一行為一類數(shù)據(jù))
這篇文章主要介紹了python:刪除離群值操作(每一行為一類數(shù)據(jù))，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-06-06
Python實現(xiàn)過濾單個Android程序日志腳本分享
這篇文章主要介紹了Python實現(xiàn)過濾單個Android程序日志腳本分享,本文講解了原理、實現(xiàn)代碼、使用方法、最新代碼等內(nèi)容,需要的朋友可以參考下2015-01-01