哪种数据结构最适合在Python中实现二叉树？
如何实现二叉树？
140
- Bruce
2
6这里有很多解决方案都在实现二叉搜索树，但问题要求实现二叉树。 - vikas mehta
也许在问题标题中指定你想要使用Python实现树算法？ - Ken Tran
21个回答
132
这是我简单的二叉搜索树的递归实现。
#!/bin/python
class Node:
def __init__(self, val):
self.l = None
self.r = None
self.v = val
class Tree:
def __init__(self):
self.root = None
def get_root(self):
return self.root
def add(self, val):
if not self.root:
self.root = Node(val)
else:
self._add(val, self.root)
def _add(self, val, node):
if val < node.v:
if node.l:
self._add(val, node.l)
else:
node.l = Node(val)
else:
if node.r:
self._add(val, node.r)
else:
node.r = Node(val)
def find(self, val):
if self.root:
return self._find(val, self.root)
def _find(self, val, node):
if val == node.v:
return node
elif val < node.v and node.l:
return self._find(val, node.l)
elif val > node.v and node.r:
return self._find(val, node.r)
def delete_tree(self):
# garbage collector will do this for us.
if self.root:
self.root = None
def view_tree(self):
if self.root:
self._view_tree(self.root)
def _view_tree(self, node):
if node:
self._view_tree(node.l)
print(node.v, end = " ")
self._view_tree(node.r)
# 3
# 0 4
# 2 8
tree = Tree()
tree.add(3)
tree.add(4)
tree.add(0)
tree.add(8)
tree.add(2)
tree.view_tree()
print(tree.find(3).v)
print(tree.find(10))
tree.delete_tree()
tree.view_tree()
- djra
9
22实现得不错。我只是想指出一些式风格的问题。Python通常使用
node is not None而不是(node!=None)。另外，您可以使用__str__函数代替printTree方法。 - Jeff Mandell2此外，您的_find函数可能应该是这样的：
def _find(self, val, node):
if(val == node.v):
return node
elif(val < node.v and node.l != None):
return self._find(val, node.l)
elif(val > node.v and node.r != None):
return self._find(val, node.r) - darkhipo5这不是一棵满足
left<=root<=right 的二叉搜索树吗？ - Sagar Shah4tree.find(0)，tree.find(2)，tree.find(4)和tree.find(8)都返回None。 - Tony Wang
4有一个小故障，当您尝试插入已存在的键时，它会沿着树向下创建一个带有重复键的新节点。 - Diego Gallegos
显示剩余4条评论
54
[面试需要什么] 一个节点类是足够的数据结构来表示一个二叉树。
(虽然其他答案大多数是正确的，但它们并不是二叉树所必需的：不需要扩展对象类，不需要是BST，不需要导入deque)。
class Node:
def __init__(self, value = None):
self.left = None
self.right = None
self.value = value
这是一棵树的例子：
n1 = Node(1)
n2 = Node(2)
n3 = Node(3)
n1.left = n2
n1.right = n3
- apadana
4
14其他答案对于二叉树来说过于复杂了。下面是二叉树实现所需的必要代码，我想只发表最基本的内容以帮助新手理解。其他答案适合用于文章和期刊论文；而这段代码也是软件面试中需要的。 - apadana
5它增加了简易性，这非常有价值。 - pylang
3简单而非常合乎逻辑。太好了，我喜欢它！ - Apostolos
添加这个图表真是太棒了！ - kd4ttc
30
# simple binary tree
# in this implementation, a node is inserted between an existing node and the root
class BinaryTree():
def __init__(self,rootid):
self.left = None
self.right = None
self.rootid = rootid
def getLeftChild(self):
return self.left
def getRightChild(self):
return self.right
def setNodeValue(self,value):
self.rootid = value
def getNodeValue(self):
return self.rootid
def insertRight(self,newNode):
if self.right == None:
self.right = BinaryTree(newNode)
else:
tree = BinaryTree(newNode)
tree.right = self.right
self.right = tree
def insertLeft(self,newNode):
if self.left == None:
self.left = BinaryTree(newNode)
else:
tree = BinaryTree(newNode)
tree.left = self.left
self.left = tree
def printTree(tree):
if tree != None:
printTree(tree.getLeftChild())
print(tree.getNodeValue())
printTree(tree.getRightChild())
# test tree
def testTree():
myTree = BinaryTree("Maud")
myTree.insertLeft("Bob")
myTree.insertRight("Tony")
myTree.insertRight("Steven")
printTree(myTree)
阅读更多信息：这是一个非常简单的二叉树实现。
这个是一个带有问题的不错的教程。
- Rahul
3
2
insertLeft 函数中的代码有问题，任何尝试递归遍历二叉树最左侧分支的操作都会导致无限循环。 - talonmies2可以通过交换以下行轻松解决：
tree.left = self.left
self.left = tree - Jagoda
1最后一个链接坏了，你能修复一下吗？ - Arjee
20
我不禁注意到这里大多数答案都是实现二叉搜索树。 二叉搜索树！=二叉树。
二叉搜索树具有非常特定的属性：对于任何节点X，X的键大于其左子节点的任何后代的键，并且小于其右子节点的任何后代的键。
二叉树没有这样的限制。 二叉树只是一个带有“键”元素和两个子元素（称为“左”和“右”）的数据结构。
树是二叉树的更一般情况，其中每个节点可以具有任意数量的子节点。 通常，每个节点都有一个类型为列表/数组的“children”元素。
现在，为了回答OP的问题，我在Python中包含了完整的二叉树实现。 存储每个BinaryTreeNode的底层数据结构是字典，因为它提供了最佳的O（1）查找。 我还实现了深度优先和广度优先遍历。 这些是在树上执行的非常常见的操作。
from collections import deque
class BinaryTreeNode:
def __init__(self, key, left=None, right=None):
self.key = key
self.left = left
self.right = right
def __repr__(self):
return "%s l: (%s) r: (%s)" % (self.key, self.left, self.right)
def __eq__(self, other):
if self.key == other.key and \
self.right == other.right and \
self.left == other.left:
return True
else:
return False
class BinaryTree:
def __init__(self, root_key=None):
# maps from BinaryTreeNode key to BinaryTreeNode instance.
# Thus, BinaryTreeNode keys must be unique.
self.nodes = {}
if root_key is not None:
# create a root BinaryTreeNode
self.root = BinaryTreeNode(root_key)
self.nodes[root_key] = self.root
def add(self, key, left_key=None, right_key=None):
if key not in self.nodes:
# BinaryTreeNode with given key does not exist, create it
self.nodes[key] = BinaryTreeNode(key)
# invariant: self.nodes[key] exists
# handle left child
if left_key is None:
self.nodes[key].left = None
else:
if left_key not in self.nodes:
self.nodes[left_key] = BinaryTreeNode(left_key)
# invariant: self.nodes[left_key] exists
self.nodes[key].left = self.nodes[left_key]
# handle right child
if right_key == None:
self.nodes[key].right = None
else:
if right_key not in self.nodes:
self.nodes[right_key] = BinaryTreeNode(right_key)
# invariant: self.nodes[right_key] exists
self.nodes[key].right = self.nodes[right_key]
def remove(self, key):
if key not in self.nodes:
raise ValueError('%s not in tree' % key)
# remove key from the list of nodes
del self.nodes[key]
# if node removed is left/right child, update parent node
for k in self.nodes:
if self.nodes[k].left and self.nodes[k].left.key == key:
self.nodes[k].left = None
if self.nodes[k].right and self.nodes[k].right.key == key:
self.nodes[k].right = None
return True
def _height(self, node):
if node is None:
return 0
else:
return 1 + max(self._height(node.left), self._height(node.right))
def height(self):
return self._height(self.root)
def size(self):
return len(self.nodes)
def __repr__(self):
return str(self.traverse_inorder(self.root))
def bfs(self, node):
if not node or node not in self.nodes:
return
reachable = []
q = deque()
# add starting node to queue
q.append(node)
while len(q):
visit = q.popleft()
# add currently visited BinaryTreeNode to list
reachable.append(visit)
# add left/right children as needed
if visit.left:
q.append(visit.left)
if visit.right:
q.append(visit.right)
return reachable
# visit left child, root, then right child
def traverse_inorder(self, node, reachable=None):
if not node or node.key not in self.nodes:
return
if reachable is None:
reachable = []
self.traverse_inorder(node.left, reachable)
reachable.append(node.key)
self.traverse_inorder(node.right, reachable)
return reachable
# visit left and right children, then root
# root of tree is always last to be visited
def traverse_postorder(self, node, reachable=None):
if not node or node.key not in self.nodes:
return
if reachable is None:
reachable = []
self.traverse_postorder(node.left, reachable)
self.traverse_postorder(node.right, reachable)
reachable.append(node.key)
return reachable
# visit root, left, then right children
# root is always visited first
def traverse_preorder(self, node, reachable=None):
if not node or node.key not in self.nodes:
return
if reachable is None:
reachable = []
reachable.append(node.key)
self.traverse_preorder(node.left, reachable)
self.traverse_preorder(node.right, reachable)
return reachable
- user8754646
1
关于“并非每个二叉树都是搜索树”的说法是正确的。因此，请不要将节点数据称为“键”。 - greybeard
11
Python中二叉搜索树的简单实现
class TreeNode:
def __init__(self, value):
self.left = None
self.right = None
self.data = value
class Tree:
def __init__(self):
self.root = None
def addNode(self, node, value):
if(node==None):
self.root = TreeNode(value)
else:
if(value<node.data):
if(node.left==None):
node.left = TreeNode(value)
else:
self.addNode(node.left, value)
else:
if(node.right==None):
node.right = TreeNode(value)
else:
self.addNode(node.right, value)
def printInorder(self, node):
if(node!=None):
self.printInorder(node.left)
print(node.data)
self.printInorder(node.right)
def main():
testTree = Tree()
testTree.addNode(testTree.root, 200)
testTree.addNode(testTree.root, 300)
testTree.addNode(testTree.root, 100)
testTree.addNode(testTree.root, 30)
testTree.printInorder(testTree.root)
- Fox
2
2你在一些句子末尾加了分号，而在另一些句子末尾没有加分号。能否请您解释一下这样做的原因？顺便说一句，我是Python初学者，所以问这样一个基础问题。 - outlier229
@outlier229 上面代码中的所有分号都是可选的，删除它们不会改变任何东西。我猜Fox只是习惯了像C++或Java这样需要在行末加上分号的语言。除了这种可选用法外，分号还可以用于将语句链接在单行中。例如a=1; b=2; c=3在Python中是有效的单行代码。 - physicsGuy
8
使用列表实现二叉树的一种快速且简单的方法。 这并不是最高效的方法，也无法很好地处理空值。 但它非常透明（至少对我来说）：
def _add(node, v):
new = [v, [], []]
if node:
left, right = node[1:]
if not left:
left.extend(new)
elif not right:
right.extend(new)
else:
_add(left, v)
else:
node.extend(new)
def binary_tree(s):
root = []
for e in s:
_add(root, e)
return root
def traverse(n, order):
if n:
v = n[0]
if order == 'pre':
yield v
for left in traverse(n[1], order):
yield left
if order == 'in':
yield v
for right in traverse(n[2], order):
yield right
if order == 'post':
yield v
从可迭代对象构建树：
>>> tree = binary_tree('A B C D E'.split())
>>> print tree
['A', ['B', ['D', [], []], ['E', [], []]], ['C', [], []]]
遍历一棵树：
>>> list(traverse(tree, 'pre')), list(traverse(tree, 'in')), list(traverse(tree, 'post'))
(['A', 'B', 'D', 'E', 'C'],
['D', 'B', 'E', 'A', 'C'],
['D', 'E', 'B', 'C', 'A'])
- p7k
1
非常好！我忍不住要评论一下，生成的树没有保持左子树中所有元素都小于v的不变量。这是二叉搜索树非常重要的一个属性。（是的，我意识到OP没有要求“搜索树”）然而，通过对_add()中的检查进行简单修改就可以实现。然后您的中序遍历将给出一个排序列表。 - thayne
6
一个基于节点的连接节点类是一种标准的方法。这些可能很难可视化。
受到关于Python模式-实现图形的论文的启发，考虑一个简单的字典：
给定
一棵二叉树
a
/ \
b c
/ \ \
d e f
代码
创建一个包含唯一节点的字典：
tree = {
"a": ["b", "c"],
"b": ["d", "e"],
"c": [None, "f"],
"d": [None, None],
"e": [None, None],
"f": [None, None],
}
详情
- 每个键值对都是指向其子节点的唯一节点。
- 列表（或元组）保存左/右子节点的有序对。
- 对于具有有序插入的字典，假设第一个条目是根。
- 常见方法可以是改变或遍历字典的函数（参见
find_all_paths()）。
基于树的函数通常包括以下常见操作：
- 遍历：按给定顺序（通常从左到右）产生每个节点
- 广度优先搜索（BFS）：遍历层级
- 深度优先搜索（DFS）：首先遍历分支（前/中/后序）
- 插入：根据子节点数量将节点添加到树中
- 删除：根据子节点数量移除节点
- 更新：从一个树合并缺失的节点到另一个树
- 访问：产生遍历节点的值
请尝试实现所有这些操作。在这里，我们演示其中之一 - BFS遍历：
示例
import collections as ct
def traverse(tree):
"""Yield nodes from a tree via BFS."""
q = ct.deque() # 1
root = next(iter(tree)) # 2
q.append(root)
while q:
node = q.popleft()
children = filter(None, tree.get(node))
for n in children: # 3
q.append(n)
yield node
list(traverse(tree))
# ['a', 'b', 'c', 'd', 'e', 'f']
这是一个应用于节点和子节点字典的广度优先搜索（层序）算法。
- 初始化FIFO队列。我们使用
deque，但queue或list也可以（后者效率较低）。 - 获取并将根节点入队（假设根节点是字典中的第一个条目，Python 3.6+）。
- 迭代地出队一个节点，将其子节点入队并返回节点值。
还可以参考这篇关于树的深入教程。
洞察
遍历算法的一个很棒的特点是，我们可以通过简单地用深度优先搜索（DFS）来替换队列为栈（即LIFO队列），从而轻松改变后面的迭代方法。这意味着我们从同一侧出队列入队列。DFS允许我们搜索每个分支。
怎么做？由于我们使用了deque，我们可以通过将node = q.popleft()更改为node = q.pop()（右边）来模拟一个栈。结果是一个右向的，预排序DFS：['a'，'c'，'f'，'b'，'e'，'d']。
- pylang
4
你不需要有两个类
class Tree:
val = None
left = None
right = None
def __init__(self, val):
self.val = val
def insert(self, val):
if self.val is not None:
if val < self.val:
if self.left is not None:
self.left.insert(val)
else:
self.left = Tree(val)
elif val > self.val:
if self.right is not None:
self.right.insert(val)
else:
self.right = Tree(val)
else:
return
else:
self.val = val
print("new node added")
def showTree(self):
if self.left is not None:
self.left.showTree()
print(self.val, end = ' ')
if self.right is not None:
self.right.showTree()
- dshri
4
8最好有两个课程。这样实施会更好。 - user3022012
1@user3022012，你的评论是完全错误的。按照定义，树由数据和子树组成（对于二叉树来说，它有两个子树），这些子树也是树。没有任何理由将根节点与其他节点区别对待。 - Guy
1原帖只要求二叉树实现，而不是二叉搜索树。 - Guy
（@Guy
原帖只是询问二叉树，关于删除的事情？） - greybeard2
更“Python化”一点？
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def __repr__(self):
return str(self.value)
class BST:
def __init__(self):
self.root = None
def __repr__(self):
self.sorted = []
self.get_inorder(self.root)
return str(self.sorted)
def get_inorder(self, node):
if node:
self.get_inorder(node.left)
self.sorted.append(str(node.value))
self.get_inorder(node.right)
def add(self, value):
if not self.root:
self.root = Node(value)
else:
self._add(self.root, value)
def _add(self, node, value):
if value <= node.value:
if node.left:
self._add(node.left, value)
else:
node.left = Node(value)
else:
if node.right:
self._add(node.right, value)
else:
node.right = Node(value)
from random import randint
bst = BST()
for i in range(100):
bst.add(randint(1, 1000))
print (bst)
- binithb
2
我知道已经有很多好的解决方案被发布了，但是对于二叉树，我通常采用不同的方法：使用一些节点类并直接实现它更易读，但当你有很多节点时，它可能会变得非常贪婪，涉及到内存，因此我建议增加一层复杂性，并将节点存储在Python列表中，然后仅使用该列表模拟树行为。
当需要时仍然可以定义一个Node类来最终表示树中的节点，但是将它们以简单形式[value，left，right]存储在列表中将使用一半或更少的内存！
这里是一个快速示例，演示了将节点存储在数组中的二叉搜索树类。它提供基本函数，如添加、删除、查找等...
"""
Basic Binary Search Tree class without recursion...
"""
__author__ = "@fbparis"
class Node(object):
__slots__ = "value", "parent", "left", "right"
def __init__(self, value, parent=None, left=None, right=None):
self.value = value
self.parent = parent
self.left = left
self.right = right
def __repr__(self):
return "<%s object at %s: parent=%s, left=%s, right=%s, value=%s>" % (self.__class__.__name__, hex(id(self)), self.parent, self.left, self.right, self.value)
class BinarySearchTree(object):
__slots__ = "_tree"
def __init__(self, *args):
self._tree = []
if args:
for x in args[0]:
self.add(x)
def __len__(self):
return len(self._tree)
def __repr__(self):
return "<%s object at %s with %d nodes>" % (self.__class__.__name__, hex(id(self)), len(self))
def __str__(self, nodes=None, level=0):
ret = ""
if nodes is None:
if len(self):
nodes = [0]
else:
nodes = []
for node in nodes:
if node is None:
continue
ret += "-" * level + " %s\n" % self._tree[node][0]
ret += self.__str__(self._tree[node][2:4], level + 1)
if level == 0:
ret = ret.strip()
return ret
def __contains__(self, value):
if len(self):
node_index = 0
while self._tree[node_index][0] != value:
if value < self._tree[node_index][0]:
node_index = self._tree[node_index][2]
else:
node_index = self._tree[node_index][3]
if node_index is None:
return False
return True
return False
def __eq__(self, other):
return self._tree == other._tree
def add(self, value):
if len(self):
node_index = 0
while self._tree[node_index][0] != value:
if value < self._tree[node_index][0]:
b = self._tree[node_index][2]
k = 2
else:
b = self._tree[node_index][3]
k = 3
if b is None:
self._tree[node_index][k] = len(self)
self._tree.append([value, node_index, None, None])
break
node_index = b
else:
self._tree.append([value, None, None, None])
def remove(self, value):
if len(self):
node_index = 0
while self._tree[node_index][0] != value:
if value < self._tree[node_index][0]:
node_index = self._tree[node_index][2]
else:
node_index = self._tree[node_index][3]
if node_index is None:
raise KeyError
if self._tree[node_index][2] is not None:
b, d = 2, 3
elif self._tree[node_index][3] is not None:
b, d = 3, 2
else:
i = node_index
b = None
if b is not None:
i = self._tree[node_index][b]
while self._tree[i][d] is not None:
i = self._tree[i][d]
p = self._tree[i][1]
b = self._tree[i][b]
if p == node_index:
self._tree[p][5-d] = b
else:
self._tree[p][d] = b
if b is not None:
self._tree[b][1] = p
self._tree[node_index][0] = self._tree[i][0]
else:
p = self._tree[i][1]
if p is not None:
if self._tree[p][2] == i:
self._tree[p][2] = None
else:
self._tree[p][3] = None
last = self._tree.pop()
n = len(self)
if i < n:
self._tree[i] = last[:]
if last[2] is not None:
self._tree[last[2]][1] = i
if last[3] is not None:
self._tree[last[3]][1] = i
if self._tree[last[1]][2] == n:
self._tree[last[1]][2] = i
else:
self._tree[last[1]][3] = i
else:
raise KeyError
def find(self, value):
if len(self):
node_index = 0
while self._tree[node_index][0] != value:
if value < self._tree[node_index][0]:
node_index = self._tree[node_index][2]
else:
node_index = self._tree[node_index][3]
if node_index is None:
return None
return Node(*self._tree[node_index])
return None
我添加了一个parent属性，这样您就可以删除任何节点并保持BST结构。
对于可读性问题，特别是“remove”函数，我很抱歉。基本上，当一个节点被删除时，我们弹出树数组，并用最后一个元素替换它（除非我们想要删除最后一个节点）。为了保持BST结构，被删除的节点将被其左子节点中的最大值或右子节点中的最小值所替换，并且需要进行一些操作以保持索引有效，但速度足够快。
我使用这种技术来构建一些带有内部基数字典树的高级内容，我能够将内存消耗降低7-8倍（您可以在此处看到示例：https://gist.github.com/fbparis/b3ddd5673b603b42c880974b23db7cda）
- fbparis
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接