本篇文章给大家带来的内容是关于Python实现二叉树的算法实例，有一定的参考价值，有需要的朋友可以参考一下，希望对你有所帮助。
节点定义
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层节点个数，递归方式
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，递归方式 二分查找树的定义搞清楚，二分查找树的中序遍历结果为递增序列 ''' 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))
以上是Python实现二叉树的算法实例的详细内容。更多信息请关注PHP中文网其他相关文章！
