摘要:節(jié)點定義二叉樹定義先序遍歷遞歸方式先序遍歷,遞歸方式非遞歸方式先序遍歷,非遞歸方式中序遍歷遞歸方式中序遍歷,遞歸方式非遞歸方式中序遍歷,非遞歸方式后序遍歷遞歸方式后序遍歷,遞歸方式非遞歸方式后序遍歷,非遞歸方式分層遍歷分層遍歷,使用隊
節(jié)點定義
class Node(object): def __init__(self, left_child, right_child, value): self._left_child = left_child self._right_child = right_child self._value = value @property def left_child(self): return self._left_child @property def right_child(self): return self._right_child @left_child.setter def left_child(self, value): self._left_child = value @right_child.setter def right_child(self, value): self._right_child = value @property def value(self): return self._value @value.setter def value(self, value): self._value = value二叉樹定義
class Tree(object): def __init__(self, value): self._root = Node(None, None, value=value) @property def root(self): return self._root先序遍歷 遞歸方式
""" 先序遍歷,遞歸方式 """ def preoder(root): if not isinstance(root, Node): return None preorder_res = [] if root: preorder_res.append(root.value) preorder_res += preoder(root.left_child) preorder_res += preoder(root.right_child) return preorder_res非遞歸方式
""" 先序遍歷,非遞歸方式 """ def pre_order_not_recursion(root): if not isinstance(root, Node): return None stack = [root] result = [] while stack: node = stack.pop(-1) if node: result.append(node.value) stack.append(node.right_child) stack.append(node.left_child) return result中序遍歷 遞歸方式
""" 中序遍歷,遞歸方式 """ def middle_order(root): if not isinstance(root, Node): return None middle_res = [] if root: middle_res += middle_order(root.left_child) middle_res.append(root.value) middle_res += middle_order(root.right_child) return middle_res非遞歸方式
""" 中序遍歷,非遞歸方式 """ def middle_order_bot_recursion(root): if not isinstance(root, Node): return None result = [] stack = [root.right_child, root.value, root.left_child] while stack: temp = stack.pop(-1) if temp: if isinstance(temp, Node): stack.append(temp.right_child) stack.append(temp.value) stack.append(temp.left_child) else: result.append(temp) return result后序遍歷 遞歸方式
""" 后序遍歷,遞歸方式 """ def post_order(root): if not isinstance(root, Node): return None post_res = [] if root: post_res += post_order(root.left_child) post_res += post_order(root.right_child) post_res.append(root.value) return post_res非遞歸方式
""" 后序遍歷,非遞歸方式 """ def post_order_not_recursion(root): if not isinstance(root, Node): return None stack = [root.value, root.right_child, root.left_child] result = [] while stack: temp_node = stack.pop(-1) if temp_node: if isinstance(temp_node, Node): stack.append(temp_node.value) stack.append(temp_node.right_child) stack.append(temp_node.left_child) else: result.append(temp_node) return result分層遍歷
""" 分層遍歷,使用隊列實現(xiàn) """ def layer_order(root): if not isinstance(root, Node): return None queue = [root.value, root.left_child, root.right_child] result = [] while queue: temp = queue.pop(0) if temp: if isinstance(temp, Node): queue.append(temp.value) queue.append(temp.left_child) queue.append(temp.right_child) else: result.append(temp) return result計算二叉樹結(jié)點個數(shù)
""" 計算二叉樹結(jié)點個數(shù),遞歸方式 NodeCount(root) = NodeCount(root.left_child) + NodeCount(root.right_child) """ def node_count(root): if root and not isinstance(root, Node): return None if root: return node_count(root.left_child) + node_count(root.right_child) + 1 else: return 0 """ 計算二叉樹結(jié)點個數(shù),非遞歸方式 借用分層遍歷計算 """ def node_count_not_recursion(root): if root and not isinstance(root, Node): return None return len(layer_order(root))計算二叉樹深度
""" 計算二叉樹深度,遞歸方式 tree_deep(root) = 1 + max(tree_deep(root.left_child), tree_deep(root.right_child)) """ def tree_deep(root): if root and not isinstance(root, Node): return None if root: return 1 + max(tree_deep(root.left_child), tree_deep(root.right_child)) else: return 0 """ 計算二叉樹深度,非遞歸方法 同理參考分層遍歷的思想 """ def tree_deep_not_recursion(root): if root and not isinstance(root, Node): return None result = 0 queue = [(root, 1)] while queue: temp_node, temp_layer = queue.pop(0) if temp_node: queue.append((temp_node.left_child, temp_layer+1)) queue.append((temp_node.right_child, temp_layer+1)) result = temp_layer + 1 return result-1計算二叉樹第k層節(jié)點個數(shù)
""" 計算二叉樹第k層節(jié)點個數(shù),遞歸方式 kth_node_count(root, k) = kth_node_count(root.left_count, k-1) + kth_node_count(root.right_count, k-1) """ def kth_node_count(root, k): if root and not isinstance(root, Node): return None if not root or k <= 0: return 0 if k == 1: return 1 return kth_node_count(root.left_child, k-1) + kth_node_count(root.right_child, k-1) """ 計算二叉樹第K層節(jié)點個數(shù),非遞歸方式 """ def kth_node_count_not_recursion(root, k): if root and not isinstance(root, Node): return None if not root or k <= 0: return 0 if k == 1: return 1 queue = [(root, 1)] result = 0 while queue: temp_node, temp_layer = queue.pop(0) if temp_node: if temp_layer == k: result += 1 elif temp_layer > k: return result else: queue.append((temp_node.left_child, temp_layer+1)) queue.append((temp_node.right_child, temp_layer+1)) return result計算二叉樹葉子節(jié)點個數(shù)
""" 計算二叉樹葉子節(jié)點個數(shù),遞歸方式 關(guān)鍵點是葉子節(jié)點的判斷標準,左右孩子皆為None """ def leaf_count(root): if root and not isinstance(root, Node): return None if not root: return 0 if not root.left_child and not root.right_child: return 1 return leaf_count(root.left_child) + leaf_count(root.right_child)判斷兩個二叉樹是不是相同
""" 判斷兩個二叉樹是不是相同,遞歸方式 isSame(root1, root2) = (root1.value == root2.value) and isSame(root1.left, root2.left) and isSame(root1.right, root2.right) """ def is_same_tree(root1, root2): if not root1 and not root2: return True if root1 and root2: return (root1.value == root2.value) and is_same_tree(root1.left_child, root2.left_child) and is_same_tree(root1.right_child, root2.right_child) else: return False判斷是否為二分查找樹BST
""" 判斷是否為二分查找樹BST,遞歸方式 二分查找樹的定義搞清楚,二分查找樹的中序遍歷結(jié)果為遞增序列 """ def is_bst_tree(root): if root and not isinstance(root, Node): return None def is_asc(order): for i in range(len(order)-1): if order[i] > order[i+1]: return False return True return is_asc(middle_order_bot_recursion(root))測試方法
if __name__ == "__main__": tree = Tree(1) tree1 = Tree(1) node6 = Node(None, None, 7) node5 = Node(None, None, 6) node4 = Node(None, None, 5) node3 = Node(None, None, 4) node2 = Node(node5, node6, 3) node1 = Node(node3, node4, 2) tree.root.left_child = node1 tree.root.right_child = node2 tree1.root.left_child = node2 tree1.root.right_child = node2 print(is_bst_tree(tree.root))
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/43252.html
摘要:樹和樹的算法一樹樹的概念樹英語是一種抽象數(shù)據(jù)類型或是實作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu),用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。一種時間復(fù)雜度額外空間復(fù)雜度的二叉樹的遍歷方式,為二叉樹的節(jié)點個數(shù)。 樹和樹的算法 一、樹 1.1 樹的概念 樹(英語:tree)是一種抽象數(shù)據(jù)類型(ADT)或是實作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu),用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。它是由n(n>=1)個有限節(jié)點組成一個...
摘要:樹和樹的算法一樹樹的概念樹英語是一種抽象數(shù)據(jù)類型或是實作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu),用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。一種時間復(fù)雜度額外空間復(fù)雜度的二叉樹的遍歷方式,為二叉樹的節(jié)點個數(shù)。 樹和樹的算法 一、樹 1.1 樹的概念 樹(英語:tree)是一種抽象數(shù)據(jù)類型(ADT)或是實作這種抽象數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu),用來模擬具有樹狀結(jié)構(gòu)性質(zhì)的數(shù)據(jù)集合。它是由n(n>=1)個有限節(jié)點組成一個...
摘要:什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)的組織結(jié)構(gòu)方式一組數(shù)據(jù)如何存儲,基本數(shù)據(jù)類型,,的封裝算法與數(shù)據(jù)結(jié)構(gòu)的區(qū)別數(shù)據(jù)結(jié)構(gòu)只是靜態(tài)的描述了數(shù)據(jù)元素之間的關(guān)系。高效的程序需要在數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上設(shè)計和選擇算法。 數(shù)據(jù)結(jié)構(gòu)和算法基礎(chǔ) 什么是數(shù)據(jù)結(jié)構(gòu)和算法:兵法,計算的方法。算法是獨立存在的一種解決問題的方法和思想。 算法的特征: 輸入:算法具有0個或多個輸入 輸出:算法至少有1個或多個輸出 有窮性:算法在有限的...
摘要:二叉堆的有趣之處在于,其邏輯結(jié)構(gòu)上像二叉樹,卻是用非嵌套的列表來實現(xiàn)。二叉堆結(jié)構(gòu)性質(zhì)為了更好地實現(xiàn)堆,我們采用二叉樹。圖完全二叉樹有意思的是我們用單個列表就能實現(xiàn)完全樹。下列所示的代碼是完全二叉堆的實現(xiàn)。 優(yōu)先隊列的二叉堆實現(xiàn) 在前面的章節(jié)里我們學習了先進先出(FIFO)的數(shù)據(jù)結(jié)構(gòu):隊列(Queue)。隊列有一種變體叫做優(yōu)先隊列(Priority Queue)。優(yōu)先隊列的出隊(Dequ...
閱讀 798·2021-09-06 15:02
閱讀 2439·2019-08-30 15:43
閱讀 2164·2019-08-30 11:26
閱讀 2372·2019-08-26 12:12
閱讀 3538·2019-08-23 18:24
閱讀 3254·2019-08-23 18:16
閱讀 695·2019-08-23 17:02
閱讀 2241·2019-08-23 15:34