Python은 이진 트리를 구현합니다
Python은 이진 트리 노드 클래스를 정의하여 객체 지향 프로그래밍을 사용하여 이진 트리를 구현할 수 있습니다. 각 노드에는 데이터 요소, 왼쪽 및 오른쪽 하위 노드 포인터 및 노드 삽입, 노드 찾기, 노드 삭제 등과 같은 일부 작업 방법이 포함되어 있습니다.
다음은 간단한 이진 트리 구현 예입니다.
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def insert(self, data):
if self.data:
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
def find(self, data):
if data < self.data:
if self.left is None:
return str(data) + " Not Found"
return self.left.find(data)
elif data > self.data:
if self.right is None:
return str(data) + " Not Found"
return self.right.find(data)
else:
return str(self.data) + " is found"
def inorder_traversal(self, root):
res = []
if root:
res = self.inorder_traversal(root.left)
res.append(root.data)
res = res + self.inorder_traversal(root.right)
return res로그인 후 복사
위 코드에서 Node 클래스는 데이터 요소 데이터와 왼쪽 및 오른쪽 하위 노드 포인터를 포함하는 노드를 정의합니다. insert 메소드는 이진 트리에 노드를 삽입하는 데 사용되고, find 메소드는 이진 트리에 특정 노드가 존재하는지 찾는 데 사용되고, inorder_traversal 메소드는 이진 트리의 순차 순회를 수행하는 데 사용됩니다.
이 Node 클래스를 사용하여 이진 트리를 만드는 방법은 다음과 같습니다.
root = Node(50)
root.insert(30)
root.insert(20)
root.insert(40)
root.insert(70)
root.insert(60)
root.insert(80)
# 查找节点
print(root.find(70)) # Output: 70 is found
print(root.find(90)) # Output: 90 Not Found
# 中序遍历
print(root.inorder_traversal(root)) # Output: [20, 30, 40, 50, 60, 70, 80]
로그인 후 복사
위 코드에서 루트 노드 루트가 먼저 생성된 다음 삽입 메서드를 사용하여 노드를 트리에 삽입하고 마지막으로 find 메서드를 사용합니다. 노드를 찾는 데 사용되고 inorder_traversal 메소드가 사용됩니다. 이진 트리의 중위 순회를 수행합니다.
삽입, 검색 및 순회 방법 외에도 이진 트리에는 노드 삭제, 이진 검색 트리인지 확인, 트리 깊이 계산 등과 같은 다른 작업 방법도 있습니다. 다음은 좀 더 완전한 이진 트리 샘플 코드입니다.
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def insert(self, data):
if self.data:
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
def find(self, data):
if data < self.data:
if self.left is None:
return None
return self.left.find(data)
elif data > self.data:
if self.right is None:
return None
return self.right.find(data)
else:
return self
def delete(self, data):
if self is None:
return self
if data < self.data:
self.left = self.left.delete(data)
elif data > self.data:
self.right = self.right.delete(data)
else:
if self.left is None:
temp = self.right
self = None
return temp
elif self.right is None:
temp = self.left
self = None
return temp
temp = self.right.minimum()
self.data = temp.data
self.right = self.right.delete(temp.data)
return self
def minimum(self):
if self.left is None:
return self
return self.left.minimum()
def is_bst(self):
if self.left:
if self.left.data > self.data or not self.left.is_bst():
return False
if self.right:
if self.right.data < self.data or not self.right.is_bst():
return False
return True
def height(self, node):
if node is None:
return 0
left_height = self.height(node.left)
right_height = self.height(node.right)
return max(left_height, right_height) + 1
def inorder_traversal(self, root):
res = []
if root:
res = self.inorder_traversal(root.left)
res.append(root.data)
res = res + self.inorder_traversal(root.right)
return res로그인 후 복사
이 예에서는 지정된 노드를 삭제하는 삭제 메서드를 추가했습니다. 현재 트리는 트리의 깊이를 계산하는 이진 포크 검색 트리입니다.
다음 코드를 사용하여 새 방법을 테스트할 수 있습니다.
# 创建二叉树
root = Node(50)
root.insert(30)
root.insert(20)
root.insert(40)
root.insert(70)
root.insert(60)
root.insert(80)
# 删除节点
print("Deleting node 20:")
root.delete(20)
print(root.inorder_traversal(root))
# 判断是否为二叉搜索树
print("Is it a BST?:", root.is_bst())
# 计算树的深度
print("Tree height:", root.height(root))로그인 후 복사
이러한 방식으로 비교적 완전한 이진 트리 구현을 완료했으며 Python에서 객체 지향 프로그래밍 아이디어를 사용하여 데이터 구조를 구현하는 방법도 시연했습니다.
마지막으로 전체 이진 트리 클래스 구현 코드가 첨부됩니다.
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def insert(self, data):
if self.data:
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
def find(self, data):
if data < self.data:
if self.left is None:
return None
return self.left.find(data)
elif data > self.data:
if self.right is None:
return None
return self.right.find(data)
else:
return self
def delete(self, data):
if self is None:
return self
if data < self.data:
self.left = self.left.delete(data)
elif data > self.data:
self.right = self.right.delete(data)
else:
if self.left is None:
temp = self.right
self = None
return temp
elif self.right is None:
temp = self.left
self = None
return temp
temp = self.right.minimum()
self.data = temp.data
self.right = self.right.delete(temp.data)
return self
def minimum(self):
if self.left is None:
return self
return self.left.minimum()
def is_bst(self):
if self.left:
if self.left.data > self.data or not self.left.is_bst():
return False
if self.right:
if self.right.data < self.data or not self.right.is_bst():
return False
return True
def height(self, node):
if node is None:
return 0
left_height = self.height(node.left)
right_height = self.height(node.right)
return max(left_height, right_height) + 1
def inorder_traversal(self, root):
res = []
if root:
res = self.inorder_traversal(root.left)
res.append(root.data)
res = res + self.inorder_traversal(root.right)
return res
if __name__ == '__main__':
# 创建二叉树
root = Node(50)
root.insert(30)
root.insert(20)
root.insert(40)
root.insert(70)
root.insert(60)
root.insert(80)
# 删除节点
print("Deleting node 20:")
root.delete(20)
print(root.inorder_traversal(root))
# 判断是否为二叉搜索树
print("Is it a BST?:", root.is_bst())
# 计算树的深度
print("Tree height:", root.height(root))로그인 후 복사
코드를 실행한 후 다음 출력을 얻을 수 있습니다.
노드 20 삭제:
[30, 40, 50, 60, 70, 80]
BST인가요?: True
트리 높이: 3
이 예제에는 삽입, 검색, 삭제, 순회, 이진 검색 트리인지 확인하고 트리 깊이 계산이 포함됩니다.
위 내용은 Python에서 이진 트리를 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
