Python实现二叉树相关算法

绝地灬酷狼 2022-03-07 14:30 190阅读 0赞

### 节点定义 ###

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

#### 非递归方式 ####

'''
    先序遍历，非递归方式
    '''
    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

### 计算二叉树结点个数 ###

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

### 计算二叉树第k层节点个数 ###

'''
    计算二叉树第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)

### 判断两个二叉树是不是相同 ###

'''
    判断两个二叉树是不是相同，递归方式
    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

### 判断是否为二分查找树BST ###

'''
    判断是否为二分查找树BST，递归方式
    二分查找树的定义搞清楚，二分查找树的中序遍历结果为递增序列
    '''
    def is_bst_tree(root):
        if root and not isinstance(root, Node):
            return None
    
        def is_asc(order):
            for i in range(len(order)-1):
                if order[i] > order[i+1]:
                    return False
            return True
    
        return is_asc(middle_order_bot_recursion(root))

### 测试方法 ###

if __name__ == "__main__":
        tree = Tree(1)
        tree1 = Tree(1)
        node6 = Node(None, None, 7)
        node5 = Node(None, None, 6)
        node4 = Node(None, None, 5)
        node3 = Node(None, None, 4)
        node2 = Node(node5, node6, 3)
        node1 = Node(node3, node4, 2)
        tree.root.left_child = node1
        tree.root.right_child = node2
        tree1.root.left_child = node2
        tree1.root.right_child = node2
        print(is_bst_tree(tree.root))