??上一節我們學習了資料結構里面的各種排序演算法，今天，我們接著學習資料結構中又一重要的結構：樹，對往期內容感興趣的小伙伴可以參考下面內容👇:

• python資料型別: python資料結構之資料型別.
• python的輸入輸出: python資料結構之輸入輸出、控制和例外.
• python資料結構之面向物件: python資料結構之面向物件.
• python資料結構之演算法分析: python資料結構之演算法分析.
• python資料結構之堆疊、佇列和雙端佇列: python資料結構之堆疊、佇列和雙端佇列.
• python資料結構之遞回: python資料結構之遞回.
• python資料結構之搜索: python資料結構之搜索.
• python資料結構之排序: python資料結構之排序.

🌵資料結構中所說的‘樹’，一般都是指二叉樹，許多實際問題抽象出來的資料結構往往是二叉樹形式，即使是一般的樹也能簡單地轉換為二叉樹，而且二叉樹的存盤結構及其演算法都較為簡單，因此二叉樹顯得特別重要，

1.初識樹

樹結構在我們生活中很常見，我們舉一些例子：

從樹的頂部開始，沿著由橢圓和箭頭構成的路徑，一直到底部，一個節點的所有子節點都與另一個節點的所有子節點無關，葉子節點都是獨一無二，

2.樹的術語及定義

2.1 樹的術語

先介紹樹的一些術語：

• 節點：節點是樹的基礎部分，它可以有自己的名字，我們稱作“鍵”，節點也可以帶有附加資訊，我們稱作“有效載荷”，有效載荷資訊對于很多樹演算法來說不是重點，但它常常在使用樹的應用中很重要，
• 邊：邊是樹的另一個基礎部分，兩個節點通過一條邊相連，表示它們之間存在關系，除了根節點以外，其他每個節點都僅有一條入邊，出邊則可能有多條，
• 根節點：根節點是樹中唯一沒有入邊的節點（樹的啟始節點）
• 路徑：路徑是由邊連接的有序節點串列，比如，哺乳綱→食肉目→貓科→貓屬
• 子節點：一個節點通過出邊與子節點相連，
• 父節點 ：一個節點是其所有子節點的父節點，
• 兄弟節點 ：具有同一父節點的節點互稱為兄弟節點，
• 子樹：一個父節點及其所有后代的節點和邊構成一棵子樹，
• 葉子節點 ：葉子節點沒有子節點，
• 層數：節點 n 的層數是從根節點到 n 的唯一路徑長度，
• 高度 ：樹的高度是其中節點層數的最大值，

2.2 樹的定義

樹的定義有兩種：

第一種：

• 有一個根節
• 除根節點外，其他每個節點都與其唯一的父節點相連
• 從根節點到其他每個節點都有且僅有一條路徑
• 如果每個節點最多有兩個子節點，我們就稱這樣的樹為二叉樹

第二種：
一棵樹要么為空，要么由一個根節點和零棵或多棵子樹構成，子樹本身也是一棵樹， 每棵子樹的根節點通過一條邊連到父樹的根節點，從樹的遞回定義可知，圖中的樹至少有 4 個節點，因為三角形代表的子樹必定有一個根節點，這棵樹或許有更多 的節點，但必須更深入地查看子樹后才能確定，

3. 樹的實作

3.1 串列實作法

樹的根節點是 myTree[0]，左子樹是 myTree[1]，右子樹是 myTree[2]
表示方法如下：

#樹
mytree=['a',['b',['d',[],[]],['e',[],[]]],['c',['f',[],[]],[]]]
#左子樹
mytree[1]
#右子樹
mytree[2]

創建樹的函式

def binarytree(r):#創建一顆以r為根節點的樹
    return [r,[],[]]
def insertleftree(root,newbr):#向左節點插入一棵樹
    t=root.pop(1)
    if len(t)>1:
        root.insert(1,[newbr,t,[]])
    else:
        root.insert(1,[newbr,[],[]])
    return root
def insertrighttree(root,newbr):#向右節點插入一顆樹
    t=root.pop(2)
    if len(t)>1:
        root.insert(2,[t,newbr,[]])
    else:
        root.insert(2,[t,newbr,[]])
    return root
def getlefttree(r):#獲取左子樹
    return r[1]
def getrighttree(r):#獲取右子樹
    return r[2]

3.2 面向物件法

