python中的树数据结构-阿里云开发者社区

开发者社区> python之战> 正文

python中的树数据结构

简介: 线性数据中的典型顺序表和链表已经讲完: 《顺序表数据结构在python中的应用》 《python实现单向链表数据结构及其基本方法》 《python实现单向循环链表数据结构及其方法》 《python实现双向链表基本结构及其基本方法》 《python实现双向循环链表基本结构及其基本方法》 《python实现堆栈数据结构及其基本方法》 《Python实现双端队列数据结构及其基本方法》 下面将说图形结构中的典型数据机构:树;是一种重要的非线性数据结构,直观地看,它是数据元素(在树中称为结点)按分支关系组织起来的结构,很象自然界中的树那样。
+关注继续查看

线性数据中的典型顺序表和链表已经讲完:

顺序表数据结构在python中的应用

python实现单向链表数据结构及其基本方法

python实现单向循环链表数据结构及其方法

python实现双向链表基本结构及其基本方法

python实现双向循环链表基本结构及其基本方法

python实现堆栈数据结构及其基本方法

Python实现双端队列数据结构及其基本方法

下面将说图形结构中的典型数据机构:树;是一种重要的非线性数据结构,直观地看,它是数据元素(在树中称为结点)按分支关系组织起来的结构,很象自然界中的树那样。

2019-04-10-20_03_12.png

2019-04-10-20_03_14.png

树的一些基础概念:

  • 节点的度:一个节点含有的子树的个数称为该节点的度;

  • 树的度:一棵树中,最大的节点的度称为树的度;

  • 叶节点终端节点:度为零的节点;

  • 节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;

  • 树的高度深度:树中节点的最大层次;

  • 森林:由m(m>=0)棵互不相交的树的集合称为森林;

  • 路径:对于一棵子树中的任意两个不同的结点,如果从一个结点出发,按层次自上而下沿着一个个树枝能到达另一结点,称它们之间存在着一条路径

        常用树的分类:

无序树:树中任意节点的子节点之间没有顺序关系,这种树称为无序树,也称为自由树;

有序树:树中任意节点的子节点之间有顺序关系,这种树称为有序树;

    二叉树:每个节点最多含有两个子树的树称为二叉树;

    完全二叉树:对于一颗二叉树,假设其深度为d(d>1)。除了第d层外,其它各层的节点数目均已达最大值,且第d层所有节点从左向右连续地紧密排列,这样的二叉树被称为完全二叉树,其中满二叉树的定义是所有叶节点都在最底层的完全二叉树;

    平衡二叉树(AVL树):当且仅当任何节点的两棵子树的高度差不大于1的二叉树;

    排序二叉树(二叉查找树(英语:Binary Search Tree),也称二叉搜索树、有序二叉树);

    霍夫曼树(用于信息编码):带权路径最短的二叉树称为哈夫曼树或最优二叉树;

    B树:一种对读写操作进行优化的自平衡的二叉查找树,能够保持数据有序,拥有多余两个子树。


树的储存:

在python中一切皆对象,树也不列外,树在python中可以通过列表和链表来储存。通过列表是将每个节点对象储存,在逻辑上不过形象,基本不用;用的最多的是通过链表构建一个树对象,其基本属性是根节点,根节点的左树属性和右树属性连接不同的节点,依次构建一颗庞大的树。

class Node(object):
    """节点类"""
    def __init__(self, elem=-1, lchild=None, rchild=None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild


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



后面将主要说二叉树、平衡二叉树、红黑树及其相关的一些重要方法的python实现。

2019-04-10-20_03_14.png

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
数据结构之树、森林和二叉树的转换
树转换为二叉树 (1)加线。在所有兄弟结点之间加一条连线。 (2)去线。树中的每个结点,只保留它与第一个孩子结点的连线,删除它与其它孩子结点之间的连线。
759 0
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
10089 0
数据结构之Trie树
1、什么是Trie树    Trie树,即字典树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。
803 0
《数据结构与算法:Python语言描述》一导读
由于Python语言的一些优点,近年来,国外已经有不少大学采用它作为第一门计算机科学技术课程的教学语言,包括许多一流大学。国内院校也可能参考这种趋势,出现这种变化。作者在北京大学数学学院开设了基于Python语言的程序设计和数据结构课程,通过亲身实践,发现用Python讲授这两门课程也是一种很好的安排。
1616 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
13892 0
【Python】数据结构之字典
python 中的词典结构: d = {      'db1'    : 'swaroopch@byteofpython.info',              'db2'     : 'larry@wall.org',              'db3'     : 'matz@ruby-lang.org',              'db4'     : 'spammer@hotmail.com'      } 一 字典介绍    字典(dictionary)是除列表之外python之中最灵活的内置数据结构类型。
1260 0
python中的树数据结构
线性数据中的典型顺序表和链表已经讲完: 《顺序表数据结构在python中的应用》 《python实现单向链表数据结构及其基本方法》 《python实现单向循环链表数据结构及其方法》 《python实现双向链表基本结构及其基本方法》 《python实现双向循环链表基本结构及其基本方法》 《python实现堆栈数据结构及其基本方法》 《Python实现双端队列数据结构及其基本方法》 下面将说图形结构中的典型数据机构:树;是一种重要的非线性数据结构,直观地看,它是数据元素(在树中称为结点)按分支关系组织起来的结构,很象自然界中的树那样。
1550 0
+关注
python之战
专注python学习与应用擅长爬虫、web、全栈,专注RPA技术实施;(个人公号:Python之战)
90
文章
0
问答
来源圈子
更多
+ 订阅
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载