文章/答案/技术大牛

发布

社区首页 >问答首页 >我如何让PreOrder，InOrder，PostOrder工作？

问我如何让PreOrder，InOrder，PostOrder工作？
EN

Stack Overflow用户

提问于 2021-03-20 08:35:26

回答 3查看 399关注 0票数 0

我是如何让PreOrder，InOrder，PostOrder工作的？

下面是我当前的代码和实现，请参阅InOrder()、PreOrder()、PostOrder()。我有来自Geek4Geek (https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/)的参考资料。

当我执行打印(bst.InOrder())时，它不会返回任何？

import os
import pygraphviz as pgv
from collections import deque
from IPython.display import Image, display

class BST:
    root=None

    def get(self,key):
        p = self.root
        while p is not None:
            if p.key == key:
                return p.val
            elif p.key > key: #if the key is smaller than current node, then go left (since left are all the small ones)
                p = p.left
            else:   # else if key is bigger than current node, go to right (since right are all the big ones)
                p = p.right 
        return None
        
    def put(self, key, val):
        self.root = self.put2(self.root, key, val)

    def put2(self, node, key, val):
        if node is None:
            #key is not in tree, create node and return node to parent
            return Node(key, val)
        if key < node.key:
            # key is in left subtree
            node.left = self.put2(node.left, key, val)
        elif key > node.key:
            # key is in right subtree
            node.right = self.put2(node.right, key, val)
        else:
            node.val = val
        return node

    # draw the graph
    def drawTree(self, filename):
        # create an empty undirected graph
        G=pgv.AGraph('graph myGraph {}')

        # create queue for breadth first search
        q = deque([self.root])
        # breadth first search traversal of the tree
        while len(q) != 0:
            node = q.popleft()
            G.add_node(node, label=node.key+":"+str(node.val))
            if node.left is not None:
                # draw the left node and edge
                G.add_node(node.left, label=node.left.key+":"+str(node.left.val))
                G.add_edge(node, node.left)
                q.append(node.left)
            if node.right is not None:
                # draw the right node and edge
                G.add_node(node.right, label=node.right.key+":"+str(node.right.val))
                G.add_edge(node, node.right)
                q.append(node.right)

        # render graph into PNG file
        G.draw(filename,prog='dot')
        display(Image(filename))

    def createTree(self):
        self.put("F",6)
        self.put('I',9)
        self.put("J",10)
        self.put("G",7)
        self.put("H",8)
        # left side of F:6
        self.put("D",4)
        self.put("C",3)
        self.put("B",2)
        self.put("A",1)
        self.put("E",5)

   

    def createBalancedTree(self):
      self.put("F",6)
      self.put("A",1)
      self.put("B",2)
      self.put("C",3)
      self.put("D",4)
      self.put("E",5)
      self.put("G",7)
      self.put("H",8)
      self.put('I',9)
      self.put("J",10)
    
    def find(self, key):
        p = self.root
        while p is not None:
            if p.key == key:
                return p
            elif p.key > key:
                p = p.left
            else:
                p = p.right
        return

    def size(self,key): 
      return self.size2(self.find(key)) #using the find function which gives the node instead
    
    def size2(self, subtree):
      if not subtree: #if given key is not found in entire tree (means not a node in this tree)
        return 0
      else:
        return 1 + self.size2(subtree.left) + self.size2(subtree.right)
    

    def depth(self,key):
      p = self.root                         # set the default node as Root, since we start from Root then top-bottom approach. 
      if p is not None:
        if p.key == key:                    # if key is root, then return 0 (cus at Root, there is no depth)
          return 0
        elif p.key > key:                   # if Key is smaller than current node, then search in the left side 
          return self.depth2(p.left,key,0)
        else:                               # if key is bigger than current node, search the right side 
          return self.depth2(p.right,key,0)
    
    def depth2(self,node,key,counter):
      # lets say you put a depth(Z), at depth(), it wouldt know Z exits or not, so it will call depth2() to find out. In depth2(), It will check 'Z' throughtout node.key>key and node.key<key..
      # still cannot find after all the iteration, then it will return None
      if node is not None:                 
        if node.key > key:        
          return self.depth2(node.left,key,counter+1)
        elif node.key < key:                     
          return self.depth2(node.right,key,counter+1)
        elif node.key == key:   
          return counter + 1  # this code will only run when you find your key. So example you do depth(E), it will start from F, then D, then found E. In total 2
      else:
        return None
    

 
    def height(self,key):
      x = self.root
      if x == key:
        return 0
      else:
        return self.height2(self.find(key))
    
    def height2(self,subtree):
        if not subtree:
          return -1 #Key is not a node in the tree
        else:
          return max(self.height2(subtree.left), self.height2(subtree.right)) + 1
    

    def InOrder(self):
      if self == self.root:
        InOrder(self.left)
        print(self.key)
        InOrder(self.right)
    
    #def PreOrder(self):
    #def PostOrder(self):
        
      
