如何实现二叉树？

哪种数据结构最适合在 Python 中实现二叉树？

267129 次浏览
小开 
# 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)

这是一个非常简单的二叉树 实施。

这个 是一个很好的教程，中间有一些问题

小开 
import random


class TreeNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.p = None


class BinaryTree:
def __init__(self):
self.root = None


def length(self):
return self.size


def inorder(self, node):
if node == None:
return None
else:
self.inorder(node.left)
print node.key,
self.inorder(node.right)


def search(self, k):
node = self.root
while node != None:
if node.key == k:
return node
if node.key > k:
node = node.left
else:
node = node.right
return None


def minimum(self, node):
x = None
while node.left != None:
x = node.left
node = node.left
return x


def maximum(self, node):
x = None
while node.right != None:
x = node.right
node = node.right
return x


def successor(self, node):
parent = None
if node.right != None:
return self.minimum(node.right)
parent = node.p
while parent != None and node == parent.right:
node = parent
parent = parent.p
return parent


def predecessor(self, node):
parent = None
if node.left != None:
return self.maximum(node.left)
parent = node.p
while parent != None and node == parent.left:
node = parent
parent = parent.p
return parent


def insert(self, k):
t = TreeNode(k)
parent = None
node = self.root
while node != None:
parent = node
if node.key > t.key:
node = node.left
else:
node = node.right
t.p = parent
if parent == None:
self.root = t
elif t.key < parent.key:
parent.left = t
else:
parent.right = t
return t




def delete(self, node):
if node.left == None:
self.transplant(node, node.right)
elif node.right == None:
self.transplant(node, node.left)
else:
succ = self.minimum(node.right)
if succ.p != node:
self.transplant(succ, succ.right)
succ.right = node.right
succ.right.p = succ
self.transplant(node, succ)
succ.left = node.left
succ.left.p = succ


def transplant(self, node, newnode):
if node.p == None:
self.root = newnode
elif node == node.p.left:
node.p.left = newnode
else:
node.p.right = newnode
if newnode != None:
newnode.p = node.p
小开

使用列表实现二叉树的一种非常快速而肮脏的方法。 它不是最有效的，也不能很好地处理空值。 但这是非常透明的(至少对我来说) :

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'])
小开

下面是我的二叉查找树的简单递归实现。

#!/usr/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 getRoot(self):
return self.root


def add(self, val):
if self.root is None:
self.root = Node(val)
else:
self._add(val, self.root)


def _add(self, val, node):
if val < node.v:
if node.l is not None:
self._add(val, node.l)
else:
node.l = Node(val)
else:
if node.r is not None:
self._add(val, node.r)
else:
node.r = Node(val)


def find(self, val):
if self.root is not None:
return self._find(val, self.root)
else:
return None


def _find(self, val, node):
if val == node.v:
return node
elif (val < node.v and node.l is not None):
return self._find(val, node.l)
elif (val > node.v and node.r is not None):
return self._find(val, node.r)


def deleteTree(self):
# garbage collector will do this for us.
self.root = None


def printTree(self):
if self.root is not None:
self._printTree(self.root)


def _printTree(self, node):
if node is not None:
self._printTree(node.l)
print(str(node.v) + ' ')
self._printTree(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.printTree()
print(tree.find(3).v)
print(tree.find(10))
tree.deleteTree()
tree.printTree()
小开

你不需要上两节课

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()
小开

Python 中 BST 的简单实现

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)
小开

Python 中的二叉树

 class Tree(object):
def __init__(self):
self.data=None
self.left=None
self.right=None
def insert(self, x, root):
if root==None:
t=node(x)
t.data=x
t.right=None
t.left=None
root=t
return root
elif x<root.data:
root.left=self.insert(x, root.left)
else:
root.right=self.insert(x, root.right)
return root


def printTree(self, t):
if t==None:
return


self.printTree(t.left)
print t.data
self.printTree(t.right)


class node(object):
def __init__(self, x):
self.x=x


bt=Tree()
root=None
n=int(raw_input())
a=[]
for i in range(n):
a.append(int(raw_input()))
for i in range(n):
root=bt.insert(a[i], root)
bt.printTree(root)
小开

再“蟒蛇”一点？

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)
小开 
#!/usr/bin/python


class BinaryTree:
def __init__(self, left, right, data):
self.left = left
self.right = right
self.data = data




def pre_order_traversal(root):
print(root.data, end=' ')


if root.left != None:
pre_order_traversal(root.left)