利用節點與參考，我們將定義一個類，其中有根節點和左右子樹的屬性， 這種表示法遵循面向物件編程范式，結構如下：

樹的實作

class binarytree2:
        def __init__(self,key):
            self.root=key
            self.left=None
            self.right=None
        def insertleft(self,nbran):#插入左節點
            if self.left ==None:
                self.left=binarytree2(nbran)
            else:
                t=binarytree2(nbran)
                t.left=self.left
                self.left=t
        def insertright(self,nbran):#插入右節點
            if self.right==None:
                self.right=binarytree2(nbran)
            else:
                t=binarytree2(nbran)
                t.right=self.right
                self.right=t
        def getrighttree(self):#獲取右子樹
            return self.right
        def getlefttree(self):#獲取左子樹
            return self.left
        def gettreeroot(self):#獲取根節點
            return self.root

4. 二叉樹的應用

4.1 決議樹

樹的實作已經齊全了，現在來看看如何用樹解決一些實際問題，這里介紹決議樹，可以用它 來表示現實世界中像句子或數學運算式這樣的構造，

構建決議樹的第一步是將運算式字串拆分成標記串列，需要考慮 4 種標記：左括號、右括號、運算子和運算元，我們知道，左括號代表新運算式的起點，所以應該創建一棵對應該運算式的新樹，反之，遇到右括號則意味著到達該運算式的終點，我們也知道，運算元既是葉子節點，也是其運算子的子節點，此外，每個運算子都有左右子節點，規則如下：

• 如果當前標記是(，就為當前節點添加一個左子節點，并下沉至該子節點；
• 如果當前標記在串列[’+’, ‘-’, ‘/’, ‘*’]中，就將當前節點的值設為當前標記對應的運算子；為當前節點添加一個右子節點，并下沉至該子節點；
• 如果當前標記是數字，就將當前節點的值設為這個數并回傳至父節點；
• 如果當前標記是)，就跳到當前節點的父節點，

決議樹實作方式

rom pythonds.basic import Stack
from pythonds.trees import BinaryTree
def buildParseTree(teststring):#決議樹創建
    str=teststring.split()#將字串拆分
    pstack=Stack()#創建一個堆疊，方便訪問樹節點
    etree=BinaryTree('')#創建樹
    pstack.push(etree) #將樹壓入堆疊中
    currenttree = etree 
    for i in str: #依次判斷每個字符所屬情況
        if i == '(': 
            currenttree.insertLeft('') 
            pstack.push(currenttree) 
            currenttree = currenttree.getLeftChild()
        elif i in ['+','-','/','*']:#是運算子，創建右節點
            currenttree.setRootVal(i)
            currenttree.insertRight('')
            pstack.push(currenttree)
            currenttree=currenttree.getRightChild()
        elif i not in ['+','-','/','*',')']:#是數字設定該節點的值
            currenttree.setRootVal(eval(i))
            currenttree=pstack.pop()
        elif i ==')':
            currenttree = pstack.pop() 
        else:
             raise ValueError("Unknown Operator: " + i) 
    return etree

可通過如下呼叫：

4.2 樹的遍歷

樹是創建好了，可是怎么遍歷樹呢？按節點的訪問方式分為 3 種，我們將對所有節點的訪問稱為“遍歷”，共有 3 種遍歷方式，分別為前序遍歷、中序遍歷和后序遍歷，

• 前序遍歷：在前序遍歷中，先訪問根節點，然后遞回地前序遍歷左子樹，最后遞回地前序遍歷右子樹，
• 中序遍歷：在中序遍歷中，先遞回地中序遍歷左子樹，然后訪問根節點，最后遞回地中序遍歷右子樹，
• 后序遍歷：在后序遍歷中，先遞回地后序遍歷右子樹，然后遞回地后序遍歷左子樹，最后訪問根節，

三種遍歷方式

#前序遍歷
def preorder(tree): 
    if tree: 
        print(tree.getRootVal()) 
        preorder(tree.getLeftChild()) 
        preorder(tree.getRightChild())

#中序遍歷
def inorder(tree): 
    if tree != None: 
        inorder(tree.getLeftChild()) 
        print(tree.getRootVal()) 
        inorder(tree.getRightChild())


#后序遍歷
def postorder(tree): 
    if tree != None: 
        inorder(tree.getLeftChild())  
        inorder(tree.getRightChild())
        print(tree.getRootVal())

效果如下：

5. 參考書籍

《python資料結構與演算法》
《大話資料結構》