树形数据结构个人理解:
苍茫宇宙,世间万物,都是由各种不同结构的物质构成,有基础物质,有由基础物质构成的次级基础物质,有各种不同组合体构成的高级物体。
如果说在python中,基础物质是那些最基本的数据类型,节点数据类型u则是由这些基础数据类型构成的次高级物体。一个节点中的基础数据存在着特定的数据关系,正是由于这些关系,让他们之间可以互相访问或者产生特定的作用。
嗯哈,扯的有点远。来谈谈啥是二叉树,和普通的树。
二叉树,是一种树。一种非常具有特定关系的树。
在二叉树里面一共有两种关系:父子关系,兄弟关系
有两种数据类型:基础数据类型和二叉树数据类型
还有一个非常特殊的约定,一个父对象,撑死了有两个子对象,该子对象可以是基础数据类型,也可以是二叉树数据类型。该约定就区别了二叉树和树的不同,一个普通的树,父对象可以拥有无数的子对象,但是二叉树最多有两个,我想二叉树的名字可能跟这个有关,恩啊,这个只是一个猜想而已,对错已经没有什么太大的意义。
那么树呢?区别于二叉树,他没有第三个约定,也就是说一个父对象的子对象的个数是不限制的。这也就好理解了。我们用图来表示:
二叉树的几种形态:
灰色带表没有子对象的基础类型
蓝色代表具有子对象的基础类型
橙色代表父子关系,第三那个2,3是兄弟关系,画线的话,就不好看,破坏美感,就不画了。
这三种代表了二叉树的最基本的集中组成类型。当然刚刚说过了,基础对象也可以是二叉树数据类型,有人就是说子对象也可是二叉树数据类型,如下图:
可以看到3虽然是1的子对象,但是也是4、5的父对象。
再看来看树额哈。之前也说了啊,一个父对象可以有多个子对象,如下图,蓝色的部分,就是父对象,你看看他们有很对的孩子啊,多么欢乐的家庭,只可惜没有姑娘额哈。
首先我们要明白管他是什么树,只要是树,都必须有节点。那么节点是树形结构中最小的单位,当然节点中的值除外。
那么在构造树形数据结构之前,我们需要构建节点这个数据结构。
OK,在看了这些东东后,我们来构造一个最基本的数据类型,节点。
一个具有所有元素的二叉树节点:
一个节点由what组成? 它本身的数据和它的孩子数据,他的孩子又很特殊,分为左孩子,右孩子,那么我们分开表示,左孩子用left参数表示,右孩子用right参数表示,对吧?在初始化的时候,我们需要这两个参数。
class BNode:
def __init__(self, value, left, right):
self.value = vlaue
self.left = left
self.right = right
一个具有所有元素的树节点:
value 代表他自己的数据,
child代表他的孩子对象,可以是最基本最基本的数据类型,也可以是Node类型,由于他的孩子不像二叉树那样,都很普通,所以我们直接用child来表示,他可以是list类型,也可以是其他的对象类型。
该类提供最基本的访问方法 visit
Class TNode:
def __init__(self,value, child):
self.value = value
self.child = child
def visit():
return self.value
OK.上面已经构建除了二叉树和树的两种最基本的数据类型,节点:
那么开始构建一个稍微完整一点是树啦
一个小草就只有几个枝叶,所以他很小,那么小草有毛用?我们要的是由大量节点构成的参天大树。
参天大树有毛用?如果让你把这个书上的所有变黄色的全都干下来,怎么搞?那需要先查找再删除。
也就是说你要每一个叶子都需要检查一遍,看他是不是黄色的,如果是黄色的,就干掉。
查找的话,就需要遍历啊,挨个看。写的烦死了,不写了,老子自己去实现。