Python实现二叉树的算法实例

本篇文章给大家带来的内容是关于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层节点个数

'''计算二叉树第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  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))

登录后复制

以上就是Python实现二叉树的算法实例的详细内容，更多请关注【创想鸟】其它相关文章！