算法与Python

算法与Python 知识量:10 - 40 - 100

4.2 二叉树><

二叉树的类型- 4.2.1 -

二叉树有多种类型,以下是常见的几种:

  1. 满二叉树:在二叉树中,如果所有叶节点都位于最底层,且每个叶节点左右相邻,则称该二叉树为满二叉树。

  2. 完全二叉树:如果从二叉树的根节点到最底层叶节点的路径上,每个节点都有两个子节点,除了最底层的叶节点外,其他节点都有两个子节点,则称该二叉树为完全二叉树。

  3. 二叉搜索树:如果二叉树满足左子树上任意节点的值均小于根节点的值,右子树上任意节点的值均大于根节点的值,则称该二叉树为二叉搜索树。

  4. 平衡二叉树:平衡二叉树(AVL树)是一种自平衡的二叉搜索树,其中任意节点的两个子树的高度差不超过1。

  5. 红黑树:红黑树是一种自平衡的二叉搜索树,其中每个节点要么是红色,要么是黑色,且满足以下性质:(1)每个叶节点(NIL节点,空节点)都是黑色的。(2)如果一个节点是红色的,则它的两个子节点都是黑色的。(3)从任一节点到其每个叶节点的所有路径都包含相同数目的黑节点。

二叉树的相关术语- 4.2.2 -

二叉树的相关术语有很多,包括但不限于以下:

  • 根节点:在二叉树中,根节点是整个树的起始节点。

  • 左子节点和右子节点:在二叉树中,一个节点有两个子节点,分别称为左子节点和右子节点。

  • 子树:在二叉树中,一个节点的子节点集合称为子树。

  • 父节点:在二叉树中,一个节点的父节点是其直接上级的节点。

  • 兄弟节点:在二叉树中,具有相同父节点的节点称为兄弟节点。

  • 叶子节点:在二叉树中,没有子节点的节点称为叶子节点。

  • 空二叉树:在二叉树中,一个没有节点的二叉树称为空二叉树。

  • 高度:在二叉树中,高度是从根节点到最底层叶子节点的最长路径上的节点数。

  • 深度:在二叉树中,深度是从根节点到叶子节点的最长路径上的节点数。

二叉树的节点代码- 4.2.3 -

以下是一个简单的Python代码,用于定义二叉树的节点:

class TreeNode:  
    def __init__(self, val=0, left=None, right=None):  
        self.val = val  
        self.left = left  
        self.right = right

在这个代码中,定义了一个名为TreeNode的类,它有三个属性:val表示节点的值,left表示左子节点,right表示右子节点。使用__init__方法初始化这些属性。如果需要,可以将val的值设置为一个特定的值,否则它的默认值为0。left和right属性的默认值为None,表示该节点没有左子节点和右子节点。

二叉树的遍历顺序- 4.2.4 -

二叉树的遍历顺序通常有四种,包括前序遍历、中序遍历、后序遍历和层次遍历。以下是它们的详细说明:

  • 前序遍历(Preorder Traversal):首先访问根节点,然后遍历左子树,最后遍历右子树。

  • 中序遍历(Inorder Traversal):首先遍历左子树,然后访问根节点,最后遍历右子树。

  • 后序遍历(Postorder Traversal):首先遍历左子树,然后遍历右子树,最后访问根节点。

  • 层次遍历(Level order Traversal):从根节点开始,按照层次从上到下、从左到右遍历整个二叉树。

深度优先遍历- 4.2.5 -

深度优先遍历(Depth-First Search,DFS)是一种用于遍历或搜索树或图的算法。这个算法会尽可能深地搜索树的分支。当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。

深度优先遍历的具体实现方式有多种,包括递归和迭代(使用栈)等。在二叉树中,常见的深度优先遍历方式有前序遍历、中序遍历和后序遍历。

广度优先遍历- 4.2.6 -

广度优先遍历(Breadth-First Search,BFS)是一种用于遍历或搜索树或图的算法。这个算法从根节点开始,首先访问根节点的所有相邻节点,然后对每个相邻节点执行相同的操作,再访问它们的未被访问过的相邻节点,以此类推。广度优先遍历按照层次顺序访问节点,从上到下、从左到右。

广度优先遍历的具体实现方式有多种,包括递归和迭代(使用队列)等。在二叉树中,广度优先遍历通常从根节点开始,将其所有子节点依次入队,然后逐个出队并访问,同时将每个节点的子节点入队。通过这种方式,广度优先遍历可以确保按照层次顺序访问二叉树中的所有节点。

以下是一个简单的广度优先遍历的Python代码示例:

from collections import deque  
  
def breadth_first_search(root):  
    queue = deque([root])  
    while queue:  
        node = queue.popleft()  
        print(node.val)  # 访问节点值  
        if node.left:  
            queue.append(node.left)  
        if node.right:  
            queue.append(node.right)

在这个示例中,使用Python的deque数据结构来实现队列,将根节点入队。然后,在循环中不断出队一个节点并访问它,同时将其子节点入队。通过这种方式,可以按照层次顺序访问二叉树中的所有节点。