class Node:
    left = None
    right = None
    key = 0
    val = 0

    def __init__(self, key, val):
        self.key = key
        self.val = val

我该怎么做才能让指纹起作用？

binary-search-tree

root

python

recursion

key

回答 3

Stack Overflow用户

回答已采纳

发布于 2021-03-20 16:26:08

代码检查和修复

第一个问题是size使用get，它返回树的值，而不是节点。为了解决这个问题，我们将get函数重写为find，但这次它返回一个节点-

class BST:
    root=None
    
    def put(self, key, val): # ...
    def put2(self, node, key, val): # ...
    def createTree(self): # ...
    def createBalancedTree(self): # ...

    def find(self,key):
        p = self.root
        while p is not None:
            if p.key == key:
                return p       # return p
            elif p.key > key:
                p = p.left
            else:
                p = p.right 

        return None            # return None, not "None"

我们不需要在get中重复这个逻辑。相反，我们调用find来获取节点。如果节点存在，则返回值-

class BST:
    # ...

    def get(self, key):
      p = self.find(key)       # call to find
      if not p:
        return None
      else:
        return p.val           # return p.val

接下来，在size函数中，我们将使用find来获取节点。类似于编写put2助手的方式，我们可以编写处理循环的size2 -

class BST:
    # ...

    def size(self,key):
      return self.size2(self.find(key)) # find, not get

    def size2(self, subtree):           # define size2 like you did put2
      if not subtree:
        return 0
      else:
        return 1 + self.size2(subtree.left) + self.size2(subtree.right)

这意味着我们没有在size类中定义Node -

class Node:
    left = None
    right = None
    key = 0
    val = 0

    def __init__(self, key, val):
        self.key = key
        self.val = val

    # do not define "size" on the Node class

让我们用你的createBalancedTree()测试一下-

bst = BST()
bst.createBalancedTree()

#   F
#  / \
# A   G
#  \   \
#   B   H
#    \   \
#     C   I
#      \   \
#       D   J
#        \
#         E

print(bst.size('F')) # 10
print(bst.size('A')) # 5
print(bst.size('H')) # 3
print(bst.size('D')) # 2

高度

在您的帮助下，

也进行了更新，我尝试了同样的方法来查找身高()，但是它返回错误的路径。

我们可以编写类似于height的size -

class BST:
    # ...
    def height(self,key):
      return self.height2(self.find(key))
    
    def height2(self,subtree):
        if not subtree:
            return 0 
        else:
            return max(self.height2(subtree.left), self.height2(subtree.right)) + 1

深度

所以，如果我做一个深度(‘B’)，它应该返回3。因为B到F，深度级别是3。如果我做一个深度(‘F’)，它应该返回0。因为根F中没有深度

我们可以写depth非常类似于我们写find的方式-

