用Python實現資料結構之樹
樹
樹是由根結點和若干顆子樹構成的。樹是由一個集合以及在該集合上定義的一種關係構成的。集合中的元素稱為樹的結點,所定義的關係稱為父子關係。父子關係在樹的結點之間建立了一個層次結構。在這種層次結構中有一個結點具有特殊的地位,這個結點稱為該樹的根結點,或稱為樹根。
相關概念
-
根節點:樹中最頂部的元素
-
父節點:處了根節點都有父節點,每個節點最多隻有一個父節點
-
孩子節點:一個父節點具有0個或多個孩子節點
-
兄弟節點:同一個父節點的孩子節點之間是兄弟關係
-
外部節點:一個沒有孩子的節點稱為外部節點,也叫葉子結點
-
內部節點:有一個或多個孩子節點的節點叫做內部節點
-
樹的邊:指一對節點(u,v),其中u是v的父節點或者v是u的父節點
-
樹的路徑:一系列連續的邊組成了一條路徑
-
節點的深度:節點的深度就是該節點的祖先的個數,不包括該節點本身,如果根節點的層數為1,則深度即為該節點的層數-1
-
節點的高度:如果p是樹中的葉子節點,那麼它的高度為0.否則p的高度是它的孩子節點中的最大高度+1
-
有序樹:每個孩子之間有一定的順序,例如:
一個樹的抽象基類
class Tree(): """ 樹的抽象基類 """ # 叫做位置的內嵌類,用於封裝節點 class Position(): def element(self): raise NotImplementedError('must be implemented by subclass') def __eq__(self, other): raise NotImplementedError('must be implemented by subclass') def root(self): """ return 根節點的position """ raise NotImplementedError('must be implemented by subclass') def parent(self,p): """ :param p:一個位置物件 :return: 返回p的父節點的position物件,如果p是根節點則飯後空 """ raise NotImplementedError('must be implemented by subclass') def num_children(self,p): """ :param p:一個位置物件 :return: 返回該位置的孩子節點的數量 """ raise NotImplementedError('must be implemented by subclass') def children(self,p): """ :param p: 一個位置物件 :return: 返回位置p的孩子的迭代 """ raise NotImplementedError('must be implemented by subclass') def __len__(self): """ :return: 返回整個樹的節點個數 """ raise NotImplementedError('must be implemented by subclass') def is_root(self,p): return self.root() == p def is_leaf(self,p): return self.num_children(p) == 0 def is_empty(self): return len(self) == 0
這個抽象類中的方法必須在子類中實現才能呼叫,不然會產生NotImplementedError(‘must be implemented by subclass’)的異常
除此之外,對於Position()這個內嵌類可能較難理解,為什麼要有這麼一個內嵌類
這個內嵌類目前也是抽象類,具體方法都沒有實現,但使用它的目的已經有了,就是將樹中的節點進行封裝,那為什麼要封裝節點呢?當呼叫樹的相關方法時,節點可能為一個必要的引數,但我們手動傳入時,實際上可以是任意的物件,這就會導致錯誤發生,所以我們必須保證傳入的節點是節點的物件,同時也是本樹物件的節點,不然就會弄混樹與樹的節點。同時將節點進行封裝,可以避免使用者直接使用節點物件本身,相關節點的方法可以在封裝成的Position物件呼叫。目前只是抽象類的定義,節點類等其他方法還未定義,後面還會看到具體的position物件的使用。
目前有了Tree這個抽象類,雖然其中的大多數方法還是抽象方法,但使用這些方法已經可以構成一些其他的功能了,所以就有了is_root,is_leaf,is_empty方法的定義。同時還可以定義計算節點的深度與高度的方法:
def depth(self,p): """ 計算節點在樹中的深度 """ if self.is_root(p): return 0 else: return 1 + self.depth(self.parent(p)) def height(self,p): """ 計算節點在樹中的深度 """ if self.is_leaf(p): return 0 else: return 1 + max(self.height(c) for c in self.children(p))
二叉樹
我們現在介紹一種樹的特殊化形式二叉樹
二叉樹的特點:
-
每個父節點最多隻有兩個孩子節點
-
兩個孩子節點又叫做左孩子和右孩子
-
以左孩子為根節點形成的樹叫做左子樹,以右孩子為根節點形成的樹叫做右子樹
-
如果每個非葉子節點都有兩個孩子,那麼這個樹就叫做完全二叉樹
-
非空完全二叉樹中,外部節點數=內部節點數+1
二叉樹的實現可以以繼承樹的抽象類的方式實現:
class BinaryTree(Tree): class Node(): def __init__(self, element, parent=None, left=None, right=None): self.element = element self.parent = parent self.left = left self.right = right class Position(Tree.Position): def __init__(self, container, node): self.container = container self.node = node def element(self): return self.node.element def __eq__(self, other): return isinstance(other, type(self)) and other.node is self.node def validate(self, p): """ 進行位置驗證 """ if not isinstance(p, self.Position): raise TypeError('p must be proper Position type') if p.container is not self: raise ValueError('p does not belong to this container') if p.node.parent is p.node: raise ValueError('p is no longer valid') return p.node def make_position(self, node): """ 封裝節點 """ return self.Position(self, node) if node is not None else None def __init__(self): self.root = None self.size = 0 def __len__(self): return self.size def root(self): return self.make_position(self.root) def parent(self, p): node = self.validate(p) return self.make_position(node.parent) def left(self, p): node = self.validate(p) return self.make_position(node.left) def right(self, p): node = self.validate(p) return self.make_position(node.right) def sibling(self, p): parent = self.parent(p) if parent is None: return None else: if p == self.left(parent): return self.right(parent) else: return self.left(parent) def num_children(self, p): node = self.validate(p) count = 0 if node.left is not None: count += 1 if node.right is not None: count += 1 return count def children(self,p): if self.left(p) is not None: yield self.left(p) if self.right(p) is not None: yield self.right(p)
程式碼中將之前的抽象方法進行了完整的定義,同時添加了validate與make_position方法。validate方法用於對傳入的position引數進行驗證,make_position方法用於將節點進行封裝。除此之外還添加了二叉樹特有的方法right,left和sibling,left與right分別返回節點的左孩子節點與右孩子節點,sibling返回的是節點的兄弟節點。
目前的二叉樹的資料結構只是建立了一顆空樹,我們接下來要加入的是對二叉樹進行更新操作的方法
def add_root(self, e): if self.root is not None: raise ValueError('Root exists') self.size += 1 self.root = self.Node(e) return self.make_position(self.root) def add_left(self, e, p): node = self.validate(p) if node.left is not None: raise ValueError('Left child exists') self.size += 1 node.left = self.Node(e, node) return self.make_position(node.left) def add_right(self, e, p): node = self.validate(p) if node.right is not None: raise ValueError('Left child exists') self.size += 1 node.right = self.Node(e, node) return self.make_position(node.right) def replace(self, p, e): node = self.validate(p) old = node.element node.element = e return old def delete(self, p): """ 刪除該位置的節點,如果該節點有兩個孩子,則會產生異常,如果只有一個孩子, 則使其孩子代替該節點與其雙親節點連線 """ node = self.validate(p) if self.num_children(p) == 2: raise ValueError('p has two children') child = node.left if node.left else node.right if child is not None: child.parent = node.parent if node is self.root: self.root = child else: parent = node.parent if node is parent.left: parent.left = child else: parent.right = child self.size -= 1 node.parent = node return node.element
總共加入了新增根節點,新增左孩子,新增右孩子,代替元素和刪除節點5個方法,其中刪除幾點稍微有一些複雜,因為涉及到許多情況的判斷。
到現在,一個完整的二叉樹資料結構基本完成了。
但是我們還需要掌握一個演算法,就是樹的遍歷演算法
樹的遍歷
樹的遍歷一般有先序遍歷,後序遍歷,廣度優先遍歷(層序遍歷),對於二叉樹還有中序遍歷
先序遍歷
先序遍歷是按照根節點->從左到右的孩子節點的順序遍歷,而且把每個孩子節點看作是子樹的根節點同樣如此,例如:
用python實現先序遍歷為:
def preorder(self,p): """ 先序遍歷節點p為根節點的樹 """ yield p for c in self.children(p): for other in self.preorder(c): yield other
雖然程式碼只有4行,但理解起來卻不是很容易的,首先該方法是一個生成器,所以通過yield返回一個可迭代物件,也就是可以for迴圈該方法,由於是先序遍歷,所以要先yield p,之後便要返回孩子節點,由於孩子節點可能還具有孩子,所以並不能只返回孩子節點,應該返回以孩子節點為根節點的樹的所有節點,而要想for迴圈得到左右的孩子節點為根節點的所有節點,還需要呼叫孩子節點的先序遍歷方法才能得到。總而言之,程式碼理解的難度還是由於遞迴演算法造成的,一個複雜的遞迴終歸還是不是那麼容易就能看出來的。
後序遍歷
後序遍歷是按照先從左到右孩子節點->根節點,如圖:
用python實現:
def postorder(self,p): """ 後序遍歷節點p為根的樹 """ for c in self.children(p): for other in self.postorder(c): yield other yield p
理解與先序遍歷相同
廣度優先遍歷
廣度優先遍歷也叫層序遍歷,一層一層的遍歷,如圖:
用python實現:
def breadthfirst(self): if not self.is_empty(): queue = Queue() queue.enqueue(self.root()) while not queue.is_empty(): p = queue.dequeue() yield p for i in self.children(p): queue.enqueue(i)
中序遍歷二叉樹
對於二叉樹,遍歷順序為左孩子->父節點->右孩子
python實現為:
def inorder(self,p): if self.left(p) is not None: for other in self.inorder(self.left(p)): yield other if self.right(p) is not None: for other in self.inorder(self.right(p)): yield other
參考《資料結構與演算法Python語言實現》