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，递归方式
二分查找树的定义搞清楚，二分查找树的中序遍历

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))