Python 详解二叉树

￡神魔★判官ぃ 2023-06-27 12:57 6阅读 0赞

### Python 二叉树 ###

*  二叉树概念
 *  二叉树遍历
 *   *   *  先｜前序遍历
         *  中序列遍历
         *  后序遍历
         *  层次遍历
 *  构造二叉树排序 (堆排序)
 *  二叉树排序

【***关于二叉树的一些理解***】

--------------------

***(声明：本教程仅供本人学习使用,如有人使用该技术触犯法律与本人无关)  
(如果有错误，还希望指出。共同进步)***

--------------------

# 二叉树概念 #

计算机科学中，**二叉树**是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

一棵深度为k，且有2^k-1个结点的二叉树，称为**满二叉树**。这种树的特点是每一层上的结点数都是最大结点数。而在一棵二叉树中，除最后一层外，若其余层都是满的，并且或者最后一层是满的，或者是在右边缺少连续若干结点，则此二叉树为完全二叉树。具有n个结点的完全二叉树的深度为（**向下取整等同于int()**）floor(log2n)+1。深度为k的完全二叉树，至少有2k-1个叶子结点，至多有2k-1个结点。

--------------------

# 二叉树遍历 #

【一般情况下左节点优于右节点】

*  深度遍历：
    
     *  先序遍历
     *  中序遍历
     *  后序遍历
 *  广度遍历
    
     *  层次遍历

--------------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzYzMzc5Nw_size_16_color_FFFFFF_t_70]

#!/usr/bin/python
    # -*- coding:utf8 -*-
    
    
    # 定义二叉树
    class TreeNode:
        def __init__(self, p):
            self.val = p
            self.left = None
            self.right = None
    
        def insert_left(self, new_node):
            if self.left is None:
                self.left = TreeNode(new_node)
            else:
                print('The leftChild is not None.You can not insert')
            return self.left
    
        def insert_right(self, new_node):
            if self.right is None:
                self.right = TreeNode(new_node)
            else:
                print('The rightChild is not None.You can not insert')
            return self.right
    
    
    if __name__ == '__main__':
    	# 插入如图所示的数据
        A = TreeNode('A')
        A.insert_left('B')
        A.insert_right('C')
        A.left.insert_left('D')
        A.left.insert_right('E')
        A.right.insert_right('F')

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzYzMzc5Nw_size_16_color_FFFFFF_t_70 1]

--------------------

### 先｜前序遍历 ###

*  【**父节点在前**】
 *  **遍历顺序**：父节点 - 左节点 - 右节点

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzYzMzc5Nw_size_16_color_FFFFFF_t_70 2]

# 递归实现
    def before_traverse(root):
        if not root:
            return
        # 先序遍历,父节点在前
        print(root.val)
        before_traverse(root.left)
        before_traverse(root.right)
    
    
    # A - B - D - E - C - F
    
    
    # 迭代实现
    def before_traverse(root):
        stack = [root]
        result = []
        while stack:
            s = stack.pop()
            if s:
                result.append(s.val)
                stack.append(s.right)
                stack.append(s.left)
        return ' - '.join(result)

--------------------

### 中序列遍历 ###

*  【**父节点在中**】
 *  **遍历顺序**：左节点 - 父节点 - 右节点

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzYzMzc5Nw_size_16_color_FFFFFF_t_70 3]

# 递归实现
    def between_traverse(root):
        if not root:
            return
        between_traverse(root.left)
        # 中序遍历,父节点在中
        print(root.val)
        between_traverse(root.right)
    
    
    # D - B - E - A - C - F
    
    
    # 迭代实现
    def between_traverse(root):
        stack = []
        result = []
        while stack or root:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            result.append(root.val)
            root = root.right
        return ' - '.join(result)

--------------------

### 后序遍历 ###

*  【**父节点在后**】
 *  **遍历顺序**：左节点 - 右节点 - 父节点  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzYzMzc5Nw_size_16_color_FFFFFF_t_70 4]

