打牢地基-二叉樹、BST
- 2020 年 4 月 8 日
- 筆記
章節
- tree結構簡介
- 二叉樹詳解
- 二分搜索樹 – Binary Search Tree
1 tree結構簡介
tree-簡介
tree 是非線性數據結構tree 是高效的
tree-高效性
2 二叉樹詳解
重新認識下tree
1. 和鏈表一樣，動態的數據結構 class Node { E e; Node left; Node right; } 2. 二叉樹具有唯一根節點 3. 二叉樹中每個節點最多有兩個孩子 - 左孩子 or 右孩子 4. 1個孩子都沒有的節點叫葉子節點 5. 二叉樹每個節點最多有一個父節點 6. 根節點沒有父節點 7. 二叉樹具有比鏈表更明顯的遞歸屬性
二叉樹的天然遞歸屬性
一個節點有n個分叉- n叉樹
滿二叉樹
定義: 除了葉子節點，每個節點都有兩個孩子節點
二叉樹不一定是滿二叉樹
3 二分搜索樹 – Binary Search Tree
1. 二分搜索樹是二叉樹 2. 二分搜索樹每個節點的值: 大於其左子樹所有節點的值 小於其右子樹所有節點的值 左子樹(all node val) < cur node val < 右子樹(all node val) 3. 每一棵子樹也是二分搜索樹
二分搜索樹-BTS 加速查詢過程的原因，假如根節點val = 28, 現在在查找 30 這個元素，因為BTS的存儲特性，只需要查找右子樹部分就可以了，大大提高了查詢的速度 有個細節，需要保證node的val 是可比較的，這是有局限性的
3.1 定義樹中節點-struct
class Node: def __init__(self, e=None, left=None, right=None): self.e = e self.left = left self.right = right
節點結構體中 包含數據域 e, 左子樹引用 left， 右子樹引用right
3.2 定義BTS
class BST: def __init__(self, root: Node = None): """ 根節點 :param root: """ self._root = root self._size = 0
一棵樹包包含一個根節點root，以及node的個數 size
3.3 add(e)-遞歸新增一個節點數據
def add(self, e): self._root = self._add_element(self._root, e) def _add_element(self, root, e): """ 遞歸構建二分搜索樹 :param root: :param e: :return: """ if root is None: self._size += 1 """ 返回的是子樹根節點 """ return Node(e) elif e < root.e: root.left = self._add_element(root.left, e) elif e > root.e: root.right = self._add_element(root.right, e) return root
3.4 contains- 遞歸查詢樹中是否包含某個數據
def contains(self, e): return self._contains(self._root, e) def _contains(self, _root, e): if self._root is None: return False if self._root.e == e: return True if e < self._root.e: return self._contains(self._root.left, e) if e > self._root.e: return self._contains(self._root.right, e)
3.5 二分搜索樹的遍歷
3.5.1 前序遍歷 – 遞歸
def pre_order(self): """ 前序遍歷 :return: """ self._pre_order(self._root) def _pre_order(self, node): if node is None: return print(node.e) self._pre_order(node.left) self._pre_order(node.right)
3.5.2 中序遍歷-遞歸
def in_order(self): """ 中序遍歷，即是二分搜索樹從小到達排序的數據 :return: """ self._in_order(self._root) def _in_order(self, node): if node is None: return self._in_order(node.left) print(node.e) self._in_order(node.right)
3.5.3 後序遍歷 post_order – 遞歸
def post_order(self): """ 後續遍歷 :return: """ self._post_order(self._root) def _post_order(self, node): if node is None: return self._post_order(node.left) self._post_order(node.right) print(node.e)
3.5.4 前序遍歷 – 非遞歸算法(棧的應用)- DFS 深度優先遍歷
LinkedListStack-使用先前實現的鏈表棧
def pre_order_nr(self): """ 前序遍歷-非遞歸，使用棧 :return: """ stack = LinkedListStack() stack.push(self._root) while stack.is_empty() is False: cur = stack.pop() print(cur.e) if cur.right is not None: stack.push(cur.right) if cur.left is not None: stack.push(cur.left)
3.5.5 二分搜索樹的層序遍歷-(隊列的應用) BFS (Breadth First Search)
LinkedListQueue-使用先前實現的鏈表隊列實現層序遍歷
def level_order(self): """ 隊列實現中序遍歷 - 先進先出 :return: """ queue = LinkedListQueue() queue.enqueue(self._root) while queue.is_empty() is False: cur = queue.dequeue() print(cur.e.e) if cur.e.left is not None: queue.enqueue(cur.e.left) if cur.e.right is not None: queue.enqueue(cur.e.right)
編程的過程中會發現其實每一個節點都會被訪問3次。
