資料結構與演算法之樹形結構
二叉樹
二叉樹的節點的節點定義
在堆排序時曾經介紹了什麼是二叉樹,當時是用列表來實現的,但是二叉樹可能出現空值,浪費空間,所以使用類似連結串列的儲存結構。
class BiTreeNode: def __init__(self,data): self.data=data self.lchild=None self.rchild=Node
二叉樹的遍歷
二叉樹的遍歷有兩類四種:
- 深度優先:前序遍歷,中序遍歷,後序遍歷。
- 對於有兩個遍歷求二叉樹的方法:前序找根節點(根在前面),中序找左右子樹,後序找根節點(根在後面)
#前序遍歷,root為根節點 def pre_order(root): if root: print(root.data,end = '') pre_order(root.lchild) pre_order(root.rchild) #中序遍歷,如果lchild沒值則出棧 def in_order(root): if root: pre_order(root.lchild) print(root.data,end = '') pre_order(root.rchild) #後序遍歷,如果rchild沒值則出棧 def post_order(root): if root: pre_order(root.lchild) pre_order(root.rchild) print(root.data,end = '')
- 廣度優先:層次遍歷
#根據佇列實現 def level_order(root): q=deque() q.append(root) while(len(q)>0): x=q.popleft() print(x.data,end='') if x.lchild(): q.append(x.lchild) if x.rchild(): q.append(x.rchild)
二叉搜尋樹
相關知識點
二叉搜尋樹,也叫二叉排序樹,它要求每一個節點左子樹的節點都比它小,右子樹的節點都比他大。
- 二叉搜尋樹的遍歷是升序序列
- 如果y是x左子樹的一個節點,那麼y.key <=x.key;
- 如果y是x右子樹的一個節點,那麼y.key >= x.key;
二叉搜尋樹的插入
class BST: def __init__(self): self.root=None#空不是根節點 而是None def insert(self,key): if not self.root: self.root = BiTreeNode(key) else: p=self.root while p: if key < p.data:#分為左子樹是否為空的情況 if p.lchild:#左子樹有節點就在左子樹繼續查詢,否則就插入左節點的位置 p = p.lchild else: p.lchild = BiTreeNode(key) if key < p.data:#分為左子樹是否為空的情況 elif key > p.data: if p.rchild: p = p.rchild else: p.lchild = BiTreeNode(key) break else: break
二叉搜尋樹的查詢
def query(self,key): p = self.root while p : if key < p.data: p = p.lchild elif key >p.data: p=p.rchild else: return True return False
二叉搜尋樹的刪除
刪除有三種情況:
- 如果要刪除的節點是葉子節點,那麼找到後直接刪除。
- 如果要刪除的節點有一個子節點點,將 此節點的父節點和子節點相連線,然後刪除此節點。
- 如果刪除的節點有兩個子節點,找到其左子樹最大的節點或者右子樹的最小節點,刪除並替換當前節點,若最後一個一個節點還有一個右子節點,那麼再按照第二種情況處理。
二叉搜尋樹的效率和AVL樹
平均情況下,二叉搜尋時的時間複雜度為O(logn),但是二叉搜尋樹可能會出現偏斜的情況,需要採用隨機打亂的方法,所以這時候採用AVL樹(自動平衡樹)。
相關知識點:
AVL樹:AVL樹是一棵自平衡的二叉搜尋樹,它具有以下性質:
-
根的左右子樹高度之差的絕對值不能超過1.
- 計算方法:
- 每個節點的左右子樹的深度之差,也就是平衡因子。
- 根的左右子樹都是平衡二叉樹。
AVL樹的插入操作
插入一個節點可能會造成AVL樹的不平衡,可以通過旋轉操作來修正。
插入一個節點後,只有從插入節點到根節點的路徑上的節點的平衡可能被改變,需要找到第一個平衡條件的節點,稱之為K,K的兩棵子樹高度差肯定為2.
不平衡的出現有四種情況:
- 不平衡是由於對K的右子節點的右子樹插入導致的:左旋。
- 不平衡是由於對K的左子節點的左子樹插入導致的:右旋。
- 不平衡是由於右子節點的左子樹插入導致的:右旋->左旋。
- 不平衡是由於左子節點的右子樹插入導致的:左旋->右旋。
B樹
B-Tree是一種自平衡的多路搜尋樹,B-Tree儲存在硬盤裡,用於資料庫的索引。