if root.right != None:
pre_order_traversal(root.right)


def in_order_traversal(root):
if root.left != None:
in_order_traversal(root.left)
print(root.data, end=' ')
if root.right != None:
in_order_traversal(root.right)


def post_order_traversal(root):
if root.left != None:
post_order_traversal(root.left)
if root.right != None:
post_order_traversal(root.right)
print(root.data, end=' ')
小开

该实现支持插入、查找和删除操作，而不会破坏树的结构。这不是一棵平衡的树。

# Class for construct the nodes of the tree. (Subtrees)
class Node:
def __init__(self, key, parent_node = None):
self.left = None
self.right = None
self.key = key
if parent_node == None:
self.parent = self
else:
self.parent = parent_node


# Class with the  structure of the tree.
# This Tree is not balanced.
class Tree:
def __init__(self):
self.root = None


# Insert a single element
def insert(self, x):
if(self.root == None):
self.root = Node(x)
else:
self._insert(x, self.root)


def _insert(self, x, node):
if(x < node.key):
if(node.left == None):
node.left = Node(x, node)
else:
self._insert(x, node.left)
else:
if(node.right == None):
node.right = Node(x, node)
else:
self._insert(x, node.right)


# Given a element, return a node in the tree with key x.
def find(self, x):
if(self.root == None):
return None
else:
return self._find(x, self.root)
def _find(self, x, node):
if(x == node.key):
return node
elif(x < node.key):
if(node.left == None):
return None
else:
return self._find(x, node.left)
elif(x > node.key):
if(node.right == None):
return None
else:
return self._find(x, node.right)


# Given a node, return the node in the tree with the next largest element.
def next(self, node):
if node.right != None:
return self._left_descendant(node.right)
else:
return self._right_ancestor(node)


def _left_descendant(self, node):
if node.left == None:
return node
else:
return self._left_descendant(node.left)


def _right_ancestor(self, node):
if node.key <= node.parent.key:
return node.parent
else:
return self._right_ancestor(node.parent)


# Delete an element of the tree
def delete(self, x):
node = self.find(x)
if node == None:
print(x, "isn't in the tree")
else:
if node.right == None:
if node.left == None:
if node.key < node.parent.key:
node.parent.left = None
del node # Clean garbage
else:
node.parent.right = None
del Node # Clean garbage
else:
node.key = node.left.key
node.left = None
else:
x = self.next(node)
node.key = x.key
x = None




# tests
t = Tree()
t.insert(5)
t.insert(8)
t.insert(3)
t.insert(4)
t.insert(6)
t.insert(2)


t.delete(8)
t.delete(5)


t.insert(9)
t.insert(1)


t.delete(2)
t.delete(100)


# Remember: Find method return the node object.
# To return a number use t.find(nº).key
# But it will cause an error if the number is not in the tree.
print(t.find(5))
print(t.find(8))
print(t.find(4))
print(t.find(6))
print(t.find(9))
小开

我不禁注意到，这里的大多数答案都实现了一种二叉查找树。二叉查找树！= 二叉树。

  • 二叉查找树有一个非常特殊的属性: 对于任何节点 x，x 的键大于其左子节点的任何子节点的键，小于其右子节点的任何子节点的键。

  • 二叉树没有这样的限制。二叉树是一个简单的数据结构，带有一个“ key”元素，两个子元素，分别是“ left”和“ right”。

  • Tree 是二叉树的一种更一般的情况，其中每个节点可以有任意数量的子节点。通常，每个节点都有一个类型为 list/array 的“ 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
小开

这里有一个简单的解决方案，它可以用来建立一个二叉树使用递归的方法来显示树的顺序遍历已在下面的代码中使用。

class Node(object):


def __init__(self):
self.left = None
self.right = None
self.value = None
@property
def get_value(self):
return self.value


@property
def get_left(self):
return self.left


@property
def get_right(self):
return self.right


@get_left.setter
def set_left(self, left_node):
self.left = left_node
@get_value.setter
def set_value(self, value):
self.value = value
@get_right.setter
def set_right(self, right_node):
self.right = right_node






def create_tree(self):
_node = Node() #creating new node.
_x = input("Enter the node data(-1 for null)")
if(_x == str(-1)): #for defining no child.
return None
_node.set_value = _x #setting the value of the node.
print("Enter the left child of {}".format(_x))
_node.set_left = self.create_tree() #setting the left subtree
print("Enter the right child of {}".format(_x))
_node.set_right = self.create_tree() #setting the right subtree.


