节点定义
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
分层遍历
'''分层遍历，使用队列实现'''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
计算二叉树结点个数
'''计算二叉树结点个数，递归方式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'''计算二叉树结点个数，非递归方式借用分层遍历计算'''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层节点个数
'''计算二叉树第k层节点个数，递归方式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层节点个数，非递归方式'''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
计算二叉树叶子节点个数
'''计算二叉树叶子节点个数，递归方式关键点是叶子节点的判断标准，左右孩子皆为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，递归方式二分查找树的定义搞清楚，二分查找树的中序遍历结果为递增序列'''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))