class BST:
    # ...
    def depth(self,key):
        p = self.root
        d = 0
        while p is not None:
            if p.key == key:
                return d
            elif p.key > key:
                p = p.left
            else:
                p = p.right
            d = d + 1 
        return None

你做得很好！您的代码没有问题，如下所示-

bst2 = BST()
bst2.createTree()

#          F
#        /   \
#       D     I
#      / \   / \
#     C   E G   J
#    /       \
#   B         H
#  /
# A 

print(bst2.depth("F")) # 5
print(bst2.depth("I")) # 3
print(bst2.depth("B")) # 2
print(bst2.depth("Z")) # 0

improvements

，你能解释一下为什么需要put2和size2吗？对不起，我没有拿put2.这是我的作业的代码

您实际上并不需要put2或size2，我会说它们是一种糟糕的实践。问题是，所有的树逻辑都纠缠在类中。在答案的这一节中，我将向您展示对bst模块的全面修订。

首先，我们从一个基本的节点接口开始。我们需要一个简单的__init__构造函数，而不是分配属性。key和val是必需的。left和right是可选的，如果没有指定，则默认为None -

# bst.py

class node:
  def __init__(self, key, val, left = None, right = None):
    self.key = key
    self.val = val
    self.left = left
    self.right = right

现在我们编写一个普通的put函数。注意，没有引用像self这样的特殊变量。另一件重要的事情是，我们从不通过重新分配left或right属性来改变(覆盖)节点。而是创建了一个新的node -

# bst.py (continued)

def put(t, k, v):
  if not t:
    return node(k, v)
  elif k < t.key:
    return node(t.key, t.val, put(t.left, k, v), t.right)
  elif k > t.key:
    return node(t.key, t.val, t.left, put(t.right, k, v))
  else:
    return node(t.key, v, t.left, t.right)

我们将继续以这种方式编写普通函数。接下来，我们定义get，它是find的一个专门化-

# bst.py (continued)

def get(t, k):
  r = find(t, k)
  if not r:
    return None
  else:
    return r.val

def find(t, k):
  if not t:
    return None
  elif k < t.key:
    return find(t.left, k)
  elif k > t.key:
    return find(t.right, k)
  else:
    return t

在这里，我们将偏离size一点。这一次，它将不采用key参数。相反，调用方将能够在任何节点上调用size。使用情况如下所示-

# bst.py (continued)

def size(t):
  if not t:
    return 0
  else:
    return 1 + size(t.left) + size(t.right)

如果我们可以从节点列表中构建树，那将是很方便的。这是对createBalancedTree的一个改进，后者一次又一次地调用.put。我们可以叫它from_list -

# main.py

nodes = \
  [("F",6), ("A",1), ("B",2), ("C",3), ("D",4), ("E",5), ("G",7), ("H",8), ('I',9), ("J",10)]

t = bst.from_list(nodes)

我们可以在我们的from_list模块中轻松地实现bst -

# bst.py (continued)

def from_list(l):
  t = None
  for (k,v) in l:
    t = put(t, k, v)
  return t

这是模块最大的区别。我们编写bst类，但它是一个简单的包装器，它包含普通函数put、find、get、size和from_list。全班没有复杂的逻辑-

# bst.py (continued)

class bst:
  def __init__(self, t): self.t = t
  def put(self, k, v): return bst(put(self.t, k, v))
  def find(self, k): return bst(find(self.t, k))
  def get(self, k): return get(self.t, k)
  def size(self): return size(self.t)
  def from_list(l): return bst(from_list(l))

我们都完了。我们将编写我们的main程序，从我们的bst模块导入-

# main.py

from bst import bst

nodes = \
  [("F",6), ("A",1), ("B",2), ("C",3), ("D",4), ("E",5), ("G",7), ("H",8), ('I',9), ("J",10)]

t = bst.from_list(nodes)
#   F
#  / \
# A   G
#  \   \
#   B   H
#    \   \
#     C   I
#      \   \
#       D   J
#        \
#         E

