树——celia的学习笔记

1212-王同学

发表文章数:21

首页 » 数据结构 » 正文

二叉树的广度优先遍历

应用“队列”数据结构,按照广度优先遍历的顺序进行。

先序遍历

根节点-左子树-右子树

中序遍历

左子树-根节点-右子树
从小到大

后序遍历

左子树-右子树-根节点

注意
记忆方法先、中、后指的都是根节点的位置,且
不管什么遍历始终是左子树在右子树前面

代码

class Node(object):

    def __init__(self, item):
        self.item = item
        self.left = None
        self.right = None


class Tree(object):

    def __init__(self):
        self.root = None

    def add(self, item):
        node = Node(item)
        if self.root is None:
            self.root = node

        else:
            q = [self.root]

            while True:
                pop_node = q.pop(0)
                if pop_node.left is None:
                    pop_node.left = node
                    return
                elif pop_node.right is None:
                    pop_node.right = node
                    return
                else:
                    q.append(pop_node.left)
                    q.append(pop_node.right)

    def traverse(self):  # 层次遍历
        if self.root is None:
            return None
        q = [self.root]
        res = [self.root.item]
        while q != []:
            pop_node = q.pop(0)
            if pop_node.left is not None:
                q.append(pop_node.left)
                res.append(pop_node.left.item)

            if pop_node.right is not None:
                q.append(pop_node.right)
                res.append(pop_node.right.item)
        return res

    def preorder(self, root):  # 先序遍历
        if root is None:
            return []
        result = [root.item]
        left_item = self.preorder(root.left)
        right_item = self.preorder(root.right)
        return result + left_item + right_item

    def inorder(self, root):  # 中序遍历
        if root is None:
            return []
        result = [root.item]
        left_item = self.inorder(root.left)
        right_item = self.inorder(root.right)
        return left_item + result + right_item

    def postorder(self, root):  # 后序遍历
        if root is None:
            return []
        result = [root.item]
        left_item = self.postorder(root.left)
        right_item = self.postorder(root.right)
        return left_item + right_item + result


if __name__ == '__main__':
    t = Tree()
    for i in range(10):
        t.add(i)

    print("层序遍历:", t.traverse())
    print("先序遍历:", t.preorder(t.root))
    print("中序遍历:", t.inorder(t.root))
    print("后序遍历:", t.postorder(t.root))

根据遍历结果画出树

需要至少给出两种遍历结果才可以画出原树,且其中必须包含中序遍历,因为中序遍历是唯一能够把左子树和右子树分开的遍历结果。

未经允许不得转载:作者:1212-王同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《树——celia的学习笔记》 发布于2020-11-19

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录