整合营销服务商

电脑端+手机端+微信端=数据同步管理

免费咨询热线:

XML 树结构

ML 文档形成了一种树结构,它从"根部"开始,然后扩展到"枝叶"。


一个 XML 文档实例

XML 文档使用简单的具有自我描述性的语法:

<?xmlversion="1.0"encoding="UTF-8"?><note><to>Tove</to><from>Jani</from><heading>Reminder</heading><body>Don't forget me this weekend!</body></note>

第一行是 XML 声明。它定义 XML 的版本(1.0)和所使用的编码(UTF-8 : 万国码, 可显示各种语言)。

下一行描述文档的根元素(像在说:"本文档是一个便签"):

<note>

接下来 4 行描述根的 4 个子元素(to, from, heading 以及 body):

<to>Tove</to><from>Jani</from><heading>Reminder</heading><body>Don't forget me this weekend!</body>

最后一行定义根元素的结尾:

</note>

您可以假设,从这个实例中,XML 文档包含了一张 Jani 写给 Tove 的便签。

XML 具有出色的自我描述性,您同意吗?


XML 文档形成一种树结构

XML 文档必须包含根元素。该元素是所有其他元素的父元素。

XML 文档中的元素形成了一棵文档树。这棵树从根部开始,并扩展到树的最底端。

所有的元素都可以有子元素:

<root><child><subchild>.....</subchild></child></root>

父、子以及同胞等术语用于描述元素之间的关系。父元素拥有子元素。相同层级上的子元素成为同胞(兄弟或姐妹)。

所有的元素都可以有文本内容和属性(类似 HTML 中)。


实例:

上图表示下面的 XML 中的一本书:

XML 文档实例

<bookstore><bookcategory="COOKING"><titlelang="en">Everyday Italian</title><author>Giada De Laurentiis</author><year>2005</year><price>30.00</price></book><bookcategory="CHILDREN"><titlelang="en">Harry Potter</title><author>J K. Rowling</author><year>2005</year><price>29.99</price></book><bookcategory="WEB"><titlelang="en">Learning XML</title><author>Erik T. Ray</author><year>2003</year><price>39.95</price></book></bookstore>

实例中的根元素是 <bookstore>。文档中的所有 <book> 元素都被包含在 <bookstore> 中。

<book> 元素有 4 个子元素:<title>、<author>、<year>、<price>。

是一种抽象的数据结构,乍一听,就给人一种晦涩难懂的感觉,也确实如此,因为它的表现形式不像线性表那样那么直观。但是树结构太重要了,生活中常见的:文件的目录,族谱都是基于树结构;编程中常见的,数据库的索引,数据的快速定位等也是基于树结构,而且也有超级多的有关树结构的面试题。下面进入主题



树的概念

前几篇分享的都是线性表数据结构,特点就是所有的项都有一个前驱,并且除了最后一项,每个数据也都拥有一个后继项。而在树结构中,前驱和后继项的概念也存在,只不过改个名,叫做父节点和子节点。

我们可以想象一下现实中的大树,每棵树都有树干,树枝,树叶等结构,新的树枝,树叶永远都是从已经存在的树枝,树叶中生长而来。我们可以想象,从树根到每一片树叶都有固定且唯一的一条路径,而路径上可能会呈现出不同的数据特点,路径还包含着层级的关系,我们根据这种特点,将路径上的数据抽象成自己所要的特点,树的结构就诞生了

说到这,对于刚接触的朋友们来说,肯定还是蒙的,所以我们先介绍下术语。

树的相关术语

  1. 边/分支

树是由节点(Node)和边(Edge)组成的,将一个父节点连接到其子节点的线,从(树的结构)上往下看,针对这条边,上面的节点是这个边的出边,下面的节点是这个边的入边

  1. 父节点

一个节点是其所有出边所连接节点的父节点,一个节点只能有一个父节点

  1. 子节点

入边均来自于同一个节点的若干节点,称之为这个节点的子节点

  1. 兄弟节点

具有同一个父节点的节点之间称之为兄弟节点

  1. 叶节点

没有子节点的节点称之为叶节点

  1. 深度/层级

一个节点的深度或者层级数等于将其连接到根节点的路径的长度,根节点深度为0

  1. 高度

树中的最长的路径的长度(叶子节点的最大层级数)。最大层数即为树的高度,根节点的高度为0

  1. 路径

由边依次连接在一起的节点可以看成是一个有序的列表

  1. 后代

一个节点的子节点,以及其子节点的子节点,以此类推

树结构特点

  1. 树是由节点(Node)和边(Edge)组成的
  2. 树的节点包含一个数据元素以及若干指向其子树的分支。节点拥有的子树称为节点的度,度为0的节点称为叶节点,度不为0的节点称之为分支节点,也叫内部节点
  3. 树的每条边都连接两个节点,表示节点有关联
  4. 树是一种分层的数据结构,一般规律是,越接近顶部的层越普遍(包含的数据范围越大),反之则数据会越来越集中
  5. 一棵树的不同节点的子节点之间不能相交
  6. 叶子节点具有唯一性(叶子节点是指没有子分支的节点)
  7. 从根节点开始,每一个节点下方连接着的分支都称之为该节点的孩
  8. 线性结构和树结构最大的不同在于线性结构是一对一的,而树结构是一对多的关系

生活中的案例

  1. 文件系统
  • linux系统/windows系统的目录都是以树状图的方式设计
  • 域名系统
  1. xml/html文档结构
<!-- html包含body和head两大块,body又包含其他,呈树形呈现 -->
<!DOCTYPE html>
<html>
<head>
	<title></title>
</head>
<body>
	<h1>hello,world</h1>
</body>
</html>

树结构一般性特征说到这就差不多了,接下来介绍树结构中最重要的一种:二叉树

