Python实现二叉树相关算法

guyan0319 发布于2019-07-31 10:06 / 1277人阅读

摘要：节点定义二叉树定义先序遍历递归方式先序遍历，递归方式非递归方式先序遍历，非递归方式中序遍历递归方式中序遍历，递归方式非递归方式中序遍历，非递归方式后序遍历递归方式后序遍历，递归方式非递归方式后序遍历，非递归方式分层遍历分层遍历，使用队

节点定义

</>复制代码 
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))

云服务器 GPU云服务器二叉树算法实现二叉树最优二叉树算法图 python二叉树

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/43252.html

树和树的算法

摘要：树和树的算法一树树的概念树英语是一种抽象数据类型或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。一种时间复杂度额外空间复杂度的二叉树的遍历方式，为二叉树的节点个数。树和树的算法一、树 1.1 树的概念树（英语：tree）是一种抽象数据类型（ADT）或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>=1）个有限节点组成一个...

RaoMeng 2019-08-19 11:08 评论0 收藏0
树和树的算法

摘要：树和树的算法一树树的概念树英语是一种抽象数据类型或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。一种时间复杂度额外空间复杂度的二叉树的遍历方式，为二叉树的节点个数。树和树的算法一、树 1.1 树的概念树（英语：tree）是一种抽象数据类型（ADT）或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>=1）个有限节点组成一个...

PiscesYE 2019-07-30 17:45 评论0 收藏0
Python_数据结构与算法

摘要：什么是数据结构数据的组织结构方式一组数据如何存储，基本数据类型，，的封装算法与数据结构的区别数据结构只是静态的描述了数据元素之间的关系。高效的程序需要在数据结构的基础上设计和选择算法。数据结构和算法基础什么是数据结构和算法：兵法，计算的方法。算法是独立存在的一种解决问题的方法和思想。算法的特征：输入：算法具有0个或多个输入输出：算法至少有1个或多个输出有穷性：算法在有限的...

Kylin_Mountain 2019-07-30 16:02 评论0 收藏0
Python数据结构——二叉堆的实现

摘要：二叉堆的有趣之处在于，其逻辑结构上像二叉树，却是用非嵌套的列表来实现。二叉堆结构性质为了更好地实现堆，我们采用二叉树。图完全二叉树有意思的是我们用单个列表就能实现完全树。下列所示的代码是完全二叉堆的实现。优先队列的二叉堆实现在前面的章节里我们学习了先进先出（FIFO）的数据结构：队列（Queue）。队列有一种变体叫做优先队列（Priority Queue）。优先队列的出队（Dequ...

stackfing 2019-07-24 18:19 评论0 收藏0

发表评论

登陆后可评论

0条评论

guyan0319

男|高级讲师

我要关注我要私信

TA的文章

程序人生 - 祝贺登榜《数据结构与算法领域内容榜》NO.29

阅读 845·2021-09-06 15:02
Javascript运行机制

阅读 2475·2019-08-30 15:43
代码质量把控和项目进度之间的平衡

阅读 2215·2019-08-30 11:26
带着问题学习webpack

阅读 2411·2019-08-26 12:12
一年前端女生面试经验分享

阅读 3573·2019-08-23 18:24
node-blog：用 node 搭建的个人开源博客

阅读 3298·2019-08-23 18:16
JavaScript中的继承

阅读 729·2019-08-23 17:02
ES6箭头函数

阅读 2293·2019-08-23 15:34

资讯专栏INFORMATION COLUMN

上云采购季！| 2核2G4M爆款云服务器低至59元/年，更有多台、长期优惠，快来选购！

Python实现二叉树相关算法

</>复制代码

</>复制代码

</>复制代码

</>复制代码

</>复制代码

</>复制代码

</>复制代码

</>复制代码

</>复制代码

</>复制代码

</>复制代码

</>复制代码

</>复制代码

</>复制代码

</>复制代码

</>复制代码

相关文章

树和树的算法

树和树的算法

Python_数据结构与算法

Python数据结构——二叉堆的实现

发表评论

0条评论

guyan0319

男|高级讲师

TA的文章

程序人生 - 祝贺登榜《数据结构与算法领域内容榜》NO.29

Javascript运行机制

代码质量把控和项目进度之间的平衡

带着问题学习webpack

一年前端女生面试经验分享

node-blog：用 node 搭建的个人开源博客

JavaScript中的继承

ES6箭头函数

最新活动