# 递归实现
    def after_traverse(root):
        if not root:
            return
        after_traverse(root.left)
        after_traverse(root.right)
        # 后序遍历,父节点在后
        print(root.val)
    
    
    # D - E - B - F - C - A
    
    
    # 迭代实现
    def after_traverse(root):
        stack = []
        result = []
        while stack or root:
        	# 下行循环，直到找到第一个叶子节点
            while root:  
                stack.append(root)
                # 能左就左，不能左就右
                if root.left:  
                    root = root.left
                else:
                    root = root.right
            s = stack.pop()
            result.append(s.val)
            # 如果当前节点是上一节点的左子节点，则遍历右子节点
            if stack and s == stack[-1].left:
                root = stack[-1].right
            else:
                root = None
        return ' - '.join(result)

--------------------

### 层次遍历 ###

# 迭代实现
    def bfs(root):
        queue = [root]
        result = []
        while queue:
            n = len(queue)
            for i in range(n):
                q = queue.pop(0)
                if q:
                    result.append(q.val)
                    queue.append(q.left if q.left else None)
                    queue.append(q.right if q.right else None)
        return ' - '.join(result)
    
    
    # A - B - C - D - E - F

--------------------

# 构造二叉树排序 (堆排序) #

#!/usr/bin/python
    # -*- coding:utf-8 -*-
    
    
    def heapify(arr: list, n: int, i: int):
        # 父节点下标
        p = i
        # 左节点下标
        l = 2 * i + 1
        # 右节点下标
        r = 2 * i + 2
    
        if l < n and arr[i] < arr[l]:
            p = l
    
        if r < n and arr[p] < arr[r]:
            p = r
    
        if p != i:
            arr[i], arr[p] = arr[p], arr[i]
            heapify(arr, n, p)
    
    
    def heapSort(arr: list) -> list:
        n = len(arr)
        # 构建大顶堆,父节点元素大于左右节点元素
        for i in range(n, -1, -1):
            heapify(arr, n, i)
    
        # 交换元素
        for j in range(n - 1, 0, -1):
            # 从后向前依次遍历,最后节点(最小值)和祖先节点(最大值)交换
            arr[j], arr[0] = arr[0], arr[j]
            # 保证这一树叉支为大顶堆
            heapify(arr, j, 0)
    
        return arr
    
    
    if __name__ == '__main__':
        arr = []
        print(heapSort(arr))

--------------------

# 二叉树排序 #

#!/usr/bin/python
    # -*- coding:utf-8 -*-
    
    
    # 中序遍历,左中右,正序排列
    def between_traverse(root):
        if not root:
            return
        between_traverse(root.left)
        print(root.val)
        between_traverse(root.right)
    
    
    # 中序遍历,右中左,倒序排列
    def rbetween_traverse(root):
        if not root:
            return
        rbetween_traverse(root.right)
        print(root.val)
        rbetween_traverse(root.left)
    
    
    # 左节点小于父节点,父节点小于右节点
    def insert(node, val):
        if val > node.val:
            if node.right:
                insert(node.right, val)
            else:
                node.insert_right(val)
        else:
            if node.left:
                insert(node.left, val)
            else:
                node.insert_left(val)
    
    
    if __name__ == '__main__':
        l = [3, 7, 5, 20, 43, 2, 15, 30]
        Root = TreeNode(l[0])
        node = Root
        # 构造排序二叉树
        for i in range(1, len(l)):
            insert(Root, l[i])
        between_traverse(Root)
        print('========')
        rbetween_traverse(Root)
    
    # result
    # 2
    # 3
    # 5
    # 7
    # 15
    # 20
    # 30
    # 43
    # ========
    # 43
    # 30
    # 20
    # 15
    # 7
    # 5
    # 3
    # 2

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzYzMzc5Nw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200107104853180.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzYzMzc5Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzYzMzc5Nw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200107111923550.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzYzMzc5Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzYzMzc5Nw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200107105041936.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzYzMzc5Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzYzMzc5Nw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200107105108201.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzYzMzc5Nw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzYzMzc5Nw_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200107105119962.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzYzMzc5Nw==,size_16,color_FFFFFF,t_70