二叉树相关

  1. 概念

一棵树, 如果每个节点最多有两个子树,就称之为二叉树。

二叉树是n个节点的有限集合:该集合可以为空集(称为空二叉树),也可以由一个根节点和两棵互不相交的,分别称为根节点的 左子树和右子树组成

  1. 特点
  • 每个节点最多有两个子树,所以二叉树中不存在度大于2的节点。可以没有子树或者只有一课子树也是可以的
  • 左子树和右子树是有顺序的,次序不能颠倒
  • 即便树中只有一棵子树,也要区分它是左子树还是右子树
  • 树结构为什么这么复杂,因为树结构本就分了很多种,细分到二叉树时,又分了很多种,所以这里得介绍下不同的二叉树的类型。

几种重要且特殊的二叉树

  1. 平衡二叉树

除了最后一个层级,其他的每一层都包含了完整的节点(每个节点都有两个子节点)

  1. 满二叉树
  • 所以分支节点都存在左子树和右子树,并且所有的叶子都在同一层上,这样的二叉树称为满二叉树
  • 满二叉树是同样深度的二叉树中节点最多的
  1. 完全二叉树
  • 最后一层上的所有节点(叶子节点)都是从左往右填充的
  • 完全二叉树按照线性表的方式进行存储,如果某个节点的下标为p,则其左子节点的下标为2p,右子节点为2p+1,其父节点下标为p//2,根节点的下标默认从1开始
  1. 满二叉树和完全二叉树的区别
  • 满二叉树一定是完全二叉树,但是完全二叉树不一定是满二叉树,满二叉树是完全二叉树的一个特例
  • 完全二叉树的叶子节点只能出现在最下面两层
  • 最下面的叶子一定集中在左边连续位置
  • 倒数第二层,若有叶子节点,一定在右部连续位置
  1. 二叉树的特点
  • 在二叉树的第n层上最多有2^(n-1)节点(最多的情况其实就是满二叉树)。反过来说,对于包含N个节点的满二叉树,高度为h=log2(n+1) - 1
  • 深度为n的二叉树最多有2^n - 1个节点
  • 对任何一棵二叉树,如果其终端节点数为n0,度为2的节点数为n2,则n0=n2 + 1
  • 具有n个节点的完全二叉树的深度为logn + 1
  • 一般来讲,二叉树越平衡,插入,访问以及删除的性能越高

二叉树的这些特点都是后面理解二叉树应用的关键,接下来分享二叉树的实现(基于python),基于列表和链表

二叉树的实现

  1. 列表实现

还是那句话:二叉树是一种逻辑结构,物理结构怎样实现取决于操作者,先分享数组实现的二叉树,不推荐数组,比较麻烦,且占用内存大。

# r为根节点,另外两个空列表分别代表左子节点盒右子结点
def binary_tree(r):
    return [r, [], []]
#
def insert_left(root, new_branch):
    # 先定位左子节点
    t = root.pop(1)
    # 已经存在左子节点
    if len(t) > 1:
        root.insert(1, [new_branch, t, []])
    else:
        # 不存在左子节点
        root.insert(1,[new_branch, [], []])
    return root
        
def insert_right(root, new_branch):
    t = root.pop(2)
    if len(t) > 1:
        root.insert(2, [new_branch, [], [t]])
    else:
        root.insert(2,[new_branch, [], []])
    return root

def get_root(root):
    return root[0]

def set_root(root, data):
    root[0] = data

def get_left_child(root):
    return root[1]

def get_right_child(root):
    return root[2]

# 测试都是往根节点插入
r = binary_tree(3)
insert_left(r,4)
insert_left(r,5)
insert_right(r,6)
insert_right(r,7)
l = get_left_child(r)
print(r)
  1. 链表实现

链表的实现要优于数组实现,更推荐,我们来看下如何实现

# 用链表实现的二叉树
class BinaryTree(object):
    def __init__(self, root):
        self.key = root
        self.left_child = None
        self.right_child = None
        
    def insert_left(self, data):
        if self.left_child == None:
            self.left_child = BinaryTree(data)
        else:
            t = BinaryTree(data)
            t.left_child = self.left_child
            self.left_child = t
            
    def insert_right(self, data):
        if self.right_child == None:
            self.right_child = BinaryTree(data)
        else:
            t = BinaryTree(data)
            t.right_child = self.right_child
            self.right_child = t 
            
    def get_right_child(self):
        return self.right_child
    
    def get_left_child(self):
        return self.left_child
    
    # 取出当前结点的数据
    def get_root(self):
        return self.key
    
    # 设置当前结点的值
    def set_root(self, value):
        self.key = value

        
# 前序遍历,这里只是为了展示结果用        
def pre_order(tree):
    if tree:
        print(tree.get_root())
        pre_order(tree.get_left_child())
        pre_order(tree.get_right_child())
        
        
# 生成二叉树的结构
tree = BinaryTree(0)
tree.insert_left(3)
tree.insert_left(1)
tree.get_left_child().insert_right(4)
tree.insert_right(6)
tree.insert_right(2)
pre_order(tree)

总结

本篇主要介绍了树结构的一般特性,二叉树的几种变体以及二叉树的基于python的实现。希望你对树结构能有一个初步的了解,当然,树结构还没有说完,比如树的几种遍历模式,树的一些经典应用等等,这些会放到下篇文章分享。


我是一名奋战在编程界的pythoner,工作中既要和数据打交道,也要和erp系统,web网站保持友好的沟通……时不时的会分享一些提高效率的编程小技巧,在实际应用中遇到的问题以及解决方案,或者源码的阅读等等,欢迎大家一起来讨论!如果觉得写得还不错,欢迎关注点赞,谢谢