이진 트리 알고리즘 예제의 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 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 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 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번째 수준의 노드 수 계산 이진 트리

'''
计算二叉树结点个数，递归方式
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

'''
计算二叉树深度，递归方式
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  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

'''
计算二叉树叶子节点个数，递归方式
关键点是叶子节点的判断标准，左右孩子皆为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

위 내용은 이진 트리 알고리즘 예제의 Python 구현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!