python-樹與二叉樹

樹與二叉樹

如果你了解linux檔案結構(tree指令),它的結構也是一棵樹。我們快速看下樹涉及到的一些概念:

二叉樹

了解完樹的結構以後，我們來看樹結構裡一種簡單但是卻比較常用的數-二叉樹。二叉樹是一種簡單的樹，它的每個節點最多隻能包含兩個孩子，以下都是一些合法的二叉樹:

通過上邊這幅圖再來看幾個二叉樹相關的概念:

1.節點深度(depth):節點對應的level數字

2.樹的高度(height):二叉樹的高度就是level數+1,因為level從0開始計算的

3.樹的寬度(width):二叉樹的寬度指的是包含最多節點的層級的節點數

4.樹的size:二叉樹的節點總個數

一些特殊的二叉樹

滿二叉樹(full binary tree)

如果每個内部節點(非葉節點)都包含兩個孩子，就成為滿二叉樹。下邊是一些例子，它可以有多種形狀:

完美二叉樹(perfect binary tree)

當所有的葉子節點都在同一層就是完美二叉樹，毫無間隙填充了h層

完全二叉樹(complete binary tree)

當一個高度為h的完美二叉樹減少到h-1,并且最底層的槽被毫無間隙地從左到右填充，我們就叫它完全二叉樹。下圖就是完全二叉樹的例子:

二叉樹的表示

說了那麼多，那麼怎麼表示一棵二叉樹呢？其實你發現會和連結清單有一些相似之處，

一個節點，然後節點需要儲存孩子的指針，

我以構造下邊這個二叉樹為例子:我們先定義一個類表示節點:

# -*- coding:utf-8 -*-

class BinTreeNode(object):
    def __init__(self,data,left=None,right=None):
        self.data,self.left,self.right = data,left,right

'''
    當然和連結清單類似，root 節點是我們的入口，于是乎定義一個二叉樹

class BinTree(object):
    def __init__(self,root=None):
        self.root = root
'''



'''
    怎麼構造上圖的二叉樹呢，我自己定義了一種方法,
    首先我們輸入節點資訊，仔細看下邊代碼，
    葉子節點的left和right都是None,并且隻有一個根節點A:
'''

node_list = [
    {'data':'A','left':'B', 'right':'C', 'is_root':True},
    {'data':'B','left':'D', 'right':'E', 'is_root':False},
    {'data':'D','left':None,'right':None,'is_root':False},
    {'data':'E','left':'H', 'right':None,'is_root':False},
    {'data':'H','left':None,'right':None,'is_root':False},
    {'data':'C','left':'F', 'right':'G', 'is_root':False},
    {'data':'F','left':None,'right':None,'is_root':False},
    {'data':'G','left':'I', 'right':'J', 'is_root':False},
    {'data':'I','left':None,'right':None,'is_root':False},
    {'data':'J','left':None,'right':None,'is_root':False},

]

#然後我們給BinTreeNode定義一個 build_from 方法:

class BinTree(object):
    def __init__(self,root=None):
        self.root = root

    @classmethod
    def build_from(cls,node_list):
        '''
            通過節點資訊構造二叉樹
            第一次周遊我們構造 node 節點
            第二次周遊我們給root和孩子指派
            最後我們用 root 初始化這個類并傳回一個對象

            param node_list:{'data':'A','left':None,'right':None,
            'is_root':False}
        '''

        node_dict = {}
        for node_data in node_list:
            data = node_data['data']
            node_dict[data] = BinTreeNode(data)
        for node_data in node_list:
            data = node_data['data']
            node = node_dict[data]
            if node_data['is_root']:
                root = node
            node.left = node_dict.get(node_data['left'])
            node.right = node_dict.get(node_data['right'])

        return cls(root)

btree = BinTree.build_from(node_list)
           

二叉樹的周遊

不知道你有沒有發現,二叉樹其實是一種遞歸結構,

因為單獨拿出來一個subtree子樹出來,其實它還是一棵樹。

那周遊它就很友善了，我們可以直接用遞歸的方式來周遊它。

但是當處理順序不同的時候，樹又分為三種周遊方式:

1.先(根)序周遊:先處理根，之後是左子樹，然後是右子樹

2.中(根)序周遊:先處理左子樹，之後是根，最後是右子樹

3.後(根)序周遊:先處理左子樹，之後是右子樹，最後是根

我們來實作一下:

# -*- coding:utf-8 -*-

class BinTreeNode(object):
    def __init__(self,data,left=None,right=None):
        self.data,self.left,self.right = data,left,right

class BinTree(object):
    def __init__(self,root=None):
        self.root = root

    '''
        在def前面加上@classmethod，這種類方法的一個特點就是可以通過類名去調用，
        但是也必須傳遞一個參數，一般用cls表示class，表示可以通過類直接調用
    '''
    @classmethod
    def build_from(cls,node_list):
        '''
            通過節點資訊構造二叉樹
            第一次周遊我們構造 node 節點
            第二次周遊我們給root和孩子指派
            最後我們用 root 初始化這個類并傳回一個對象

            param node_list:{'data':'A','left':None,'right':None,
            'is_root':False}
        '''

        node_dict = {}
        for node_data in node_list:
            data = node_data['data']
            node_dict[data] = BinTreeNode(data)
        for node_data in node_list:
            data = node_data['data']
            node = node_dict[data]
            if node_data['is_root']:
                root = node
            node.left = node_dict.get(node_data['left'])
            node.right = node_dict.get(node_data['right'])

        return cls(root)

    def preorder_trav(self,subtree):
        '''
            先(根)序周遊
        '''
        if subtree is not None:
            print(subtree.data)         #遞歸函數裡先處理根
            self.preorder_trav(subtree.left)    #遞歸處理左子樹
            self.preorder_trav(subtree.right)   #遞歸處理右子樹

node_list = [
    {'data':'A','left':'B', 'right':'C', 'is_root':True},
    {'data':'B','left':'D', 'right':'E', 'is_root':False},
    {'data':'D','left':None,'right':None,'is_root':False},
    {'data':'E','left':'H', 'right':None,'is_root':False},
    {'data':'H','left':None,'right':None,'is_root':False},
    {'data':'C','left':'F', 'right':'G', 'is_root':False},
    {'data':'F','left':None,'right':None,'is_root':False},
    {'data':'G','left':'I', 'right':'J', 'is_root':False},
    {'data':'I','left':None,'right':None,'is_root':False},
    {'data':'J','left':None,'right':None,'is_root':False},

]
btree = BinTree.build_from(node_list)
btree.preorder_trav(btree.root)     #輸出 A,B,D,E,H,C,F,G,I,J
           

先(根)序周遊

先周遊左子樹，再周遊右子樹

反轉二叉樹