이진 트리 알고리즘 예제의 Python 구현
이 기사는 Python에서 이진 트리를 구현하는 알고리즘의 몇 가지 예를 제공합니다. 이는 특정 참조 값을 가지고 있으므로 도움이 될 수 있습니다. 노드 정의 Way
class Node(object): def __init__(self, left_child, right_child, value): self._left_child = left_child self._right_child = right_child self._value = value @property def left_child(self): return self._left_child @property def right_child(self): return self._right_child @left_child.setter def left_child(self, value): self._left_child = value @right_child.setter def right_child(self, value): self._right_child = value @property def value(self): return self._value @value.setter def value(self, value): self._value = value
비재귀적 방식class Tree(object):
def __init__(self, value):
self._root = Node(None, None, value=value)
@property
def root(self):
return self._root
재귀적 방식
''' 先序遍历，递归方式 ''' def preoder(root): if not isinstance(root, Node): return None preorder_res = [] if root: preorder_res.append(root.value) preorder_res += preoder(root.left_child) preorder_res += preoder(root.right_child) return preorder_res
Non- 재귀적 방식#🎜🎜 #'''
先序遍历，非递归方式
'''
def pre_order_not_recursion(root):
if not isinstance(root, Node):
return None
stack = [root]
result = []
while stack:
node = stack.pop(-1)
if node:
result.append(node.value)
stack.append(node.right_child)
stack.append(node.left_child)
return result
로그인 후 복사
후순 순회재귀적 방식''' 先序遍历，非递归方式 ''' def pre_order_not_recursion(root): if not isinstance(root, Node): return None stack = [root] result = [] while stack: node = stack.pop(-1) if node: result.append(node.value) stack.append(node.right_child) stack.append(node.left_child) return result
'''
中序遍历，递归方式
'''
def middle_order(root):
if not isinstance(root, Node):
return None
middle_res = []
if root:
middle_res += middle_order(root.left_child)
middle_res.append(root.value)
middle_res += middle_order(root.right_child)
return middle_res
로그인 후 복사
비재귀적 방식''' 中序遍历，递归方式 ''' def middle_order(root): if not isinstance(root, Node): return None middle_res = [] if root: middle_res += middle_order(root.left_child) middle_res.append(root.value) middle_res += middle_order(root.right_child) return middle_res
'''
中序遍历，非递归方式
'''
def middle_order_bot_recursion(root):
if not isinstance(root, Node):
return None
result = []
stack = [root.right_child, root.value, root.left_child]
while stack:
temp = stack.pop(-1)
if temp:
if isinstance(temp, Node):
stack.append(temp.right_child)
stack.append(temp.value)
stack.append(temp.left_child)
else:
result.append(temp)
return result
로그인 후 복사
계층적 순회#🎜 🎜 #''' 中序遍历，非递归方式 ''' def middle_order_bot_recursion(root): if not isinstance(root, Node): return None result = [] stack = [root.right_child, root.value, root.left_child] while stack: temp = stack.pop(-1) if temp: if isinstance(temp, Node): stack.append(temp.right_child) stack.append(temp.value) stack.append(temp.left_child) else: result.append(temp) return result
''' 后序遍历，递归方式 ''' def post_order(root): if not isinstance(root, Node): return None post_res = [] if root: post_res += post_order(root.left_child) post_res += post_order(root.right_child) post_res.append(root.value) return post_res
'''
后序遍历，非递归方式
'''
def post_order_not_recursion(root):
if not isinstance(root, Node):
return None
stack = [root.value, root.right_child, root.left_child]
result = []
while stack:
temp_node = stack.pop(-1)
if temp_node:
if isinstance(temp_node, Node):
stack.append(temp_node.value)
stack.append(temp_node.right_child)
stack.append(temp_node.left_child)
else:
result.append(temp_node)
return result
로그인 후 복사
이진 트리의 깊이 계산''' 后序遍历，非递归方式 ''' def post_order_not_recursion(root): if not isinstance(root, Node): return None stack = [root.value, root.right_child, root.left_child] result = [] while stack: temp_node = stack.pop(-1) if temp_node: if isinstance(temp_node, Node): stack.append(temp_node.value) stack.append(temp_node.right_child) stack.append(temp_node.left_child) else: result.append(temp_node) return result
'''
分层遍历，使用队列实现
'''
def layer_order(root):
if not isinstance(root, Node):
return None
queue = [root.value, root.left_child, root.right_child]
result = []
while queue:
temp = queue.pop(0)
if temp:
if isinstance(temp, Node):
queue.append(temp.value)
queue.append(temp.left_child)
queue.append(temp.right_child)
else:
result.append(temp)
return result
로그인 후 복사
k번째 수준의 노드 수 계산 이진 트리''' 分层遍历，使用队列实现 ''' def layer_order(root): if not isinstance(root, Node): return None queue = [root.value, root.left_child, root.right_child] result = [] while queue: temp = queue.pop(0) if temp: if isinstance(temp, Node): queue.append(temp.value) queue.append(temp.left_child) queue.append(temp.right_child) else: result.append(temp) return result
'''
计算二叉树结点个数，递归方式
NodeCount(root) = NodeCount(root.left_child) + NodeCount(root.right_child)
'''
def node_count(root):
if root and not isinstance(root, Node):
return None
if root:
return node_count(root.left_child) + node_count(root.right_child) + 1
else:
return 0
'''
计算二叉树结点个数，非递归方式
借用分层遍历计算
'''
def node_count_not_recursion(root):
if root and not isinstance(root, Node):
return None
return len(layer_order(root))
로그인 후 복사
이진 트리의 리프 노드 계산 Number''' 计算二叉树结点个数，递归方式 NodeCount(root) = NodeCount(root.left_child) + NodeCount(root.right_child) ''' def node_count(root): if root and not isinstance(root, Node): return None if root: return node_count(root.left_child) + node_count(root.right_child) + 1 else: return 0 ''' 计算二叉树结点个数，非递归方式 借用分层遍历计算 ''' def node_count_not_recursion(root): if root and not isinstance(root, Node): return None return len(layer_order(root))
'''
计算二叉树深度，递归方式
tree_deep(root) = 1 + max(tree_deep(root.left_child), tree_deep(root.right_child))
'''
def tree_deep(root):
if root and not isinstance(root, Node):
return None
if root:
return 1 + max(tree_deep(root.left_child), tree_deep(root.right_child))
else:
return 0
'''
计算二叉树深度，非递归方法
同理参考分层遍历的思想
'''
def tree_deep_not_recursion(root):
if root and not isinstance(root, Node):
return None
result = 0
queue = [(root, 1)]
while queue:
temp_node, temp_layer = queue.pop(0)
if temp_node:
queue.append((temp_node.left_child, temp_layer+1))
queue.append((temp_node.right_child, temp_layer+1))
result = temp_layer + 1
return result-1
로그인 후 복사
두 이진 트리가 동일한지 여부 판단''' 计算二叉树深度，递归方式 tree_deep(root) = 1 + max(tree_deep(root.left_child), tree_deep(root.right_child)) ''' def tree_deep(root): if root and not isinstance(root, Node): return None if root: return 1 + max(tree_deep(root.left_child), tree_deep(root.right_child)) else: return 0 ''' 计算二叉树深度，非递归方法 同理参考分层遍历的思想 ''' def tree_deep_not_recursion(root): if root and not isinstance(root, Node): return None result = 0 queue = [(root, 1)] while queue: temp_node, temp_layer = queue.pop(0) if temp_node: queue.append((temp_node.left_child, temp_layer+1)) queue.append((temp_node.right_child, temp_layer+1)) result = temp_layer + 1 return result-1
'''
计算二叉树第k层节点个数，递归方式
kth_node_count(root, k) = kth_node_count(root.left_count, k-1) + kth_node_count(root.right_count, k-1)
'''
def kth_node_count(root, k):
if root and not isinstance(root, Node):
return None
if not root or k <= 0:
return 0
if k == 1:
return 1
return kth_node_count(root.left_child, k-1) + kth_node_count(root.right_child, k-1)
'''
计算二叉树第K层节点个数，非递归方式
'''
def kth_node_count_not_recursion(root, k):
if root and not isinstance(root, Node):
return None
if not root or k <= 0:
return 0
if k == 1:
return 1
queue = [(root, 1)]
result = 0
while queue:
temp_node, temp_layer = queue.pop(0)
if temp_node:
if temp_layer == k:
result += 1
elif temp_layer > k:
return result
else:
queue.append((temp_node.left_child, temp_layer+1))
queue.append((temp_node.right_child, temp_layer+1))
return result로그인 후 복사
여부 판단 이진 검색 트리입니다 BST'''
计算二叉树第k层节点个数，递归方式
kth_node_count(root, k) = kth_node_count(root.left_count, k-1) + kth_node_count(root.right_count, k-1)
'''
def kth_node_count(root, k):
if root and not isinstance(root, Node):
return None
if not root or k <= 0:
return 0
if k == 1:
return 1
return kth_node_count(root.left_child, k-1) + kth_node_count(root.right_child, k-1)
'''
计算二叉树第K层节点个数，非递归方式
'''
def kth_node_count_not_recursion(root, k):
if root and not isinstance(root, Node):
return None
if not root or k <= 0:
return 0
if k == 1:
return 1
queue = [(root, 1)]
result = 0
while queue:
temp_node, temp_layer = queue.pop(0)
if temp_node:
if temp_layer == k:
result += 1
elif temp_layer > k:
return result
else:
queue.append((temp_node.left_child, temp_layer+1))
queue.append((temp_node.right_child, temp_layer+1))
return result'''
计算二叉树叶子节点个数，递归方式
关键点是叶子节点的判断标准，左右孩子皆为None
'''
def leaf_count(root):
if root and not isinstance(root, Node):
return None
if not root:
return 0
if not root.left_child and not root.right_child:
return 1
return leaf_count(root.left_child) + leaf_count(root.right_child)
로그인 후 복사
테스트 방법''' 计算二叉树叶子节点个数，递归方式 关键点是叶子节点的判断标准，左右孩子皆为None ''' def leaf_count(root): if root and not isinstance(root, Node): return None if not root: return 0 if not root.left_child and not root.right_child: return 1 return leaf_count(root.left_child) + leaf_count(root.right_child)
'''
判断两个二叉树是不是相同，递归方式
isSame(root1, root2) = (root1.value == root2.value)
and isSame(root1.left, root2.left)
and isSame(root1.right, root2.right)
'''
def is_same_tree(root1, root2):
if not root1 and not root2:
return True
if root1 and root2:
return (root1.value == root2.value) and \
is_same_tree(root1.left_child, root2.left_child) and \
is_same_tree(root1.right_child, root2.right_child)
else:
return False
로그인 후 복사
''' 判断两个二叉树是不是相同，递归方式 isSame(root1, root2) = (root1.value == root2.value) and isSame(root1.left, root2.left) and isSame(root1.right, root2.right) ''' def is_same_tree(root1, root2): if not root1 and not root2: return True if root1 and root2: return (root1.value == root2.value) and \ is_same_tree(root1.left_child, root2.left_child) and \ is_same_tree(root1.right_child, root2.right_child) else: return False
위 내용은 이진 트리 알고리즘 예제의 Python 구현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
핫 AI 도구
Undresser.AI Undress
사실적인 누드 사진을 만들기 위한 AI 기반 앱
AI Clothes Remover
사진에서 옷을 제거하는 온라인 AI 도구입니다.
Undress AI Tool
무료로 이미지를 벗다
Clothoff.io
AI 옷 제거제
AI Hentai Generator
AI Hentai를 무료로 생성하십시오.
인기 기사
뜨거운 도구
메모장++7.3.1
사용하기 쉬운 무료 코드 편집기
SublimeText3 중국어 버전
중국어 버전, 사용하기 매우 쉽습니다.
스튜디오 13.0.1 보내기
강력한 PHP 통합 개발 환경
드림위버 CS6
시각적 웹 개발 도구
SublimeText3 Mac 버전
신 수준의 코드 편집 소프트웨어(SublimeText3)
뜨거운 주제
7514
15
1378
52
79
11
53
19
19
64
2 시간의 파이썬 계획 : 현실적인 접근
Apr 11, 2025 am 12:04 AM
2 시간 이내에 Python의 기본 프로그래밍 개념과 기술을 배울 수 있습니다. 1. 변수 및 데이터 유형을 배우기, 2. 마스터 제어 흐름 (조건부 명세서 및 루프), 3. 기능의 정의 및 사용을 이해하십시오. 4. 간단한 예제 및 코드 스 니펫을 통해 Python 프로그래밍을 신속하게 시작하십시오.
파이썬 : 기본 응용 프로그램 탐색
Apr 10, 2025 am 09:41 AM
Python은 웹 개발, 데이터 과학, 기계 학습, 자동화 및 스크립팅 분야에서 널리 사용됩니다. 1) 웹 개발에서 Django 및 Flask 프레임 워크는 개발 프로세스를 단순화합니다. 2) 데이터 과학 및 기계 학습 분야에서 Numpy, Pandas, Scikit-Learn 및 Tensorflow 라이브러리는 강력한 지원을 제공합니다. 3) 자동화 및 스크립팅 측면에서 Python은 자동화 된 테스트 및 시스템 관리와 같은 작업에 적합합니다.
MongoDB 데이터베이스 비밀번호를 보는 Navicat의 방법
Apr 08, 2025 pm 09:39 PM
해시 값으로 저장되기 때문에 MongoDB 비밀번호를 Navicat을 통해 직접 보는 것은 불가능합니다. 분실 된 비밀번호 검색 방법 : 1. 비밀번호 재설정; 2. 구성 파일 확인 (해시 값이 포함될 수 있음); 3. 코드를 점검하십시오 (암호 하드 코드 메일).
Amazon Athena와 함께 AWS Glue Crawler를 사용하는 방법
Apr 09, 2025 pm 03:09 PM
데이터 전문가는 다양한 소스에서 많은 양의 데이터를 처리해야합니다. 이것은 데이터 관리 및 분석에 어려움을 겪을 수 있습니다. 다행히도 AWS Glue와 Amazon Athena의 두 가지 AWS 서비스가 도움이 될 수 있습니다.
Redis 대기열을 읽는 방법
Apr 10, 2025 pm 10:12 PM
Redis의 대기열을 읽으려면 대기열 이름을 얻고 LPOP 명령을 사용하여 요소를 읽고 빈 큐를 처리해야합니다. 특정 단계는 다음과 같습니다. 대기열 이름 가져 오기 : "큐 :"와 같은 "대기열 : my-queue"의 접두사로 이름을 지정하십시오. LPOP 명령을 사용하십시오. 빈 대기열 처리 : 대기열이 비어 있으면 LPOP이 NIL을 반환하고 요소를 읽기 전에 대기열이 존재하는지 확인할 수 있습니다.
Redis의 서버 버전을 보는 방법
Apr 10, 2025 pm 01:27 PM
질문 : Redis 서버 버전을 보는 방법은 무엇입니까? 명령 줄 도구 Redis-Cli를 사용하여 연결된 서버의 버전을보십시오. 정보 서버 명령을 사용하여 서버의 내부 버전을보고 정보를 구문 분석하고 반환해야합니다. 클러스터 환경에서 각 노드의 버전 일관성을 확인하고 스크립트를 사용하여 자동으로 확인할 수 있습니다. 스크립트를 사용하여 Python 스크립트와 연결 및 인쇄 버전 정보와 같은보기 버전을 자동화하십시오.
Redis로 서버를 시작하는 방법
Apr 10, 2025 pm 08:12 PM
Redis 서버를 시작하는 단계에는 다음이 포함됩니다. 운영 체제에 따라 Redis 설치. Redis-Server (Linux/MacOS) 또는 Redis-Server.exe (Windows)를 통해 Redis 서비스를 시작하십시오. Redis-Cli Ping (Linux/MacOS) 또는 Redis-Cli.exe Ping (Windows) 명령을 사용하여 서비스 상태를 확인하십시오. Redis-Cli, Python 또는 Node.js와 같은 Redis 클라이언트를 사용하여 서버에 액세스하십시오.
Navicat의 비밀번호는 얼마나 안전합니까?
Apr 08, 2025 pm 09:24 PM
Navicat의 비밀번호 보안은 대칭 암호화, 암호 강도 및 보안 측정의 조합에 의존합니다. 특정 측정에는 다음이 포함됩니다. SSL 연결 사용 (데이터베이스 서버가 인증서를 지원하고 올바르게 구성하는 경우), 정기적으로 Navicat을 업데이트하고보다 안전한 방법 (예 : SSH 터널), 액세스 권한 제한 및 가장 중요한 것은 암호를 기록하지 않습니다.
