python中的树数据结构

野性酷女 2022-02-12 23:05 258阅读 0赞

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

《[顺序表数据结构在python中的应用][python]》

《[python实现单向链表数据结构及其基本方法][python 1]》

《[python实现单向循环链表数据结构及其方法][python 2]》

《[python实现双向链表基本结构及其基本方法][python 3]》

《[python实现双向循环链表基本结构及其基本方法][python 4]》

《[python实现堆栈数据结构及其基本方法][python 5]》

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

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

![2019-04-10-20\_03\_12.png][2019-04-10-20_03_12.png]

![2019-04-10-20\_03\_14.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][2019-04-10-20_03_14.png]

[python]: http://mp.weixin.qq.com/s?__biz=MzI2OTQ1NzEyMQ==&mid=2247484317&idx=1&sn=07fedcd9a9b21554f988a7a0297fa761&chksm=eae14013dd96c905a5aed9b05a5bcfdc92dee3b44cbba901335642c1700b06afad92c3621c52&scene=21#wechat_redirect
[python 1]: http://mp.weixin.qq.com/s?__biz=MzI2OTQ1NzEyMQ==&mid=2247484323&idx=1&sn=497036bb2c2e4ec29917319c5004fcad&chksm=eae1402ddd96c93b08ce3c5ec52e2f3c6cc81e6321dd36ce9100105c6677424d7beb97acc402&scene=21#wechat_redirect
[python 2]: http://mp.weixin.qq.com/s?__biz=MzI2OTQ1NzEyMQ==&mid=2247484329&idx=1&sn=8b6531019b053bf0cc112716c426c7dc&chksm=eae14027dd96c931cfec7afbc917093141acdd246a8635ec9cab66eab0b53d9aee14865095f6&scene=21#wechat_redirect
[python 3]: http://mp.weixin.qq.com/s?__biz=MzI2OTQ1NzEyMQ==&mid=2247484341&idx=1&sn=f7faf926cd15ccb6e21304066d86a4b2&chksm=eae1403bdd96c92de2b948418eb96f75563498d11905ebaa96ca72d234604c3178a07fa6bd79&scene=21#wechat_redirect
[python 4]: http://mp.weixin.qq.com/s?__biz=MzI2OTQ1NzEyMQ==&mid=2247484347&idx=1&sn=1cefd972158a249046aaa2fc68af1ac0&chksm=eae14035dd96c9234d7739847f0d8df1297fdae2a63db8b6b4e2b84db90fb6c817c619cbe7ba&scene=21#wechat_redirect
[python 5]: http://mp.weixin.qq.com/s?__biz=MzI2OTQ1NzEyMQ==&mid=2247484353&idx=1&sn=c949a404d3bef4fcbd8ad3ab5a5d7078&chksm=eae1404fdd96c95924773b2c8bb1f60d44dadda39eabe35a27731f382a764e68d87d8c9deae2&scene=21#wechat_redirect
[Python]: http://mp.weixin.qq.com/s?__biz=MzI2OTQ1NzEyMQ==&mid=2247484359&idx=1&sn=ca67a39aa98a2314f88fe3625826573c&chksm=eae14049dd96c95fb0375aca5d91cb40d8f3da99a6dd395c3aafe149c915dc21a903bb38897b&scene=21#wechat_redirect
[2019-04-10-20_03_12.png]: http://mzzd.xyz/static/wxfile/image/2019-04-10-20_03_12.png
[2019-04-10-20_03_14.png]: http://mzzd.xyz/static/wxfile/image/2019-04-10-20_03_14.png