教你如何使用Python实现二叉树结构及三种遍历

教你如何使用Python实现二叉树结构及三种遍历

一:代码实现

class TreeNode:
    """节点类"""
    def __init__(self, mid, left=None, right=None):
        self.mid = mid
        self.left = left
        self.right = right


# 树类
class Tree:
    """树类"""
    def __init__(self, root=None):
        self.root = root

    def add(self, item):
        # 将要添加的数据封装成一个node结点
        node = TreeNode(item)
        if not self.root:
            self.root = node
            return
        queue = [self.root]
        while queue:
            cur = queue.pop(0)
            if not cur.left:
                cur.left = node
                return
            else:
                queue.append(cur.left)

            if not cur.right:
                cur.right = node
                return
            else:
                queue.append(cur.right)
               
tree = Tree()
tree.add(0)
tree.add(1)
tree.add(2)
tree.add(3)
tree.add(4)
tree.add(5)
tree.add(6)

二:遍历

在上述树类代码基础上加遍历函数,基于递归实现。

先序遍历:

先序遍历结果是:0 -> 1 -> 3 -> 4 -> 2 -> 5 -> 6

# 先序遍历
    def preorder(self, root, result=[]):
        if not root:
            return
        result.append(root.mid)
        self.preorder(root.left, result)
        self.preorder(root.right, result)
        return result
        
print("先序遍历")
print(tree.preorder(tree.root))
"""
先序遍历
[0, 1, 3, 4, 2, 5, 6]
"""

中序遍历:

中序遍历结果是:3 -> 1 -> 4 -> 0 -> 5 -> 2 -> 6

# 中序遍历
    def inorder(self, root, result=[]):
        if not root:
            return result
        self.inorder(root.left, result)
        result.append(root.mid)
        self.inorder(root.right, result)
        return result
        
print("中序遍历")
print(tree.inorder(tree.root))
"""
中序遍历
3, 1, 4, 0, 5, 2, 6]
"""

后续遍历

后序遍历结果是:3 -> 4 -> 1 -> 5 -> 6 -> 2 -> 0

# 后序遍历
    def postorder(self, root, result=[]):
        if not root:
            return result
        self.postorder(root.left, result)
        self.postorder(root.right, result)
        result.append(root.mid)

        return result
        
print("后序遍历")
print(tree.postorder(tree.root))
"""
后序遍历
[3, 4, 1, 5, 6, 2, 0]
"""

到此这篇关于教你如何使用Python实现二叉树结构及三种遍历的文章就介绍到这了,更多相关Python实现二叉树结构及三种遍历内容请搜索趣讯吧以前的文章或继续浏览下面的相关文章希望大家以后多多支持趣讯吧!

发布于 2021-06-19 06:11:36
收藏
分享
海报
0 条评论
184
上一篇:Python使用海龟绘图实现贪吃蛇游戏 下一篇:Android基于opencv实现多通道分离与合并
目录

    推荐阅读

    0 条评论

    本站已关闭游客评论,请登录或者注册后再评论吧~

    忘记密码?

    图形验证码