还记得我说过size不使用key参数吗？这是因为它可以在任何节点上调用。因此，要找到特定节点的大小，我们首先find它，然后size它！这是编写可重用函数的核心原则:每个函数只应该做一件事-

print(t.find('F').size()) # 10
print(t.find('A').size()) # 5
print(t.find('H').size()) # 3
print(t.find('D').size()) # 2

泛函

我们所使用的技术的一个被低估的优点是，我们的bst模块可以以面向对象的方式(如上图)或以功能的方式使用(如下所示)。这种双重界面使我们的模块非常灵活，因为它可以在多种风格中使用-

# functional.py

from bst import from_list, find, size

nodes = \
  [("F",6), ("A",1), ("B",2), ("C",3), ("D",4), ("E",5), ("G",7), ("H",8), ('I',9), ("J",10)]

t = from_list(nodes)

print(size(find(t, 'F'))) # 10
print(size(find(t, 'A'))) # 5
print(size(find(t, 'H'))) # 3
print(size(find(t, 'D'))) # 2

附加读数

我写了很多关于这个答案所使用的技巧的文章。请按照链接查看在其他上下文中使用的链接，并提供其他解释-

Deleting node in BST Python

I want to reverse the stack but i dont know how to use recursion for reversing this… How can i reverse the stack without using Recursion

Finding all maze solutions with Python

Return middle node of linked list with recursion

票数 1

Stack Overflow用户

发布于 2021-03-20 09:27:06

在我看来你的停车条件是不正确的。子(和根)的默认值是None，因此您应该检查z == None。而且，您似乎混淆了子节点和密钥。在我看来，最好的方法是首先找到具有所需密钥的节点，然后在该节点上递归地计算子树大小。请看下面的代码。

# a function in the BST class that finds the node with a specific key
class BST:
    def find(self, key):
        p = self.root
        while p is not None:
            if p.key == key:
                return p
            elif p.key > key:
                p = p.left
            else:
                p = p.right
        return

    # the function that you asked about
    def getSize(self, key):
        subroot = self.find(key)
        if subroot:
            return subroot.size()
        return 0 # if the key is not found return zero

# a function in the node class to find the subtree size with that node as root
class Node:
    def size(self): 
      return 1 + (self.left.size() if self.left else 0) + (self.right.size() if self.right else 0)

票数 0

Stack Overflow用户

发布于 2021-03-21 16:06:19

无序

您应该为有关此代码的每一个独特的问题打开新的帖子。目前的问题与原来的问题有很大的出入。无论如何，按照现有代码的模式，下面是我如何处理inorder的方法-

class BST:
    # ...
    def inorder(self):
        return self.inorder2(self.root)

    def inorder2(self, t):
        if not t: return
        yield from self.inorder2(t.left)
        yield (t.key, t.val)
        yield from self.inorder2(t.right)

另一种写这个的方法是使用嵌套函数-

class BST:
    # ...
    def inorder(self):
        def loop(t):
            if not t: return
            yield from loop(t.left)
            yield t
            yield from loop(t.right)
        return loop(self.root)

注意print是如何与inorder函数分离的。这允许调用方使用遍历逻辑，并为每个节点选择要执行的操作-

for node in bst.inorder():
  print(node.key, node.val)

可重用性

在定义了inorder之后，可以在BST类中重新定义一些其他函数-

class BST:
  # ...
  def find(self, key):
    for node in self.inorder():
      if node.key == key:
        return node

  def size(self, key):
    p = self.find(key)
    if not p: return 0
    return sum(1 for _ in BST(p).inorder())

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/66719637

复制

相似问题

问我如何让PreOrder，InOrder，PostOrder工作？
EN

回答 3

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问我如何让PreOrder，InOrder，PostOrder工作？EN

回答 3

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问我如何让PreOrder，InOrder，PostOrder工作？
EN