Python 树结构,python树形结构
Python数据结构应用——树形数据结构是计算机存储和组织数据的一种方式。数据结构是指相互之间具有一种或多种特定关系的数据元素的集合。通常，精心选择的数据结构可以带来更高的操作或存储效率。数据结构通常与高效的检索算法和索引技术有关。
数据结构中树的节点和机器学习中决策树的节点有一个很大的区别，就是数据结构中树的每个叶节点都是独立的。树的高度是指叶子节点(不包括根节点)的最大级别树。1.构建树可以定义如下：树由一系列节点和一系列连接节点的边组成。
一棵树也可以这样定义：一棵树有根和其他子树，这些子树也是树。
在python中，使用的定义是后者。
1.1.list列表对于一个列表：[q ，[]，[]]，它代表一棵树(子树)， q 是根节点，[]，[]分别是左右子节点。因此，有一个左节点为 A 的树，可以写成[q ，[a ，[]，[]]，[]]
My _ tree=[a ，[b ，[d ，[]，[]]，[e ，[]，[]]，[c ，[f ，[]，[]]]在这个定义的情况下
定义二叉树(r):
return [r，[]，[]]
def insert_left(root，new_branch):
t=root.pop(1) #左边的子位置
if len(t) 1: # if不为空
#原始左孩子变成新分支的左孩子
root.insert(1，[new_branch，t，[]])
否则：
root.insert(1，[新分支，[]，[]])
返回根目录
def insert_right(root，new_branch):
t=root.pop(2)
如果len(t) 1:
root.insert(2，[新分支，[]，t])
否则：
root.insert(2，[新分支，[]，[]])
返回根目录
def get_root_val(root):
返回根目录[0]
def set_root_val(root，new_val):
root[0]=new_val
def get_left_child(根):
返回根目录[1]
def get_right_child(根):
返回根[2]x=二叉树( a )
insert_left(x， b )
insert_right(x， c )
insert_right(get_right_child(x)， d) #重要！
insert _ left(get _ right _ child(get _ right _ child(x))。
类BinaryTree:
def __init__(self，root):
self.key=root
self.left_child=None
self.right_child=None
def insert_left(自身，新节点):
if self.left_child==None:
self . left _ child=binary tree(new _ node)
否则：
t=BinaryTree(new_node)
左孩子=self.left_child
self.left_child=t
def insert_right(自身，新节点):
if self.right_child==None:
self . right _ child=binary tree(new _ node)
否则：
t=BinaryTree(new_node)
t.right_child=self
self.right_child=t
def get_right_child(self):
返回self.right_child
def get_left_child(self):
返回self.left_child
def set_root_val(self，obj):
self.key=obj
def get_root_val(自身):
return self.keyx=BinaryTree(a )
x.insert_left(b )
x.insert_right(c )
x.get_right_child()。insert_right(f )
X _ _ main _ _。二叉树在0x105930278，这两种构造方法都没有办法返回到父节点。详情见第三节。解析树。
第二，基于二进制堆的优先级队列之前的队列都是FIFO数据结构。但是，在优先级队列中，队列中的数据有一个优先级标签。在优先级队列中，队列中项目的逻辑顺序由它们的优先级决定。最高优先级在队列的前面，最低优先级在项目的后面。
实现优先级队列的经典方法是使用一种叫做二进制堆的数据结构，可以在O(log(n))O(log(n))时间内对队列进行排队和取队列。
PS:二进制堆和栈不是一回事。这个堆在结构上是一个完整的二叉树。实现中使用的数组列表使用数组的索引值来表示父节点和子节点。fork堆有两种常见的变体：最小堆(其中最小的键总是在前面)和最大堆。
因为二叉堆是一棵完整的二叉树，为了保证log(n)时间，树必须是平衡的。
如图，是二进制堆。堆结构类似于树，实现方式是通过列表实现的。列表的第一个元素是0。为什么会这样？因为树中每个元素都有对应的索引，所以需要满足左右节点分别为2*p 2*p 1。如果index index从0开始，则不满足。
二进制堆的性质是一个非常重要的东西。二进制堆的所有操作基本都是基于它的性质：每个节点的父节点都比自己小(最小堆)。
类BinHeap:
def __init__(self):
self.heap_list=[0]
Self.current_size=02.1插入操作在二进制堆中插入一个项。过程是：要插入的项放在二进制堆列表的最后一项。因为二进制堆要保持它的属性(每个节点的父节点都比自己小)，所以这个项就和它的父节点进行比较，小的在上面，大的在下面，进行可能的交换。这种比较将持续到根节点。
这种交换被称为percolate _ up，因为要插入的项目是自下而上交换的。
def perc_up(self，I):
而我//2 0:
if self . heap _ list[I]self . heap _ list[I//2]:
self.heap_list[i]，self . heap _ list[I//2]=self . heap _ list[I//2]，self.heap_list[i]
i=i//2
定义插入(自身，k):
self.heap_list.append(k)
self.current_size=1
自我。PERC _ UP(自我，自我。current _ size) 2.2删除(出列)操作因为我们研究的是最小堆，所以出列操作就是把值最小的节点也就是根节点移出来。
操作：去掉根节点后，将链表的最后一项放在根节点上，然后根据二进制堆的属性进行percolate _ down操作(即依次向下比较根节点的项)。
def perc_down(self，I):
while (i * 2)=self.current_size:
mc=self.min_child(i)
if self . heap _ list[I]self . heap _ list[MC]:
self.heap_list[i]，self . heap _ list[MC]=self . heap _ list[MC]，self.heap_list[i]
i=mc
#返回左右节点较小的那个
def min_child(self，I):
if i*2 1 self.current_size:
返回i*2
否则：
if self . heap _ list[I * 2]self . heap _ list[I * 2 1]:
返回i*2
否则：
返回i*2 1
def del_min(自身):
#第一个元素是0
ret_val=self.heap_list[1]
self . heap _ list[1]=self . heap _ list[self . current _ size]
self.current_size=self .当前大小- 1
self.heap_list.pop()
self.perc_down(1)
Ret _ Val2.3构建二进制堆的两种思路：
1.列表可以直接排序，代价最低为O(nlogn)O(nlogn)，得到的列表必须是二进制堆。
2.对于一个链表的每一项，从左到右执行percolate _ down操作，时间复杂度为O(n)O(n)
def build_heap(self，a_list):
i=len(a_list)//2
self.current_size=len(a_list)
self.heap_list=[0] a_list[:]
while(i 0):
self.perc_down(一)
I=i-1 III。解析树以树的形式表示解析表达式，例如((73) (52)) ((73) (52))可以表示为
解析树的形成可以定义为以下四条规则：
1.如果遇到(，表示有新的表达式，创建一个新的子树(添加一个新的子节点，然后创建这个新节点的左子，将处理目标移动到这个左子)。
2.如果遇到[，-，*，/]运算符，把这个运算符放在当前节点，同时创建一个右子，把处理目标移到这个右子。
3.如果遇到数字，就把数字放在当前节点，把处理目标返回给父节点。
4.如果是)，将处理目标返回给父节点。
定义构建解析树(fp_exp):
fp_list=fp_exp.split()
p_stack=堆栈()
e_tree=BinaryTree( )
push(e_tree)
当前树=e树
对于fp_list中的I:
如果i==(:
当前树.插入左()
p_stack.push(当前树)
current _ tree=current _ tree . get _ left _ child()
e如果I不在[ ，-， * ，/，)]中：
current _ tree . set _ root _ val(int(I))
parent=p_stack.pop()
当前树=父树
elif i in [ ，-， * ，/]:
当前树设置根值(I)
current_tree.insert_right( )
p _栈. push(当前树)
当前树=当前树。get _ right _ child()
elif i==):
current_tree=p_stack.pop()
否则：
提高值错误
返回e树\u由于之间构造的二叉树类无法访问其父结点，所以这里要新建一个堆在储存当前的父结点。
在遇到(和操作员的这两个操作都需要将当前操作结点移到左右孩子上，所以这两个操作需要将父结点入堆。
四、树的遍历三种遍历方式：先序遍历（预购，中左右), 中序遍历（为了，左中右), 后序遍历（邮购，左右中),他们的不同在于每个结点访问的顺序。
先，中，后都是对于根结点来说的。
在大蟒中两种方法进行遍历：
1.外界函数
2.类中函数
事实证明外界函数处理遍历更加有效率，因为在大多数情况下，遍历都会跟别的操作混合在一起，所以外界函数修改更方便。
定义预订（树):
如果树：
print(tree.get_root_val())
preorder(tree.get_left_child())
预购(树。get _ right _ child())def preorder(self):#类中函数
打印(self.key)
if self.left_child:
self.left.preorder()
if self.right_child:
自我。没错。预订()定义后订单(树):
如果树：
postorder(tree.get_left_child())
postorder(tree.get_right_child())
打印(tree.get _ root _ val)定义顺序(树):
如果树：
inorder(tree.get_left_child())
打印(tree.get _ root _ val)
按顺序(树。get _ right _ child())4.1解析树eval(232，232，232)；颜色：rgb(38，38，38)；边距：0px填充：0px背景：rgb(249，249，249)；进口经营者
def postorder_eval(树):
opers={ :operator.add，-:operator.sub， *:operator.mul，
/:operator.truediv}
res1=无
res2=无
如果树：
res1=post order _ eval(树。get _ left _ child())
res2=post order _ eval(树。get _ right _ child())
如果res1和res2:
返回操作[树。get _ root _ val()](res1，res2)
否则：
return tree.get_root_val()五、二叉搜索树（英国夏令时)二叉搜索树的实现主要依赖于它的性质(英国夏令时属性):父母的键值比左结点大，比右结点小。
类TreeNode:
def __init__(self，key，val，left=None，right=None，parent=None):
self.key=key
self.payload=val
self.left_child=left
self.right_child=right
self.parent=parent
定义有_左_子（自己):
返回self.left_child
定义有_右_子（自己):
返回self.right_child
def is_left_child(自身):
返回自我父母和self.parent.left_child==self
def is_right_child(自身):
返回自我父母和self.parent.right_child==self
def is_root(自身):
返回非自身。父
def is_leaf(self):
不返回(self.right_child或self.left_child)
定义有_any_children(自己):
返回self.right_child或self.left_child
定义有_两个孩子(自己):
返回self.right_child和self.left_child
def replace_node_data(self，key，value，lc，rc):
self.key=key
self.payload=值
self.left_child=lc
self.right_child=rc
if self.has_left_child():
self.left_child.parent=self
if self.has_right_child():
自我。右_子。parent=self binarysearchtree这个类很复杂：
类二进制搜索树：
def __init__(self):
self.root=None
self.size=0
定义长度（自身):
返回自身大小
def __len__(self):
返回自身大小
def __iter__(self):
返回self.root.__iter__()下面的放()函数在二元搜索树中，他的主要功能是插入一个新节点7 .如果树没有根结点，即将待插入结点为根结点，如果树有根结点，即执行该类的私有函数_put()
def put(self，key，val):
if self.root:
自我. put(key，val，self.root)
否则：
self.root=TreeNode(key，val)
self.size=self.size 1
def _put(self，key，val，current_node):
if键当前节点。关键：
如果current_node.has_left_child():
自我. put(键，值，当前节点。左子节点)
否则：
当前节点。向左。child=TreeNode(key，val，parent=当前节点)
否则：
如果current_node.has_right_child():
自我. put(key，val，current_node.right_child)
否则：
当前节点。right _ child=TreeNode(key，val，parent=current_node)下面是大蟒的魔术方法，能轻易的进行赋值操作：(下列函数生成后即可以执行my_zip_tree[32]==你好这种赋值操作)
def __setitem__(self，k，v):
self.put(k，v) get()操作是放()的反操作，用来找到结点
def get(self，key):
if self.root:
res=self ._get(key，self.root)
如果res:
返回资源有效负载
否则：
不返回
否则：
不返回
def _get(自身，关键字，当前节点):
如果不是当前节点：
不返回
否则如果当前节点。key==key:
返回当前节点
elif key current_node.key:
回归自我. get(key，current_node.left_child)
否则：
回归自我. get(key，current_node.right_child)
def __getitem(self，key):
return self.get(键)使用获取()函数，我们还可以创建在操作，即创建__包含_ _函数：
def __contains__(self，key):
如果自我. get(key，self.root):
返回真实的
否则：
如果我的_压缩_树中有“北菲尔德”，则返回Falseif:
打印(“oom ya ya”)删除结点操作是二叉搜索树中最复杂的部分，主要过程分为两步：首先，使用获取()操作找到要删除的节点；然后，删除结节且保证其他子树连接仍然保持二叉树属性。
定义删除(自我，关键):
如果自身尺寸为1:
node_to_remove=self ._get(key，self.root)
如果要删除节点：
自我移除(节点到移除)
self.size=self.size - 1
否则：
引发KeyError(“错误，密钥不在树中")
elif self.size==1，self.root.key==key:
self.root=None
self.size=self.size - 1
否则：
引发KeyError(“错误，密钥不在树中")
def __delitem__(self，key):
self.delete(key) remove()操作分为三种情况：
第一种：删除的结点没有孩子，这种情况很直接，直接删除就好的
if current_node.is_leaf():
如果当前节点==当前节点。父节点。左子节点：
当前节点。父母。left _ child=无
否则：
当前节点。父母。right _ child=无第二种：删除的结点有一个孩子（这里只考虑这个孩子是左孩子的情况，右孩子的情况是对称的)
1.如果要删除的结点是左孩子，那么我们只要更新它的左孩子与他的父结点对接即可
2.如果要删除的结点是右孩子，那么我们只要更新它的右孩子与他的父结点对接即可
3.如果删除的结点没有父母，那么他肯定是根结点
否则：#此节点有一个子节点
如果current_node.has_left_child():
if current_node.is_left_child():
当前节点。左子节点。父节点=当前节点。父节点
当前节点。父节点。左子节点=当前节点。左子节点
elif当前节点。is _ right _ child():
当前节点。左子节点。父节点=当前节点。父节点
当前节点。父节点。右子节点=当前节点。左子节点
否则：
当前节点。替换节点数据(当前节点。左_子。钥匙，
当前节点。左_子。有效载荷
当前节点。左子节点。左子节点，
当前节点。左子节点。右子节点)
否则：
if current_node.is_left_child():
当前节点。右子节点。父节点=当前节点。父节点
当前节点。父节点。左子节点=当前节点。右子节点
elif当前节点。is _ right _ child():
当前节点。右子节点。父节点=当前节点。父节点
当前节点。父节点。右子节点=当前节点。右子节点
否则：
当前节点。替换节点数据(当前节点。右_子。键
当前节点。右_子。有效载荷
当前节点。右子节点。左子节点，
当前节点。右子节点。右子节点)第三种：删除的结点有两个孩子。这时，并不能直接用他的孩子替代，这个时候需要找一个继任者（继任者),这个继任者满足两个条件(1.在删除结点中的子孙中第一个比他大的结点。2.这个继任者最多有一个孩子),继任者接替删除结点的位置。
elif当前节点。has _ both _ children():#室内
succ=current _ node.find _ successor()
succ.splice_out()
current_node.key=succ.key
当前节点。有效载荷=succ。有效负载定义查找_后继者(自身):
成功=无
if self.has_right_child():
succ=self.right_child.find_min()
否则：
如果是self.parent:
if self.is_left_child():
succ=self.parent
否则：
self.parent.right_child=None
succ=self . parent . find _ successor()
self.parent.right_child=self
返回Succ参考：用算法和数据结构解决问题，发布3.0 Python魔法指南期待陌生，拥抱惊喜。
数据结构中树的节点和机器学习中决策树的节点有一个很大的区别，就是数据结构中树的每个叶节点都是独立的。树的高度是指叶子节点(不包括根节点)的最大级别树。1.构建树可以定义如下：树由一系列节点和一系列连接节点的边组成。
一棵树也可以这样定义：一棵树有根和其他子树，这些子树也是树。
在python中，使用的定义是后者。
1.1.list列表对于一个列表：[q ，[]，[]]，它代表一棵树(子树)， q 是根节点，[]，[]分别是左右子节点。因此，有一个左节点为 A 的树，可以写成[q ，[a ，[]，[]]，[]]
My _ tree=[a ，[b ，[d ，[]，[]]，[e ，[]，[]]，[c ，[f ，[]，[]]]在这个定义的情况下
定义二叉树(r):
return [r，[]，[]]
def insert_left(root，new_branch):
t=root.pop(1) #左边的子位置
if len(t) 1: # if不为空
#原始左孩子变成新分支的左孩子
root.insert(1，[new_branch，t，[]])
否则：
root.insert(1，[新分支，[]，[]])
返回根目录
def insert_right(root，new_branch):
t=root.pop(2)
如果len(t) 1:
root.insert(2，[新分支，[]，t])
否则：
root.insert(2，[新分支，[]，[]])
返回根目录
def get_root_val(root):
返回根目录[0]
def set_root_val(root，new_val):
root[0]=new_val
def get_left_child(根):
返回根目录[1]
def get_right_child(根):
返回根[2]x=二叉树( a )
insert_left(x， b )
insert_right(x， c )
insert_right(get_right_child(x)， d) #重要！
insert _ left(get _ right _ child(get _ right _ child(x))。
类BinaryTree:
def __init__(self，root):
self.key=root
self.left_child=None
self.right_child=None
def insert_left(自身，新节点):
if self.left_child==None:
self . left _ child=binary tree(new _ node)
否则：
t=BinaryTree(new_node)
左孩子=self.left_child
self.left_child=t
def insert_right(自身，新节点):
if self.right_child==None:
self . right _ child=binary tree(new _ node)
否则：
t=BinaryTree(new_node)
t.right_child=self
self.right_child=t
def get_right_child(self):
返回self.right_child
def get_left_child(self):
返回self.left_child
def set_root_val(self，obj):
self.key=obj
def get_root_val(自身):
return self.keyx=BinaryTree(a )
x.insert_left(b )
x.insert_right(c )
x.get_right_child()。insert_right(f )
X _ _ main _ _。二叉树在0x105930278，这两种构造方法都没有办法返回到父节点。详情见第三节。解析树。
第二，基于二进制堆的优先级队列之前的队列都是FIFO数据结构。但是，在优先级队列中，队列中的数据有一个优先级标签。在优先级队列中，队列中项目的逻辑顺序由它们的优先级决定。最高优先级在队列的前面，最低优先级在项目的后面。
实现优先级队列的经典方法是使用一种叫做二进制堆的数据结构，可以在O(log(n))O(log(n))时间内对队列进行排队和取队列。
PS:二进制堆和栈不是一回事。这个堆在结构上是一个完整的二叉树。实现中使用的数组列表使用数组的索引值来表示父节点和子节点。fork堆有两种常见的变体：最小堆(其中最小的键总是在前面)和最大堆。
因为二叉堆是一棵完整的二叉树，为了保证log(n)时间，树必须是平衡的。
如图，是二进制堆。堆结构类似于树，实现方式是通过列表实现的。列表的第一个元素是0。为什么会这样？因为树中每个元素都有对应的索引，所以需要满足左右节点分别为2*p 2*p 1。如果index index从0开始，则不满足。
二进制堆的性质是一个非常重要的东西。二进制堆的所有操作基本都是基于它的性质：每个节点的父节点都比自己小(最小堆)。
类BinHeap:
def __init__(self):
self.heap_list=[0]
Self.current_size=02.1插入操作在二进制堆中插入一个项。过程是：要插入的项放在二进制堆列表的最后一项。因为二进制堆要保持它的属性(每个节点的父节点都比自己小)，所以这个项就和它的父节点进行比较，小的在上面，大的在下面，进行可能的交换。这种比较将持续到根节点。
这种交换被称为percolate _ up，因为要插入的项目是自下而上交换的。
def perc_up(self，I):
而我//2 0:
if self . heap _ list[I]self . heap _ list[I//2]:
self.heap_list[i]，self . heap _ list[I//2]=self . heap _ list[I//2]，self.heap_list[i]
i=i//2
定义插入(自身，k):
self.heap_list.append(k)
self.current_size=1
自我。PERC _ UP(自我，自我。current _ size) 2.2 Delete(出列)操作因为我们研究的是最小堆，所以出列操作是去掉值最小的节点，也就是根节点。
操作：去掉根节点后，将链表的最后一项放在根节点上，然后根据二进制堆的属性进行percolate _ down操作(即依次向下比较根节点的项)。
def perc_down(self，I):
while (i * 2)=self.current_size:
mc=self.min_child(i)
if self . heap _ list[I]self . heap _ list[MC]:
self.heap_list[i]，self . heap _ list[MC]=self . heap _ list[MC]，self.heap_list[i]
i=mc
#返回左右节点较小的那个
def min_child(self，I):
if i*2 1 self.current_size:
返回i*2
否则：
if self . heap _ list[I * 2]self . heap _ list[I * 2 1]:
返回i*2
否则：
返回i*2 1
def del_min(自身):
#第一个元素是0
ret_val=self.heap_list[1]
self . heap _ list[1]=self . heap _ list[self . current _ size]
self.current_size=self .当前大小- 1
self.heap_list.pop()
self.perc_down(1)
Ret _ Val2.3构建二进制堆的两种思路：
1.列表可以直接排序，代价最低为O(nlogn)O(nlogn)，得到的列表必须是二进制堆。
2.对于一个链表的每一项，从左到右执行percolate _ down操作，时间复杂度为O(n)O(n)
def build_heap(self，a_list):
i=len(a_list)//2
self.current_size=len(a_list)
self.heap_list=[0] a_list[:]
while(i 0):
self.perc_down(一)
I=i-1 III。解析树以树的形式表示解析表达式，例如((73) (52)) ((73) (52))可以表示为
解析树的形成可以定义为以下四条规则：
1.如果遇到(，表示有新的表达式，创建一个新的子树(添加一个新的子节点，然后创建这个新节点的左子，将处理目标移动到这个左子)。
2.如果遇到[，-，*，/]运算符，把这个运算符放在当前节点，同时创建一个右子，把处理目标移到这个右子。
3.如果遇到数字，就把数字放在当前节点，把处理目标返回给父节点。
4.如果是)，将处理目标返回给父节点。
定义构建解析树(fp_exp):
fp_list=fp_exp.split()
p_stack=堆栈()
e_tree=BinaryTree( )
push(e_tree)
当前树=e树
对于fp_list中的I:
如果i==(:
当前树.插入左()
p_stack.push(当前树)
current _ tree=current _ tree . get _ left _ child()
e如果I不在[ ，-， * ，/，)]中：
current _ tree . set _ root _ val(int(I))
parent=p_stack.pop()
当前树=父树
elif i in [ ，-， * ，/]:
当前树设置根值(I)
current_tree.insert_right( )
p _栈. push(当前树)
当前树=当前树。get _ right _ child()
elif i==):
current_tree=p_stack.pop()
否则：
提高值错误
返回e树\u由于之间构造的二叉树类无法访问其父结点，所以这里要新建一个堆在储存当前的父结点。
在遇到(和操作员的这两个操作都需要将当前操作结点移到左右孩子上，所以这两个操作需要将父结点入堆。
四、树的遍历三种遍历方式：先序遍历（预购，中左右), 中序遍历（为了，左中右), 后序遍历（邮购，左右中),他们的不同在于每个结点访问的顺序。
先，中，后都是对于根结点来说的。
在大蟒中两种方法进行遍历：
1.外界函数
2.类中函数
事实证明外界函数处理遍历更加有效率，因为在大多数情况下，遍历都会跟别的操作混合在一起，所以外界函数修改更方便。
定义预订（树):
如果树：
print(tree.get_root_val())
preorder(tree.get_left_child())
预购(树。get _ right _ child())def preorder(self):#类中函数
打印(self.key)
if self.left_child:
self.left.preorder()
if self.right_child:
自我。没错。预订()定义后订单(树):
如果树：
postorder(tree.get_left_child())
postorder(tree.get_right_child())
打印(tree.get _ root _ val)定义顺序(树):
如果树：
inorder(tree.get_left_child())
打印(tree.get _ root _ val)
按顺序(树。get _ right _ child())4.1解析树eval(232，232，232)；颜色：rgb(38，38，38)；边距：0px填充：0px背景：rgb(249，249，249)；进口经营者
def postorder_eval(树):
opers={ :operator.add，-:operator.sub， *:operator.mul，
/:operator.truediv}
res1=无
res2=无
如果树：
res1=post order _ eval(树。get _ left _ child())
res2=post order _ eval(树。get _ right _ child())
如果res1和res2:
返回操作[树。get _ root _ val()](res1，res2)
否则：
return tree.get_root_val()五、二叉搜索树（英国夏令时)二叉搜索树的实现主要依赖于它的性质(英国夏令时属性):父母的键值比左结点大，比右结点小。
类TreeNode:
def __init__(self，key，val，left=None，right=None，parent=None):
self.key=key
self.payload=val
self.left_child=left
self.right_child=right
self.parent=parent
定义有_左_子（自己):
返回self.left_child
定义有_右_子（自己):
返回self.right_child
def is_left_child(自身):
返回自我父母和self.parent.left_child==self
def is_right_child(自身):
返回自我父母和self.parent.right_child==self
def is_root(自身):
返回非自身。父
def is_leaf(self):
不返回(self.right_child或self.left_child)
定义有_any_children(自己):
返回self.right_child或self.left_child
定义有_两个孩子(自己):
返回self.right_child和self.left_child
def replace_node_data(self，key，value，lc，rc):
self.key=key
self.payload=值
self.left_child=lc
self.right_child=rc
if self.has_left_child():
self.left_child.parent=self
if self.has_right_child():
self.right_child.parent = selfBinarySearchTree 这个类很复杂：
class BinarySearchTree:
def __init__(self):
self.root = None
self.size = 0
def length(self):
return self.size
def __len__(self):
return self.size
def __iter__(self):
return self.root.__iter__()下面的put()函数在BinarySearchTree中，他的主要功能是插入一个新node。如果树没有根结点，即将待插入结点为根结点，如果树有根结点，即执行该类的私有函数_put()
def put(self, key, val):
if self.root:
self._put(key, val, self.root)
else:
self.root = TreeNode(key ,val)
self.size = self.size + 1
def _put(self, key, val, current_node):
if key current_node.key:
if current_node.has_left_child():
self._put(key, val, current_node.left_child)
else:
current_node.left.child = TreeNode(key, val, parent=current_node)
else:
if current_node.has_right_child():
self._put(key, val, current_node.right_child)
else:
current_node.right_child = TreeNode(key, val, parent=current_node)下面是python的魔术方法，能轻易的进行赋值操作：(下列函数生成后即可以执行 my_zip_tree[32]==hello 这种赋值操作)
def __setitem__(self, k, v):
self.put(k, v)get()操作是put()的反操作，用来找到结点
def get(self, key):
if self.root:
res = self._get(key, self.root)
if res:
return res.payload
else:
return None
else:
return None
def _get(self, key, current_node):
if not current_node:
return None
elif current_node.key == key:
return current_node
elif key current_node.key:
return self._get(key, current_node.left_child)
else:
return self._get(key, current_node.right_child)
def __getitem(self, key):
return self.get(key)使用get()函数，我们还可以创建in操作，即创建__contains__函数：
def __contains__(self, key):
if self._get(key, self.root):
return True
else:
return Falseif Northfield in my_zip_tree:
print("oom ya ya")删除结点操作是二叉搜索树中最复杂的部分，主要过程分为两步：首先，使用get()操作找到要删除的node；然后，删除node且保证其他子树连接仍然保持二叉树属性。
def delete(self, key):
if self.size 1:
node_to_remove = self._get(key, self.root)
if node_to_remove:
self.remove(node_to_remove)
self.size = self.size - 1
else:
raise KeyError(Error, key not in tree)
elif self.size == 1 and self.root.key == key:
self.root = None
self.size = self.size - 1
else:
raise KeyError(Error, key not in tree)
def __delitem__(self, key):
self.delete(key)remove()操作分为三种情况：
第一种：删除的结点没有孩子，这种情况很直接，直接删除就ok
if current_node.is_leaf():
if current_node == current_node.parent.left_child:
current_node.parent.left_child = None
else:
current_node.parent.right_child = None第二种：删除的结点有一个孩子（这里只考虑这个孩子是左孩子的情况，右孩子的情况是对称的）
1.如果要删除的结点是左孩子，那么我们只要更新它的左孩子与他的父结点对接即可
2.如果要删除的结点是右孩子，那么我们只要更新它的右孩子与他的父结点对接即可
3.如果删除的结点没有父母，那么他肯定是根结点
else: # this node has one child
if current_node.has_left_child():
if current_node.is_left_child():
current_node.left_child.parent = current_node.parent
current_node.parent.left_child = current_node.left_child
elif current_node.is_right_child():
current_node.left_child.parent = current_node.parent
current_node.parent.right_child = current_node.left_child
else:
current_node.replace_node_data(current_node.left_child.key,
current_node.left_child.payload,
current_node.left_child.left_child,
current_node.left_child.right_child)
else:
if current_node.is_left_child():
current_node.right_child.parent = current_node.parent
current_node.parent.left_child = current_node.right_child
elif current_node.is_right_child():
current_node.right_child.parent = current_node.parent
current_node.parent.right_child = current_node.right_child
else:
current_node.replace_node_data(current_node.right_child.key,
current_node.right_child.payload,
current_node.right_child.left_child,
current_node.right_child.right_child)第三种：删除的结点有两个孩子。这时，并不能直接用他的孩子替代，这个时候需要找一个继任者（successor），这个继任者满足两个条件（1.在删除结点中的子孙中第一个比他大的结点。2.这个继任者最多有一个孩子），继任者接替删除结点的位置。
elif current_node.has_both_children(): #interior
succ = current_node.find_successor()
succ.splice_out()
current_node.key = succ.key
current_node.payload = succ.payloaddef find_successor(self):
succ = None
if self.has_right_child():
succ = self.right_child.find_min()
else:
if self.parent:
if self.is_left_child():
succ = self.parent
else:
self.parent.right_child = None
succ = self.parent.find_successor()
self.parent.right_child = self
return succReference:Problem Solving with Algorithms and Data Structures, Release 3.0Python 魔术方法指南
©
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。