Python 資料結構-二叉樹
二叉樹是樹的特殊一種,具有如下特點:1、每個結點最多有兩顆子樹,結點的度最大為2。2、左子樹和右子樹是有順序的,次序不能顛倒。3、即使某結點只有一個子樹,也要區分左右子樹。
基本結構
節點
class Node(): def __init__(self, val =0): self.val = val self.left = None self.right = None
二叉樹
class BinaryTree(): def __init__(self): self.root = None
基本操作
插入節點
def insert_node(self, val): node = Node(val) if not self.root: self.root = node return else: q = [self.root] while True: root = q.pop(0) if root.left is None: root.left = node return elif root.right is None: root.right = node return else: q.append(root.left) q.append(root.right)
判斷是否為空
def is_empty(self): if self.root: return True else: return False
統計節點數
def count_node(self, root): if root is None: return 0 else: return 1 + self.count_node(root.left) + self.count_node(root.right)
最大深度
- 遞迴方式
def max_depth(self, root): if root is None: return 0 return 1 + max(self.max_depth(root.left), self.max_depth(root.right))
- 非遞迴方式
def max_depth(self, root): if root is None: return 0 depth = 0 queue = [root] while len(queue) != 0: depth += 1 node = queue[0] for i in range(len(queue)): if node.left: queue.append(node.left) if node.right: queue.append(node.right) del queue[0] return depth
構造樹
nums = [4, 2, 7, 1, 3, 6, 9] tree = BinaryTree() for i in nums: tree.insert_node(i)
生成如下所示的二叉樹:
4 /\ 27 / \/ \ 13 69
列印樹
def print_tree(self, root): if root: print(root.val, end=" ") self.print_tree(root.left) self.print_tree(root.right)
反轉樹
- 遞迴方式
def invert_tree(self, root): if not root: return root.left, root.right = root.right, root.left if root.left: self.invert_tree(root.left) if root.right: self.invert_tree(root.right)
- 非遞迴方式
def invert_tree(self, root): if root is None: return root if root.left is not None or root.right is not None: tmp = root.left root.left = root.right root.right = tmp if root.left is not None: self.invert_tree(root.left) if root.right is not None: self.invert_tree(root.right) return root
遍歷
前序遍歷
- 遞迴方式
def pre_order(self, root, res=None): if root is None: return [] if res is None: return [] res.append(root.val) self.pre_order(root.left, res) self.pre_order(root.right, res) return res
- 非遞迴方式
def pre_order(self, root): res = [] if not root: return res stack = [] stack.append(root) while stack: root = stack.pop() res.append(root.val) if root.right: stack.append(root.right) if root.left: stack.append(root.left) return res
中序遍歷
- 遞迴方式
def in_order(self, root, res=None): if root is None: return [] if res is None: return [] self.in_order(root.left, res) res.append(root.val) self.in_order(root.right, res) return res
- 非遞迴方式
def in_order(self, root): res = [] if not root: return res stack = [] while root or stack: while root: stack.append(root) root = root.left root = stack.pop() res.append(root.val) root = root.right return res
後序遍歷
- 遞迴方式
def post_order(self, root): res = [] if root is None: return [] preorder(root.left, res) preorder(root.right, res) res.append(root.val) return res
- 非遞迴方式
def post_order(self, root): res_temp = [] res = [] if not root: return res stack = [] stack.append(root) while stack: root = stack.pop() res_temp.append(root.val) if root.left: stack.append(root.left) if root.right: stack.append(root.right) while res_temp: res.append(res_temp.pop()) return res
層次遍歷
def level_order(self, root): res = [] if not root: return res level = [root] while level: current = [] new_level = [] for node in level: current.append(node.val) if node.left: new_level.append(node.left) if node.right: new_level.append(node.right) level = new_level res.append(current) return res