return _node


def pre_order(self, root):
if root is not None:
print(root.get_value)
self.pre_order(root.get_left)
self.pre_order(root.get_right)


if __name__ == '__main__':
node = Node()
root_node = node.create_tree()
node.pre_order(root_node)

代码来自: Python 中的二叉树

小开

Node 类是足以表示二叉树的数据结构。

(虽然其他答案大部分是正确的，但它们不需要用于二叉树: 不需要扩展对象类，不需要是 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

在这个例子中，n1是树的根，它的子树是 n2，n3。

enter image description here

小开

二进制 搜索树的一个很好的实现，取自 给你:

'''
A binary search Tree
'''
from __future__ import print_function
class Node:


def __init__(self, label, parent):
self.label = label
self.left = None
self.right = None
#Added in order to delete a node easier
self.parent = parent


def getLabel(self):
return self.label


def setLabel(self, label):
self.label = label


def getLeft(self):
return self.left


def setLeft(self, left):
self.left = left


def getRight(self):
return self.right


def setRight(self, right):
self.right = right


def getParent(self):
return self.parent


def setParent(self, parent):
self.parent = parent


class BinarySearchTree:


def __init__(self):
self.root = None


def insert(self, label):
# Create a new Node
new_node = Node(label, None)
# If Tree is empty
if self.empty():
self.root = new_node
else:
#If Tree is not empty
curr_node = self.root
#While we don't get to a leaf
while curr_node is not None:
#We keep reference of the parent node
parent_node = curr_node
#If node label is less than current node
if new_node.getLabel() < curr_node.getLabel():
#We go left
curr_node = curr_node.getLeft()
else:
#Else we go right
curr_node = curr_node.getRight()
#We insert the new node in a leaf
if new_node.getLabel() < parent_node.getLabel():
parent_node.setLeft(new_node)
else:
parent_node.setRight(new_node)
#Set parent to the new node
new_node.setParent(parent_node)


def delete(self, label):
if (not self.empty()):
#Look for the node with that label
node = self.getNode(label)
#If the node exists
if(node is not None):
#If it has no children
if(node.getLeft() is None and node.getRight() is None):
self.__reassignNodes(node, None)
node = None
#Has only right children
elif(node.getLeft() is None and node.getRight() is not None):
self.__reassignNodes(node, node.getRight())
#Has only left children
elif(node.getLeft() is not None and node.getRight() is None):
self.__reassignNodes(node, node.getLeft())
#Has two children
else:
#Gets the max value of the left branch
tmpNode = self.getMax(node.getLeft())
#Deletes the tmpNode
self.delete(tmpNode.getLabel())
#Assigns the value to the node to delete and keesp tree structure
node.setLabel(tmpNode.getLabel())


def getNode(self, label):
curr_node = None
#If the tree is not empty
if(not self.empty()):
#Get tree root
curr_node = self.getRoot()
#While we don't find the node we look for
#I am using lazy evaluation here to avoid NoneType Attribute error
while curr_node is not None and curr_node.getLabel() is not label:
#If node label is less than current node
if label < curr_node.getLabel():
#We go left
curr_node = curr_node.getLeft()
else:
#Else we go right
curr_node = curr_node.getRight()
return curr_node


def getMax(self, root = None):
if(root is not None):
curr_node = root
else:
#We go deep on the right branch
curr_node = self.getRoot()
if(not self.empty()):
while(curr_node.getRight() is not None):
curr_node = curr_node.getRight()
return curr_node


def getMin(self, root = None):
if(root is not None):
curr_node = root
else:
#We go deep on the left branch
curr_node = self.getRoot()
if(not self.empty()):
curr_node = self.getRoot()
while(curr_node.getLeft() is not None):
curr_node = curr_node.getLeft()
return curr_node


def empty(self):
if self.root is None:
return True
return False


def __InOrderTraversal(self, curr_node):
nodeList = []
if curr_node is not None:
nodeList.insert(0, curr_node)
nodeList = nodeList + self.__InOrderTraversal(curr_node.getLeft())
nodeList = nodeList + self.__InOrderTraversal(curr_node.getRight())
return nodeList


def getRoot(self):
return self.root


def __isRightChildren(self, node):
if(node == node.getParent().getRight()):
return True
return False


def __reassignNodes(self, node, newChildren):
if(newChildren is not None):
newChildren.setParent(node.getParent())
if(node.getParent() is not None):
#If it is the Right Children
if(self.__isRightChildren(node)):
node.getParent().setRight(newChildren)
else:
#Else it is the left children
node.getParent().setLeft(newChildren)


#This function traversal the tree. By default it returns an
#In order traversal list. You can pass a function to traversal
#The tree as needed by client code
def traversalTree(self, traversalFunction = None, root = None):
if(traversalFunction is None):
#Returns a list of nodes in preOrder by default
return self.__InOrderTraversal(self.root)
else:
#Returns a list of nodes in the order that the users wants to
return traversalFunction(self.root)


#Returns an string of all the nodes labels in the list
#In Order Traversal
def __str__(self):
list = self.__InOrderTraversal(self.root)
str = ""
for x in list:
str = str + " " + x.getLabel().__str__()
return str


def InPreOrder(curr_node):
nodeList = []
if curr_node is not None:
nodeList = nodeList + InPreOrder(curr_node.getLeft())
nodeList.insert(0, curr_node.getLabel())
nodeList = nodeList + InPreOrder(curr_node.getRight())
return nodeList


def testBinarySearchTree():
r'''
Example
8
/ \
3   10
/ \    \
1   6    14
/ \   /
4   7 13
'''


r'''
Example After Deletion
7
/ \
1   4


'''
t = BinarySearchTree()
t.insert(8)
t.insert(3)
t.insert(6)
t.insert(1)
t.insert(10)
t.insert(14)
t.insert(13)
t.insert(4)
t.insert(7)


#Prints all the elements of the list in order traversal
print(t.__str__())


if(t.getNode(6) is not None):
print("The label 6 exists")
else:
print("The label 6 doesn't exist")


if(t.getNode(-1) is not None):
print("The label -1 exists")
else:
print("The label -1 doesn't exist")


if(not t.empty()):
print(("Max Value: ", t.getMax().getLabel()))
print(("Min Value: ", t.getMin().getLabel()))


t.delete(13)
t.delete(10)
t.delete(8)
t.delete(3)
t.delete(6)
t.delete(14)


#Gets all the elements of the tree In pre order
#And it prints them
list = t.traversalTree(InPreOrder, t.root)
for x in list:
print(x)


if __name__ == "__main__":
testBinarySearchTree()
小开

我知道已经有很多很好的解决方案，但是我通常对二叉树有不同的方法: 使用一些 Node 类并直接实现它更具可读性，但是当你有很多节点时，它会变得对内存非常贪婪，所以我建议增加一层复杂性并将节点存储在一个 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

我添加了一个父属性，这样您就可以删除任何节点并维护 BST 结构。

对于可读性感到抱歉，特别是对于“删除”功能。基本上，当删除一个节点时，我们弹出树数组并用最后一个元素替换它(除非我们想删除最后一个节点)。为了维护 BST 结构，删除的节点被替换为其左子节点的最大值或右子节点的最小值，为了保持索引有效，必须执行一些操作，但是它的速度足够快。

我使用这种技术为更高级的东西，建立一些大词字典与内部基数试验，我能够除以7-8内存消耗(你可以看到这里的一个例子: https://gist.github.com/fbparis/b3ddd5673b603b42c880974b23db7cda)

小开

基于 Node的连接节点类是一种标准方法，它们很难可视化。

动机来自 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],
}

