Python에서 이진 트리를 구현하는 방법

WBOY
풀어 주다: 2023-05-03 09:16:06
앞으로
1319명이 탐색했습니다.

Python은 이진 트리를 구현합니다

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 중국어 웹사이트의 기타 관련 기사를 참조하세요!

관련 라벨:
원천:yisu.com
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
최신 이슈
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿
회사 소개 부인 성명 Sitemap
PHP 중국어 웹사이트:공공복지 온라인 PHP 교육,PHP 학습자의 빠른 성장을 도와주세요!