반응형
이진 트리를 구현하는 방법은 무엇입니까?
파이썬에서 이진 트리를 구현하는 데 사용할 수 있는 최고의 데이터 구조는 무엇입니까?
이진 검색 트리의 간단한 재귀 구현입니다.
#!/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()
[인터뷰에 필요한 것] 노드 클래스는 이진 트리를 나타내기에 충분한 데이터 구조입니다.
(다른 답변은 대부분 정확하지만 이진 트리에는 오브젝트 클래스를 확장할 필요가 없고, 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을 자식으로 갖는 트리의 루트입니다.
# 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)
자세한 내용은 여기를 참조하십시오.-이것은 이진 트리의 매우 간단한 구현입니다.
이 튜토리얼은 중간중간에 질문이 있는 좋은 튜토리얼입니다.
여기서 대부분의 답변이 이진 검색 트리를 구현하고 있다는 것을 알 수 없습니다.이진 검색 트리!= 이진 트리.
이진 검색 트리에는 매우 특정한 속성이 있습니다. 노드 X의 경우 X의 키는 왼쪽 자식의 키보다 크고 오른쪽 자식의 키보다 작습니다.
이진 트리에는 이러한 제한이 없습니다.이진 트리는 단순히 '키' 요소와 '왼쪽' 및 '오른쪽'과 같은 두 자식을 가진 데이터 구조입니다.
트리는 각 노드가 임의의 수의 자식을 가질 수 있는 이진 트리의 더 일반적인 경우입니다.일반적으로 각 노드에는 list/array 유형의 '하위' 요소가 있습니다.
이제 OP의 질문에 답하기 위해, 저는 파이썬에서 이진 트리의 완전한 구현을 포함하고 있습니다.각 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
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)
목록을 사용하여 이진 트리를 구현하는 매우 빠른 더러운 방법.가장 효율적이지도 않고 0 값을 너무 잘 처리하지도 않습니다.하지만 (적어도 나에게는) 매우 투명합니다.
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'])
A Node연결된 노드의 기본 클래스는 표준 접근 방식입니다.이것들은 시각화하기 어려울 수 있습니다.
Python Patterns - Implementing Graphs에 대한 에세이에서 영감을 받아 간단한 사전을 생각해 보십시오.
정해진
이진 트리
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],
}
세부 사항
- 각 키-값 쌍은 자식을 가리키는 고유한 노드입니다.
- 목록(또는 튜플)에는 순서가 지정된 왼쪽/오른쪽 자식 쌍이 들어 있습니다.
- 딕트가 삽입 순서를 지정한 경우 첫 번째 항목이 루트라고 가정합니다.
- 일반적인 방법은 딕트를 변환하거나 통과하는 함수일 수 있습니다( 참조).
트리 기반 함수에는 다음과 같은 일반적인 작업이 포함됩니다.
- travers: 주어진 순서로 각 노드를 산출합니다(일반적으로 왼쪽에서 오른쪽으로).
- 폭 우선 검색(BFS): 횡단 수준
- 깊이 우선 검색(DFS): 분기를 먼저 통과합니다(사전/내/사후 순서).
- insert: 하위 항목 수에 따라 트리에 노드 추가
- 제거: 하위 항목 수에 따라 노드 제거
- 업데이트: 누락된 노드를 한 트리에서 다른 트리로 병합
- visit: 횡단 노드의 값을 산출합니다.
이 모든 작업을 구현해 보십시오.여기에서는 다음 기능 중 하나인 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 대기열을 초기화합니다.우리는 , 그러나 , 또는 를 사용합니다.
list(후자는 비효율적입니다.) - 루트 노드를 가져와 큐에 넣습니다(루트가 딕트의 첫 번째 항목인 Python 3.6+라고 가정합니다).
- 반복적으로 노드의 대기열을 해제하고 자식 노드를 대기열에 넣고 노드 값을 산출합니다.
트리에 대한 자세한 내용은 이 튜토리얼을 참조하십시오.
통찰력
일반적으로 트래버설의 장점은 단순히 큐를 스택(LIFO 큐)으로 대체함으로써 깊이 우선 검색(DFS)에 대한 후자의 반복적인 접근 방식을 쉽게 변경할 수 있다는 것입니다.이것은 단순히 우리가 대기하고 있는 것과 같은 쪽에서 대기열을 해제한다는 것을 의미합니다.DFS를 사용하면 각 지점을 검색할 수 있습니다.
가 어게요를 ? 저희가 이렇게.deque우리는 변화를 통해 스택을 에뮬레이트할 수 있습니다.node = q.popleft()node = q.pop()(오른쪽).그 결과, 우선순위가 높은 사전 주문형 DFS가 제공됩니다.['a', 'c', 'f', 'b', 'e', 'd'].
당신은 두 개의 수업을 받을 필요가 없습니다.
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()
좀 더 "피토닉"
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=' ')
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
이 구현은 트리 구조를 파괴하지 않고 삽입, 찾기 및 삭제 작업을 지원합니다.이것은 분산된 나무가 아닙니다.
# 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))
바이너리 검색 트리의 좋은 구현은 다음과 같습니다.
'''
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()
나는 이미 많은 좋은 솔루션이 게시되었다는 것을 알고 있지만 보통 이진 트리에 대해 다른 접근 방식을 사용합니다. 일부 노드 클래스로 이동하여 직접 구현하는 것이 더 읽기 쉽지만 노드가 많을 때는 메모리와 관련하여 매우 탐욕스러울 수 있으므로 복잡성의 한 레이어를 추가하고 파이썬 목록에 노드를 저장하는 것을 제안합니다.목록만 사용하여 트리 동작을 시뮬레이션합니다.
필요할 때 트리의 노드를 최종적으로 나타내도록 노드 클래스를 정의할 수 있지만, 노드 클래스를 단순한 형태(값, 왼쪽, 오른쪽)로 유지하면 메모리 사용량이 절반 이하가 됩니다!
다음은 이진 검색 트리 클래스가 노드를 배열에 저장하는 간단한 예입니다.추가, 제거, 찾기와 같은 기본 기능을 제공합니다.
"""
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 구조를 유지하기 위해 제거된 노드는 왼쪽 자식 노드의 최대값 또는 오른쪽 자식 노드의 최소값으로 대체되며 인덱스를 유효하게 유지하기 위해 일부 작업을 수행해야 하지만 충분히 빠릅니다.
저는 이 기술을 사용하여 내부 radix trie를 포함한 몇 가지 큰 단어 사전을 구축했고 메모리 소비를 7-8로 나눌 수 있었습니다(여기 예를 볼 수 있습니다: https://gist.github.com/fbparis/b3ddd5673b603b42c880974b23db7cda) ).
@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 데이터 구조를 OOP 방식(또는 클래스 구축)으로 만들 수 있습니다.여기서 노드 및 이진 트리라는 두 클래스를 구분할 수 있습니다."Node" 클래스는 이진 트리에 대한 개별 노드 개체를 생성하는 역할을 하며, "Binary Tree" 클래스는 "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)
속도:
p.s.: 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
파이썬의 이진 트리
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(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의 이진 트리에서 가져온 코드
언급URL : https://stackoverflow.com/questions/2598437/how-to-implement-a-binary-tree
반응형
'programing' 카테고리의 다른 글
| Oracle 번호 및 varchar 조인 (0) | 2023.07.21 |
|---|---|
| oracle "order by" 부품에서 SQL 주입 방지 (0) | 2023.07.21 |
| 스파크 데이터 프레임 열에서 최대값을 가져오는 가장 좋은 방법 (0) | 2023.07.21 |
| 테스트 사례에 사용되는 "setUp" 및 "tearDown" Python 방법 설명 (0) | 2023.07.21 |
| 스프링 REST 및 PATCH 방법 (0) | 2023.07.21 |