Python 中的树
请帮我理解一下Python中的树结构。这是我在网上找到的一个树的实现例子。
from collections import deque
class EmptyTree(object):
"""Represents an empty tree."""
# Supported methods
def isEmpty(self):
return True
def __str__(self):
return ""
def __iter__(self):
"""Iterator for the tree."""
return iter([])
def preorder(self, lyst):
return
def inorder(self, lyst):
return
def postorder(self, lyst):
return
class BinaryTree(object):
"""Represents a nonempty binary tree."""
# Singleton for all empty tree objects
THE_EMPTY_TREE = EmptyTree()
def __init__(self, item):
"""Creates a tree with
the given item at the root."""
self._root = item
self._left = BinaryTree.THE_EMPTY_TREE
self._right = BinaryTree.THE_EMPTY_TREE
def isEmpty(self):
return False
def getRoot(self):
return self._root
def getLeft(self):
return self._left
def getRight(self):
return self._right
def setRoot(self, item):
self._root = item
def setLeft(self, tree):
self._left = tree
def setRight(self, tree):
self._right = tree
def removeLeft(self):
left = self._left
self._left = BinaryTree.THE_EMPTY_TREE
return left
def removeRight(self):
right = self._right
self._right = BinaryTree.THE_EMPTY_TREE
return right
def __str__(self):
"""Returns a string representation of the tree
rotated 90 degrees to the left."""
def strHelper(tree, level):
result = ""
if not tree.isEmpty():
result += strHelper(tree.getRight(), level + 1)
result += " " * level
result += str(tree.getRoot()) + "\n"
result += strHelper(tree.getLeft(), level + 1)
return result
return strHelper(self, 0)
def __iter__(self):
"""Iterator for the tree."""
lyst = []
self.inorder(lyst)
return iter(lyst)
def preorder(self, lyst):
"""Adds items to lyst during
a preorder traversal."""
lyst.append(self.getRoot())
self.getLeft().preorder(lyst)
self.getRight().preorder(lyst)
def inorder(self, lyst):
"""Adds items to lyst during
an inorder traversal."""
self.getLeft().inorder(lyst)
lyst.append(self.getRoot())
self.getRight().inorder(lyst)
def postorder(self, lyst):
"""Adds items to lystduring
a postorder traversal."""
self.getLeft().postorder(lyst)
self.getRight().postorder(lyst)
lyst.append(self.getRoot())
def levelorder(self, lyst):
"""Adds items to lyst during
a levelorder traversal."""
# levelsQueue = LinkedQueue()
levelsQueue = deque ([])
levelsQueue.append(self)
while levelsQueue != deque():
node = levelsQueue.popleft()
lyst.append(node.getRoot())
left = node.getLeft()
right = node.getRight()
if not left.isEmpty():
levelsQueue.append(left)
if not right.isEmpty():
levelsQueue.append(right)
这是一个创建小树的程序。
"""
File: testbinarytree.py
Builds a full binary tree with 7 nodes.
"""
from binarytree import BinaryTree
lst = ["5", "+", "2"]
for i in range(len(lst)):
b = BinaryTree(lst[0])
d = BinaryTree(lst[1])
f = BinaryTree(lst[2])
# Build the tree from the bottom up, where
# d is the root node of the entire tree
d.setLeft(b)
d.setRight(f)
def size(tree):
if tree.isEmpty():
return 0
else:
return 1 + size(tree.getLeft()) + size(tree.getRight())
def frontier(tree):
"""Returns a list containing the leaf nodes
of tree."""
if tree.isEmpty():
return []
elif tree.getLeft().isEmpty() and tree.getRight().isEmpty():
return [tree.getRoot()]
else:
return frontier(tree.getLeft()) + frontier(tree.getRight())
print ("Size:", size(d))
print ("String:")
print (d)
我该如何创建一个类来计算表达式的值，让答案等于7（5+2）。我真的想通过一个简单的例子来理解这个概念。
3 个回答
0
你应该写一个函数，按照深度优先的顺序遍历一棵树，计算每个节点的值。对于每个节点，你可以直接取它的值（比如它是“5”），或者进行计算（比如它是“+”）。通过深度优先遍历，你可以确保在计算某个节点时，它的所有子节点都会先被计算出来（比如在计算“+”时，“5”和“2”会先被计算）。
最后，在树的根节点上，你就能得到整棵树的结果。
0
首先，我不想给太多细节，以免这是作业，听起来有点像。
你需要在你的树类里写一个方法，用来计算树的值。我想这个方法会假设每个树节点的“根”值是一个数字（当节点是叶子节点，也就是没有孩子的时候）或者是一个运算符的名字（当节点有孩子的时候）。
这个方法会用到递归：一个有孩子的树节点的值是由三个部分决定的：(1) 它左边子树的值，(2) 它右边子树的值，以及 (3) 它的“根”里的运算符。
你可能还需要一个表格——也许用一个 dict 来存储——把运算符的名字，比如 "+"，映射到实际的函数，比如 operator.add（或者，如果你喜欢的话，可以用 lambda x,y: x+y）。
1
听起来你的问题不是关于树的，这个概念其实比较简单和通用，而是关于如何正确地填充和评估一个表达式树。
如果你的运算符是按照后缀顺序排列的，那就简单多了。
可以看看这篇维基百科文章，讲的是如何处理中缀表示法，以便输入到桌面计算器中。这个方法叫做“调度算法”。