|
<div class="markdown-here-wrapper" data-md-url="https://i.cnblogs.com/EditPosts.aspx?postid=10341449">
<h1 id="-" style="margin: 20px 0px 10px; padding: 0px; font-weight: bold; color: black; font-size: 24px; border-bottom: 2px solid #aaaaaa;">树
<blockquote style="margin: 1.2em 0px; border-left: 4px solid #dddddd; padding: 0px 1em; color: #777777; quotes: none;">
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">树是由根结点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或称为树根。
:
<span class="hljs-comment" style="color: #738191;"># 叫做位置的内嵌类，用于封装节点</span>
<span class="hljs-class"><span class="hljs-keyword" style="font-weight: bold;">class</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">Position</span><span class="hljs-params">()</span>:</span>
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">element</span><span class="hljs-params">(self)</span>:</span>
<span class="hljs-keyword" style="font-weight: bold;">raise</span> NotImplementedError(<span class="hljs-string" style="color: #0048ab;">'must be implemented by subclass'</span>)
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">__eq__</span><span class="hljs-params">(self,other)</span>:</span>
<span class="hljs-keyword" style="font-weight: bold;">raise</span> NotImplementedError(<span class="hljs-string" style="color: #0048ab;">'must be implemented by subclass'</span>)
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">root</span><span class="hljs-params">(self)</span>:</span>
<span class="hljs-string" style="color: #0048ab;">"""
return 根节点的position
"""</span>
<span class="hljs-keyword" style="font-weight: bold;">raise</span> NotImplementedError(<span class="hljs-string" style="color: #0048ab;">'must be implemented by subclass'</span>)
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">parent</span><span class="hljs-params">(self,p)</span>:</span>
<span class="hljs-string" style="color: #0048ab;">"""
:param p:一个位置对象
:return: 返回p的父节点的position对象，如果p是根节点则饭后空
"""</span>
<span class="hljs-keyword" style="font-weight: bold;">raise</span> NotImplementedError(<span class="hljs-string" style="color: #0048ab;">'must be implemented by subclass'</span>)
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">num_children</span><span class="hljs-params">(self,p)</span>:</span>
<span class="hljs-string" style="color: #0048ab;">"""
:param p:一个位置对象
:return: 返回该位置的孩子节点的数量
"""</span>
<span class="hljs-keyword" style="font-weight: bold;">raise</span> NotImplementedError(<span class="hljs-string" style="color: #0048ab;">'must be implemented by subclass'</span>)
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">children</span><span class="hljs-params">(self,p)</span>:</span>
<span class="hljs-string" style="color: #0048ab;">"""
:param p: 一个位置对象
:return: 返回位置p的孩子的迭代
"""</span>
<span class="hljs-keyword" style="font-weight: bold;">raise</span> NotImplementedError(<span class="hljs-string" style="color: #0048ab;">'must be implemented by subclass'</span>)
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">__len__</span><span class="hljs-params">(self)</span>:</span>
<span class="hljs-string" style="color: #0048ab;">"""
:return: 返回整个树的节点个数
"""</span>
<span class="hljs-keyword" style="font-weight: bold;">raise NotImplementedError(<span class="hljs-string" style="color: #0048ab;">'must be implemented by subclass')
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">is_root</span><span class="hljs-params">(self,p)</span>:</span>
<span class="hljs-keyword" style="font-weight: bold;">return</span> self.root() == p
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">is_leaf</span><span class="hljs-params">(self,p)</span>:</span>
<span class="hljs-keyword" style="font-weight: bold;">return</span> self.num_children(p) == <span class="hljs-number">0</span>
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">is_empty</span><span class="hljs-params">(self)</span>:</span>
<span class="hljs-keyword" style="font-weight: bold;">return</span> len(self) == <span class="hljs-number">0</span>
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">这个抽象类中的方法必须在子类中实现才能调用，不然会产生NotImplementedError(‘must be implemented by subclass’)的异常
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">除此之外，对于Position()这个内嵌类可能较难理解，为什么要有这么一个内嵌类
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">这个内嵌类目前也是抽象类，具体方法都没有实现，但使用它的目的已经有了，就是将树中的节点进行封装，那为什么要封装节点呢？当调用树的相关方法时，节点可能为一个必要的参数，但我们手动传入时，实际上可以是任意的对象，这就会导致错误发生，所以我们必须保证传入的节点是节点的对象，同时也是本树对象的节点，不然就会弄混树与树的节点。同时将节点进行封装，可以避免使用者直接使用节点对象本身，相关节点的方法可以在封装成的Position对象调用。目前只是抽象类的定义，节点类等其他方法还未定义，后面还会看到具体的position对象的使用。
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">目前有了Tree这个抽象类，虽然其中的大多数方法还是抽象方法，但使用这些方法已经可以构成一些其他的功能了，所以就有了is_root，is_leaf，is_empty方法的定义。同时还可以定义计算节点的深度与高度的方法：
:
self.is_root(p):
:
+ self.depth(self.parent(p))
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def <span class="hljs-title" style="font-weight: bold; color: #0048ab;">height<span class="hljs-params">(self,p):
<span class="hljs-string" style="color: #0048ab;">"""
计算节点在树中的深度
"""
<span class="hljs-keyword" style="font-weight: bold;">if self.is_leaf(p):
<span class="hljs-keyword" style="font-weight: bold;">return <span class="hljs-number">0
<span class="hljs-keyword" style="font-weight: bold;">else:
<span class="hljs-keyword" style="font-weight: bold;">return <span class="hljs-number">1 + max(self.height(c) <span class="hljs-keyword" style="font-weight: bold;">for c <span class="hljs-keyword" style="font-weight: bold;">in self.children(p))
<h1 id="-" style="margin: 20px 0px 10px; padding: 0px; font-weight: bold; color: black; font-size: 24px; border-bottom: 2px solid #aaaaaa;">二叉树
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">我们现在介绍一种树的特殊化形式二叉树
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">二叉树的特点：
<ul style="margin: 1.2em 0px; padding-left: 2em; list-style-type: square; font-size: 16px;">
<li style="margin: 0.5em 0px; font-size: 16px;">
<p style="margin: 0.5em 0px !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">每个父节点最多只有两个孩子节点
:
<span class="hljs-class"><span class="hljs-keyword" style="font-weight: bold;">class</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">Node</span><span class="hljs-params">()</span>:</span>
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">__init__</span><span class="hljs-params">(self,element,parent=None,left=None,right=None)</span>:</span>
self.element = element
self.parent = parent
self.left = left
self.right = right
<span class="hljs-class"><span class="hljs-keyword" style="font-weight: bold;">class</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">Position</span><span class="hljs-params">(Tree.Position)</span>:</span>
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">__init__</span><span class="hljs-params">(self,container,node)</span>:</span>
self.container = container
self.node = node
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">element</span><span class="hljs-params">(self)</span>:</span>
<span class="hljs-keyword" style="font-weight: bold;">return</span> self.node.element
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">__eq__</span><span class="hljs-params">(self,other)</span>:</span>
<span class="hljs-keyword" style="font-weight: bold;">return</span> isinstance(other,type(self)) <span class="hljs-keyword" style="font-weight: bold;">and</span> other.node <span class="hljs-keyword" style="font-weight: bold;">is</span> self.node
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">validate</span><span class="hljs-params">(self,p)</span>:</span>
<span class="hljs-string" style="color: #0048ab;">"""
进行位置验证
"""</span>
<span class="hljs-keyword" style="font-weight: bold;">if</span> <span class="hljs-keyword" style="font-weight: bold;">not</span> isinstance(p,self.Position):
<span class="hljs-keyword" style="font-weight: bold;">raise</span> TypeError(<span class="hljs-string" style="color: #0048ab;">'p must be proper Position type'</span>)
<span class="hljs-keyword" style="font-weight: bold;">if</span> p.container <span class="hljs-keyword" style="font-weight: bold;">is</span> <span class="hljs-keyword" style="font-weight: bold;">not</span> self:
<span class="hljs-keyword" style="font-weight: bold;">raise</span> ValueError(<span class="hljs-string" style="color: #0048ab;">'p does not belong to this container'</span>)
<span class="hljs-keyword" style="font-weight: bold;">if</span> p.node.parent <span class="hljs-keyword" style="font-weight: bold;">is</span> p.node:
<span class="hljs-keyword" style="font-weight: bold;">raise</span> ValueError(<span class="hljs-string" style="color: #0048ab;">'p is no longer valid'</span>)
<span class="hljs-keyword" style="font-weight: bold;">return</span> p.node
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">make_position</span><span class="hljs-params">(self,node)</span>:</span>
<span class="hljs-string" style="color: #0048ab;">"""
封装节点
"""</span>
<span class="hljs-keyword" style="font-weight: bold;">return</span> self.Position(self,node) <span class="hljs-keyword" style="font-weight: bold;">if</span> node <span class="hljs-keyword" style="font-weight: bold;">is</span> <span class="hljs-keyword" style="font-weight: bold;">not</span> <span class="hljs-keyword" style="font-weight: bold;">None</span> <span class="hljs-keyword" style="font-weight: bold;">else</span> <span class="hljs-keyword" style="font-weight: bold;">None</span>
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">__init__</span><span class="hljs-params">(self)</span>:</span>
self.root = <span class="hljs-keyword" style="font-weight: bold;">None</span>
self.size = <span class="hljs-number">0</span>
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">__len__</span><span class="hljs-params">(self)</span>:</span>
<span class="hljs-keyword" style="font-weight: bold;">return</span> self.size
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">root</span><span class="hljs-params">(self)</span>:</span>
<span class="hljs-keyword" style="font-weight: bold;">return</span> self.make_position(self.root)
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">parent</span><span class="hljs-params">(self,p)</span>:</span>
node = self.validate(p)
<span class="hljs-keyword" style="font-weight: bold;">return</span> self.make_position(node.parent)
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">left</span><span class="hljs-params">(self,p)</span>:</span>
node = self.validate(p)
<span class="hljs-keyword" style="font-weight: bold;">return</span> self.make_position(node.left)
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">right</span><span class="hljs-params">(self,p)</span>:</span>
node = self.validate(p)
<span class="hljs-keyword" style="font-weight: bold;">return</span> self.make_position(node.right)
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">sibling</span><span class="hljs-params">(self,p)</span>:</span>
parent = self.parent(p)
<span class="hljs-keyword" style="font-weight: bold;">if</span> parent <span class="hljs-keyword" style="font-weight: bold;">is</span> <span class="hljs-keyword" style="font-weight: bold;">None</span>:
<span class="hljs-keyword" style="font-weight: bold;">return</span> <span class="hljs-keyword" style="font-weight: bold;">None</span>
<span class="hljs-keyword" style="font-weight: bold;">else</span>:
<span class="hljs-keyword" style="font-weight: bold;">if</span> p == self.left(parent):
<span class="hljs-keyword" style="font-weight: bold;">return</span> self.right(parent)
<span class="hljs-keyword" style="font-weight: bold;">else</span>:
<span class="hljs-keyword" style="font-weight: bold;">return</span> self.left(parent)
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">num_children</span><span class="hljs-params">(self,p)</span>:</span>
node = self.validate(p)
count = <span class="hljs-number">0</span>
<span class="hljs-keyword" style="font-weight: bold;">if</span> node.left <span class="hljs-keyword" style="font-weight: bold;">is</span> <span class="hljs-keyword" style="font-weight: bold;">not</span> <span class="hljs-keyword" style="font-weight: bold;">None</span>:
count += <span class="hljs-number">1</span>
<span class="hljs-keyword" style="font-weight: bold;">if</span> node.right <span class="hljs-keyword" style="font-weight: bold;">is</span> <span class="hljs-keyword" style="font-weight: bold;">not</span> <span class="hljs-keyword" style="font-weight: bold;">None</span>:
count += <span class="hljs-number">1</span>
<span class="hljs-keyword" style="font-weight: bold;">return</span> count
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def</span> <span class="hljs-title" style="font-weight: bold; color: #0048ab;">children</span><span class="hljs-params">(self,p)</span>:</span>
<span class="hljs-keyword" style="font-weight: bold;">if</span> self.left(p) <span class="hljs-keyword" style="font-weight: bold;">is</span> <span class="hljs-keyword" style="font-weight: bold;">not</span> <span class="hljs-keyword" style="font-weight: bold;">None</span>:
<span class="hljs-keyword" style="font-weight: bold;">yield</span> self.left(p)
<span class="hljs-keyword" style="font-weight: bold;">if</span> self.right(p) <span class="hljs-keyword" style="font-weight: bold;">is</span> <span class="hljs-keyword" style="font-weight: bold;">not</span> <span class="hljs-keyword" style="font-weight: bold;">None</span>:
<span class="hljs-keyword" style="font-weight: bold;">yield</span> self.right(p)
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">代码中将之前的抽象方法进行了完整的定义，同时添加了validate与make_position方法。validate方法用于对传入的position参数进行验证，make_position方法用于将节点进行封装。除此之外还添加了二叉树特有的方法right，left和sibling，left与right分别返回节点的左孩子节点与右孩子节点，sibling返回的是节点的兄弟节点。
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">目前的二叉树的数据结构只是创建了一颗空树，我们接下来要加入的是对二叉树进行更新操作的方法
:
self.root :
ValueError()
self.size +=
self.root = self.Node(e)
self.make_position(self.root)
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def <span class="hljs-title" style="font-weight: bold; color: #0048ab;">add_left<span class="hljs-params">(self,e,p):
node = self.validate(p)
<span class="hljs-keyword" style="font-weight: bold;">if node.left <span class="hljs-keyword" style="font-weight: bold;">is <span class="hljs-keyword" style="font-weight: bold;">not <span class="hljs-keyword" style="font-weight: bold;">None:
<span class="hljs-keyword" style="font-weight: bold;">raise ValueError(<span class="hljs-string" style="color: #0048ab;">'Left child exists')
self.size += <span class="hljs-number">1
node.left = self.Node(e,node)
<span class="hljs-keyword" style="font-weight: bold;">return self.make_position(node.left)
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def <span class="hljs-title" style="font-weight: bold; color: #0048ab;">add_right<span class="hljs-params">(self,p):
node = self.validate(p)
<span class="hljs-keyword" style="font-weight: bold;">if node.right <span class="hljs-keyword" style="font-weight: bold;">is <span class="hljs-keyword" style="font-weight: bold;">not <span class="hljs-keyword" style="font-weight: bold;">None:
<span class="hljs-keyword" style="font-weight: bold;">raise ValueError(<span class="hljs-string" style="color: #0048ab;">'Left child exists')
self.size += <span class="hljs-number">1
node.right = self.Node(e,node)
<span class="hljs-keyword" style="font-weight: bold;">return self.make_position(node.right)
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def <span class="hljs-title" style="font-weight: bold; color: #0048ab;">replace<span class="hljs-params">(self,p,e):
node = self.validate(p)
old = node.element
node.element = e
<span class="hljs-keyword" style="font-weight: bold;">return old
<span class="hljs-function"><span class="hljs-keyword" style="font-weight: bold;">def <span class="hljs-title" style="font-weight: bold; color: #0048ab;">delete<span class="hljs-params">(self,p):
<span class="hljs-string" style="color: #0048ab;">"""
删除该位置的节点，如果该节点有两个孩子，则会产生异常，如果只有一个孩子，
则使其孩子代替该节点与其双亲节点连接
"""
node = self.validate(p)
<span class="hljs-keyword" style="font-weight: bold;">if self.num_children(p) == <span class="hljs-number">2:
<span class="hljs-keyword" style="font-weight: bold;">raise ValueError(<span class="hljs-string" style="color: #0048ab;">'p has two children')
child = node.left <span class="hljs-keyword" style="font-weight: bold;">if node.left <span class="hljs-keyword" style="font-weight: bold;">else node.right
<span class="hljs-keyword" style="font-weight: bold;">if child <span class="hljs-keyword" style="font-weight: bold;">is <span class="hljs-keyword" style="font-weight: bold;">not <span class="hljs-keyword" style="font-weight: bold;">None:
child.parent = node.parent
<span class="hljs-keyword" style="font-weight: bold;">if node <span class="hljs-keyword" style="font-weight: bold;">is self.root:
self.root = child
<span class="hljs-keyword" style="font-weight: bold;">else:
parent = node.parent
<span class="hljs-keyword" style="font-weight: bold;">if node <span class="hljs-keyword" style="font-weight: bold;">is parent.left:
parent.left = child
<span class="hljs-keyword" style="font-weight: bold;">else:
parent.right = child
self.size -= <span class="hljs-number">1
node.parent = node
<span class="hljs-keyword" style="font-weight: bold;">return node.element
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">总共加入了添加根节点，添加左孩子，添加右孩子，代替元素和删除节点5个方法，其中删除几点稍微有一些复杂，因为涉及到许多情况的判断。
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">到现在，一个完整的二叉树数据结构基本完成了。
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">但是我们还需要掌握一个算法，就是树的遍历算法
<h1 id="-" style="margin: 20px 0px 10px; padding: 0px; font-weight: bold; color: black; font-size: 24px; border-bottom: 2px solid #aaaaaa;">树的遍历
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">树的遍历一般有先序遍历，后序遍历，广度优先遍历（层序遍历），对于二叉树还有中序遍历
<h3 id="-" style="margin: 20px 0px 10px; padding: 0px; font-weight: bold; color: black; font-size: 20px; border-bottom: 1px solid #aaaaaa;">先序遍历
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">先序遍历是按照根节点->从左到右的孩子节点的顺序遍历，而且把每个孩子节点看作是子树的根节点同样如此，例如：
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;"><img src="https://www.52php.cn/res/2019/02-05/23/cbf9b377f7adb6bc2a814c93171a4737.png" alt="" width="414" height="323">
<p style="margin: 0px 0px 1.2em !important; font-size: 16px; line-height: 1.75em; padding-right: 0.5em; padding-left: 0.5em;">用python实现先序遍历为：
:
p
c self.children(p):
other self.preorder(c):
other
根节点，如图：
:
c self.children(p):
other self.postorder(c):
other
p
:
self.is_empty():
queue = Queue()
queue.enqueue(self.root())
queue.is_empty():
p = queue.dequeue()
p
i self.children(p):
queue.enqueue(i)
父节点->右孩子
:
self.left(p) :
other self.inorder(self.left(p)):
other
self.right(p) :
other self.inorder(self.right(p)):
other
（编辑：李大同）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
