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>。
是一种抽象的数据结构,乍一听,就给人一种晦涩难懂的感觉,也确实如此,因为它的表现形式不像线性表那样那么直观。但是树结构太重要了,生活中常见的:文件的目录,族谱都是基于树结构;编程中常见的,数据库的索引,数据的快速定位等也是基于树结构,而且也有超级多的有关树结构的面试题。下面进入主题
前几篇分享的都是线性表数据结构,特点就是所有的项都有一个前驱,并且除了最后一项,每个数据也都拥有一个后继项。而在树结构中,前驱和后继项的概念也存在,只不过改个名,叫做父节点和子节点。
我们可以想象一下现实中的大树,每棵树都有树干,树枝,树叶等结构,新的树枝,树叶永远都是从已经存在的树枝,树叶中生长而来。我们可以想象,从树根到每一片树叶都有固定且唯一的一条路径,而路径上可能会呈现出不同的数据特点,路径还包含着层级的关系,我们根据这种特点,将路径上的数据抽象成自己所要的特点,树的结构就诞生了
说到这,对于刚接触的朋友们来说,肯定还是蒙的,所以我们先介绍下术语。
树是由节点(Node)和边(Edge)组成的,将一个父节点连接到其子节点的线,从(树的结构)上往下看,针对这条边,上面的节点是这个边的出边,下面的节点是这个边的入边
一个节点是其所有出边所连接节点的父节点,一个节点只能有一个父节点
入边均来自于同一个节点的若干节点,称之为这个节点的子节点
具有同一个父节点的节点之间称之为兄弟节点
没有子节点的节点称之为叶节点
一个节点的深度或者层级数等于将其连接到根节点的路径的长度,根节点深度为0
树中的最长的路径的长度(叶子节点的最大层级数)。最大层数即为树的高度,根节点的高度为0
由边依次连接在一起的节点可以看成是一个有序的列表
一个节点的子节点,以及其子节点的子节点,以此类推
<!-- html包含body和head两大块,body又包含其他,呈树形呈现 -->
<!DOCTYPE html>
<html>
<head>
<title></title>
</head>
<body>
<h1>hello,world</h1>
</body>
</html>
树结构一般性特征说到这就差不多了,接下来介绍树结构中最重要的一种:二叉树。
一棵树, 如果每个节点最多有两个子树,就称之为二叉树。
二叉树是n个节点的有限集合:该集合可以为空集(称为空二叉树),也可以由一个根节点和两棵互不相交的,分别称为根节点的 左子树和右子树组成
除了最后一个层级,其他的每一层都包含了完整的节点(每个节点都有两个子节点)
二叉树的这些特点都是后面理解二叉树应用的关键,接下来分享二叉树的实现(基于python),基于列表和链表
还是那句话:二叉树是一种逻辑结构,物理结构怎样实现取决于操作者,先分享数组实现的二叉树,不推荐数组,比较麻烦,且占用内存大。
# 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)
链表的实现要优于数组实现,更推荐,我们来看下如何实现
# 用链表实现的二叉树
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网站保持友好的沟通……时不时的会分享一些提高效率的编程小技巧,在实际应用中遇到的问题以及解决方案,或者源码的阅读等等,欢迎大家一起来讨论!如果觉得写得还不错,欢迎关注点赞,谢谢
*请认真填写需求信息,我们会在24小时内与您取得联系。