细节

  • 每个键值对都是指向其子对的 唯一节点。
  • 列表(或元组)包含有序的左/右子对。
  • 使用 有命令插入的字体时，假设第一个条目是根。
  • 常见的方法可以是变异或遍历 dict 的函数(参见 find_all_paths())。

基于树的函数通常包括以下常见操作:

  • 遍历 : 按照给定的顺序(通常从左到右)生成每个节点
    • 广度优先搜索: 横向水平
    • 深度优先搜索(dFS) : 首先遍历分支(预先/在-/后顺序)
  • Insert : 根据子节点的数量将节点添加到树中
  • Remove : 根据子节点的数量删除节点
  • Update : 将缺失的节点从一棵树合并到另一棵树
  • Access : 生成一个遍历节点的值

尝试实现所有这些操作。 这里我们演示这些函数的 一-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']

这是一个应用于节点和子节点结点的 广度优先搜索(水平顺序)算法。

  1. 初始化一个 先进先出队列。我们使用一个 deque，但是一个 queue或者一个 list可以工作(后者是低效的)。
  2. 获取并加入根节点的队列(假设根是 dictPython 3.6 + 中的第一个条目)。
  3. 迭代地取消一个节点的队列，对其子节点进行队列并生成该节点的值。

也可以参考这个关于树的 教程的深度文章。

