文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

用Python实现数据结构之树

2023-01-30 23:32

关注

树是由根结点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点,所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位,这个结点称为该树的根结点,或称为树根。

  • 根节点:树中最顶部的元素

  • 父节点:处了根节点都有父节点,每个节点最多只有一个父节点

  • 孩子节点:一个父节点具有0个或多个孩子节点

  • 兄弟节点:同一个父节点的孩子节点之间是兄弟关系

  • 外部节点:一个没有孩子的节点称为外部节点,也叫叶子结点

  • 内部节点:有一个或多个孩子节点的节点叫做内部节点

  • 树的边:指一对节点(u,v),其中u是v的父节点或者v是u的父节点

  • 树的路径:一系列连续的边组成了一条路径

  • 节点的深度:节点的深度就是该节点的祖先的个数,不包括该节点本身,如果根节点的层数为1,则深度即为该节点的层数-1

  • 节点的高度:如果p是树中的叶子节点,那么它的高度为0.否则p的高度是它的孩子节点中的最大高度+1

  • 有序树:每个孩子之间有一定的顺序,例如:


class Tree():
    """
    树的抽象基类
    """

    # 叫做位置的内嵌类,用于封装节点
    class Position():

        def element(self):
            raise NotImplementedError('must be implemented by subclass')

        def __eq__(self, other):
            raise NotImplementedError('must be implemented by subclass')

    def root(self):
        """
        return 根节点的position
        """
        raise NotImplementedError('must be implemented by subclass')

    def parent(self,p):
        """

        :param p:一个位置对象
        :return: 返回p的父节点的position对象,如果p是根节点则饭后空
        """
        raise NotImplementedError('must be implemented by subclass')

    def num_children(self,p):
        """

        :param p:一个位置对象
        :return: 返回该位置的孩子节点的数量
        """
        raise NotImplementedError('must be implemented by subclass')

    def children(self,p):
        """

        :param p: 一个位置对象
        :return: 返回位置p的孩子的迭代
        """
        raise NotImplementedError('must be implemented by subclass')

    def __len__(self):
        """

        :return: 返回整个树的节点个数
        """

     raise NotImplementedError('must be implemented by subclass')

    def is_root(self,p):
        return self.root() == p

    def is_leaf(self,p):
        return self.num_children(p) == 0

    def is_empty(self):
        return len(self) == 0

这个抽象类中的方法必须在子类中实现才能调用,不然会产生NotImplementedError(‘must be implemented by subclass’)的异常

除此之外,对于Position()这个内嵌类可能较难理解,为什么要有这么一个内嵌类

这个内嵌类目前也是抽象类,具体方法都没有实现,但使用它的目的已经有了,就是将树中的节点进行封装,那为什么要封装节点呢?当调用树的相关方法时,节点可能为一个必要的参数,但我们手动传入时,实际上可以是任意的对象,这就会导致错误发生,所以我们必须保证传入的节点是节点的对象,同时也是本树对象的节点,不然就会弄混树与树的节点。同时将节点进行封装,可以避免使用者直接使用节点对象本身,相关节点的方法可以在封装成的Position对象调用。目前只是抽象类的定义,节点类等其他方法还未定义,后面还会看到具体的position对象的使用。

目前有了Tree这个抽象类,虽然其中的大多数方法还是抽象方法,但使用这些方法已经可以构成一些其他的功能了,所以就有了is_root,is_leaf,is_empty方法的定义。同时还可以定义计算节点的深度与高度的方法:


def depth(self,p):
    """
    计算节点在树中的深度
    """
    if self.is_root(p):
        return 0
    else:
        return 1 + self.depth(self.parent(p))

def height(self,p):
    """
    计算节点在树中的深度 
    """
    if self.is_leaf(p):
        return 0
    else:
        return 1 + max(self.height(c) for c in self.children(p))

我们现在介绍一种树的特殊化形式二叉树

二叉树的特点:

  • 每个父节点最多只有两个孩子节点

  • 两个孩子节点又叫做左孩子和右孩子

  • 以左孩子为根节点形成的树叫做左子树,以右孩子为根节点形成的树叫做右子树

  • 如果除了最下面的一层节点,其余节点组成的是一颗满二叉树,并且最下面的这层节点遵循从左到右依次添加的顺序,那么这个树就叫做完全二叉树

  • 非空完全二叉树中,外部节点数=内部节点数+1

二叉树的实现可以以继承树的抽象类的方式实现:


class BinaryTree(Tree):

    class Node():

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

    class Position(Tree.Position):

        def __init__(self, container, node):
            self.container = container
            self.node = node

        def element(self):
            return self.node.element

        def __eq__(self, other):
            return isinstance(other, type(self)) and other.node is self.node

    def validate(self, p):
        """
        进行位置验证
        """
        if not isinstance(p, self.Position):
            raise TypeError('p must be proper Position type')
        if p.container is not self:
            raise ValueError('p does not belong to this container')
        if p.node.parent is p.node:
            raise ValueError('p is no longer valid')
        return p.node

    def make_position(self, node):
        """
        封装节点
        """
        return self.Position(self, node) if node is not None else None

    def __init__(self):
        self._root = None
        self.size = 0

    def __len__(self):
        return self.size

    def root(self):
        return self.make_position(self._root)

    def parent(self, p):
        node = self.validate(p)
        return self.make_position(node.parent)

    def left(self, p):
        node = self.validate(p)
        return self.make_position(node.left)

    def right(self, p):
        node = self.validate(p)
        return self.make_position(node.right)

    def sibling(self, p):
        parent = self.parent(p)
        if parent is None:
            return None
        else:
            if p == self.left(parent):
                return self.right(parent)
            else:
                return self.left(parent)

    def num_children(self, p):
        node = self.validate(p)
        count = 0
        if node.left is not None:
            count += 1
        if node.right is not None:
            count += 1
        return count
  

    def children(self,p):
        if self.left(p) is not None:
            yield self.left(p)
        if self.right(p) is not None:
            yield self.right(p)

代码中将之前的抽象方法进行了完整的定义,同时添加了validate与make_position方法。validate方法用于对传入的position参数进行验证,make_position方法用于将节点进行封装。除此之外还添加了二叉树特有的方法right,left和sibling,left与right分别返回节点的左孩子节点与右孩子节点,sibling返回的是节点的兄弟节点。

目前的二叉树的数据结构只是创建了一颗空树,我们接下来要加入的是对二叉树进行更新操作的方法


def add_root(self, e):
    if self._root is not None:
        raise ValueError('Root exists')
    self.size += 1
    self._root = self.Node(e)
    return self.make_position(self._root)

def add_left(self, e, p):
    node = self.validate(p)
    if node.left is not None:
        raise ValueError('Left child exists')
    self.size += 1
    node.left = self.Node(e, node)
    return self.make_position(node.left)

def add_right(self, e, p):
    node = self.validate(p)
    if node.right is not None:
        raise ValueError('Left child exists')
    self.size += 1
    node.right = self.Node(e, node)
    return self.make_position(node.right)

def replace(self, p, e):
    node = self.validate(p)
    old = node.element
    node.element = e
    return old

def delete(self, p):
    """
    删除该位置的节点,如果该节点有两个孩子,则会产生异常,如果只有一个孩子,
    则使其孩子代替该节点与其双亲节点连接
    """
    node = self.validate(p)
    if self.num_children(p) == 2:
        raise ValueError('p has two children')
    child = node.left if node.left else node.right
    if child is not None:
        child.parent = node.parent
    if node is self._root:
        self._root = child
    else:
        parent = node.parent
        if node is parent.left:
            parent.left = child
        else:
            parent.right = child
    self.size -= 1
    node.parent = node
    return node.element

总共加入了添加根节点,添加左孩子,添加右孩子,代替元素和删除节点5个方法,其中删除几点稍微有一些复杂,因为涉及到许多情况的判断。

到现在,一个完整的二叉树数据结构基本完成了。

但是我们还需要掌握一个算法,就是树的遍历算法

树的遍历一般有先序遍历,后序遍历,广度优先遍历(层序遍历),对于二叉树还有中序遍历

先序遍历

先序遍历是按照根节点->从左到右的孩子节点的顺序遍历,而且把每个孩子节点看作是子树的根节点同样如此,例如:

用python实现先序遍历为:


def preorder(self,p):
    """
    先序遍历节点p为根节点的树
    """
    yield p
    for c in self.children(p):
        for other in self.preorder(c):
            yield other

虽然代码只有4行,但理解起来却不是很容易的,首先该方法是一个生成器,所以通过yield返回一个可迭代对象,也就是可以for循环该方法,由于是先序遍历,所以要先yield p,之后便要返回孩子节点,由于孩子节点可能还具有孩子,所以并不能只返回孩子节点,应该返回以孩子节点为根节点的树的所有节点,而要想for循环得到左右的孩子节点为根节点的所有节点,还需要调用孩子节点的先序遍历方法才能得到。总而言之,代码理解的难度还是由于递归算法造成的,一个复杂的递归终归还是不是那么容易就能看出来的。

后序遍历

后序遍历是按照先从左到右孩子节点->根节点,如图:

用python实现:


def postorder(self,p):
    """
    后序遍历节点p为根的树 
    """
    for c in self.children(p):
        for other in self.postorder(c):
            yield other
    yield p

理解与先序遍历相同

广度优先遍历

广度优先遍历也叫层序遍历,一层一层的遍历,如图:

用python实现:


def breadthfirst(self):
    if not self.is_empty():
        queue = Queue()
        queue.enqueue(self.root())
        while not queue.is_empty():
            p = queue.dequeue()
            yield p
            for i in self.children(p):
                queue.enqueue(i)

中序遍历二叉树

对于二叉树,遍历顺序为左孩子->父节点->右孩子

python实现为:


def inorder(self,p):
    if self.left(p) is not None:
        for other in self.inorder(self.left(p)):
            yield other
    if self.right(p) is not None:
        for other in self.inorder(self.right(p)):
            yield other

参考《数据结构与算法Python语言实现》

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