洞察力

一般来说，遍历的好处是，我们可以通过简单地用 栈(也称为 LIFO Queue)替换队列来轻松地改变后一种对 深度优先搜索的迭代方法。这仅仅意味着我们从排队的同一侧出发。DFS 允许我们搜索每个分支。

怎么做到的？因为我们使用的是 deque，所以我们可以通过将 node = q.popleft()更改为 node = q.pop()(右)来模拟栈。结果是右偏的，预定的家庭服务部: ['a', 'c', 'f', 'b', 'e', 'd']。

小开

我想展示@apadana 方法的一个变体，当有相当数量的节点时，它更有用:

'''
Suppose we have the following tree
10
/    \
11      9
/  \     / \
7   12  15   8
'''
# Step 1 - Create nodes - Use a list instead of defining each node separately
nlist = [10,11,7,9,15,8,12]; n = []
for i in range(len(nlist)): n.append(Node(nlist[i]))


# Step 2 - Set each node position
n[0].left  = n[1]
n[1].left = n[2]
n[0].right = n[3]
n[3].left = n[4]
n[3].right = n[5]
n[1].right = n[6]
小开

您可以使用面向对象的方式(或者构建类)在 Python 中创建自己的 BinaryTree 数据结构。 您可以在这里分离两个类: Node 和 BinaryTree。 “ Node”类负责为 BinaryTree 创建单独的节点对象，而“ BinaryTree”类是在“ Node”类之上实现二叉树所需要的。

这是我当时研究它时编写的代码:

class TreeNode:


def __init__(self, data=None):
self.data = data
self.left = None
self.right = None


def __str__(self):
return f'Node(Data={self.data}, Left={self.left}, Right={self.right})'


def __repr__(self):
return self.__str__()


def get_data(self):
return self.data


def set_data(self, data):
self.data = data


def get_left(self):
return self.left


def set_left(self, left):
self.left = left


def get_right(self):
return self.right


def set_right(self, right):
self.right = right


class BinaryTree:


def __init__(self, root=None):
self.root = TreeNode(root)


def __str__(self):
return f'BinaryTree({self.root})'


def __repr__(self):
return f'BinaryTree({self.root})'


def insert(self, data):
# if empty tree
if self.root.get_data() is None:
return self.root.set_data(data)
new_node = TreeNode(data)
current = self.root
while True:
if data < current.get_data():
if current.get_left() is None:
return current.set_left(new_node)
current = current.get_left()
continue
elif data > current.get_data():
if current.get_right() is None:
return current.set_right(new_node)
current = current.get_right()
continue
return


# still needs other methods like the delete method, but you can
# try it out yourself
def delete(self, node):
pass


def main():
myTree = BinaryTree()
myTree.insert(5)
myTree.insert(3)
myTree.insert(4)
myTree.insert(2)
myTree.insert(8)
myTree.insert(9)
myTree.insert(6)
print(myTree)


if __name__ == '__main__':
main()
小开

左子元素按照节点顺序排列在右子元素之前。

每个节点都被认为是左右树的根节点。编写一个类来轻松创建节点:

class _Node:
#slots are class level member,efficiently allocates memory for instance variables
__slots__='_element','_left','_right'
def __init__(self,element,left=None,right=None):
# left is not a node, left is the left sub Binary Tree
# right is the right sub Binary Tree
self._element=element
self._left=left
self._right=right

这里我们写二进制类:

class BinaryTree:
def __init__(self):
self._root=None
def make_tree(self,e,left,right): # left=left-subtree, right=right-subtree
# we start the tree from leaf nodes.. since it has no left and right subtrees, left and right null
# x.maketree(B,null,null)=[Q,B,Q] this is node x
# y.maketree(C,null,null)=[Q,C,Q]
# z.maketree(A,x,y)  "z" is the parent of "x" and "y"
# each node is the root of the binary tree
# each subtree is also considered to be Binary Tree
self._root=_Node(e,left._root,right._root)
# inorder similar to infix:A+B. visit left first, then root, then right
def inorder(self,troot):
if troot:
self.inorder(troot._left)
print(troot._element,end=' ')
self.inorder(troot._right)
# preorder similar to prefix. +AB, visit root first,then left, then right
def preorder(self,troot):
if troot:
print(troot._element,end=' ')
self.preorder(troot._left)
self.preorder(troot._right)
# postorder similar to postfix. left first, then right, then root
def postorder(self,troot):
if troot:
self.postorder(troot._left)
self.postorder(troot._right)
print(troot._element,end=' ')
# count the number of nodes recursively
# recursive calls break the problem into smallest sub problems
# we are recursively asking each node, how many children does each node have
# if a node does not have any child, we count that node, that is why add +1. x+y+1
def count(self,troot):
if troot:
x=self.count(troot._left)
print("x",x)
y=self.count(troot._right)
print("y",y)
print("x+y",x+y)
# we add +1 because we have to count the root
return x+y+1
return 0
def height(self,troot):
if troot:
x=self.height(troot._left)
y=self.height(troot._right)
if x>y:
return x+1
else:
return y+1
return 0

现在创建二叉树:

创建6个子二叉树

x=BinaryTree()
y=BinaryTree()
z=BinaryTree()
r=BinaryTree()
s=BinaryTree()
t=BinaryTree()
a=BinaryTree() # null binary tree

首先使叶节点，40和60

# if a tree has only root node, it is still binary tree
x.make_tree(40,a,a)
y.make_tree(60,a,a)

创建内部节点

z.make_tree(20,x,a) #left internal
r.make_tree(50,a,y) #right internal
s.make_tree(30,r,a)
t.make_tree(10,z,s)
小开

虽然我喜欢“ djra”的答案，但我并不喜欢递归，因为它通常比简单的循环慢，而且不易读。

二叉树 没有递归大致是:

  • 增加新节点的速度要快72%
  • 找到节点的时候快了27%

我的实施方案:

class Node:
def __init__(self, val) -> None:
self.val = val
self.left = None
self.right = None




class Tree:
def __init__(self) -> None:
self.root = None


def add(self, val):
if self.root is None:
self.root = Node(val)
return


current_node = self.root
while current_node is not None:
# too many nested conditionals, you could move it into a separated
# method for readibility purposes
if val < current_node.val:
if current_node.left is None:
current_node.left = Node(val)
break
else:
current_node = current_node.left
else:
if current_node.right is None:
current_node.right = Node(val)
break
else:
current_node = current_node.right


def find(self, val):
current_node = self.root
while current_node is not None:
if val < current_node.val:
current_node = current_node.left
elif val > current_node.val:
current_node = current_node.right
else:
return current_node


raise ValueError("Node does not exist")


def add_with_recursion(self, val):
if self.root is None:
self.root = Node(val)
else:
self._add_with_recursion(val, self.root)


def _add_with_recursion(self, val, node):
if val < node.val:
if node.left is not None:
self._add_with_recursion(val, node.left)
else:
node.left = Node(val)
else:
if node.right is not None:
self._add_with_recursion(val, node.right)
else:
node.right = Node(val)


def find_with_recursion(self, val):
if self.root is not None:
return self._find_with_recursion(val, self.root)
else:
return None


def _find_with_recursion(self, val, node):
if val == node.val:
return node
elif val < node.val and node.left is not None:
return self._find_with_recursion(val, node.left)
elif val > node.val and node.right is not None:
return self._find_with_recursion(val, node.right)

速度:

我只是把时间的结果乘以500因为500是我在不超过最大递归深度的情况下所能达到的最大时间

import timeit


values = [10, 7, 14, 8, 12, 9, 2, 1, 5, 3, 14, 0.5]




def add_with_rec(tree_with_recursion, values):
for i in values:
tree_with_recursion.add_with_recursion(i)
return tree_with_recursion




def add(tree, values):
for i in values:
tree.add(i)
return tree




# Measuring with recursion
tree_with_recursion = Tree()
print("\nAdding with recursion:")
print(
100000
* timeit.timeit(lambda: add_with_rec(tree_with_recursion, values), number=500)
)


print("\nFinding with recursion:")
print(
100000
* timeit.timeit(lambda: tree_with_recursion.find_with_recursion(0.5), number=500)
)




# Measuring without recursion
tree = Tree()
print("\nAdding without recursion:")
print(100000 * timeit.timeit(lambda: add(tree, values), number=500))


print("\nFinding wihtout recursion:")
print(100000 * timeit.timeit(lambda: tree.find(0.5), number=500))
产出:
Adding with recursion:
13253.60000191722


Finding with recursion:
37.02999965753406


Adding without recursion:
3672.5399986607954


Finding wihtout recursion:
27.779999072663486

提交答案