与你交谈系列#3

介绍

今天我们将介绍二叉树的理论和实践基础以及遍历它的方法。

树通常是图族的子集，其构建和管理遵循一定的规则。

二叉树

二叉树是一种具体的数据结构，其中每个节点最多有两个子节点。通常每个节点都有 3 个属性：data、leftchild 和 rightchild。

它用于按“标准”对不同类型的二叉树进行分类。

让我们看看那里存在哪些类型（类）：

基于子节点数量的二叉树类型（标准：子节点的节点数量）
基于级别完成的二叉树类型（标准：级别的树完成）
基于节点值的二叉树类型（标准：节点值）

让我们分别看看每种类型。

基于子节点数量的二叉树类型

完整二叉树
退化（或病态）树
倾斜二叉树

基于级别完成的二叉树类型

完全二叉树
完美二叉树
平衡二叉树

基于节点值的二叉树类型

二叉搜索树
avl 树
红黑树
b树
b+树
线段树

如果您想更深入地了解其中每一个，这里有完整的概述。

很好，现在我们从概念上了解什么是二叉树以及可能的类型。

image description

现在，让我们编写代码。回想一下，二叉树由节点组成，每个节点都有数据、leftchild 和 rightchild 属性。

from typing import any

class treenode:
    def __init__(self, data: any):
        self.data = data
        self.left = none
        self.right = none

# define all the nodes we need
root = treenode('r')
nodea = treenode('a')
nodeb = treenode('b')
nodec = treenode('c')
noded = treenode('d')

# connect all the nodes between each other
root.left = nodea
root.right = nodeb
nodea.left = nodec
nodea.right = noded

# what we've got
    r
   / \
  a   b
 / \ 
c   d

登录后复制

接下来至关重要的就是如何遍历二叉树。

遍历二叉树

通常来说，遍历二叉树主要有2种方式（类型），广度优先搜索（bfs）和深度优先搜索（dfs）。

bfs 表示在进入树中的下一层之前访问同一级别的节点。这意味着树是在更侧面的方向上探索的。
dfs 代表当遍历树一直向下移动到叶节点时，向下逐枝探索树。

此外，dfs 遍历还有三种类型：

预购
下单后
按顺序

dfs及其遍历类型

"""
preorder - is done by visiting the root node first, then recursively do a pre-order traversal of the left subtree, followed by a recursive pre-order traversal of the right subtree.

this traversal is "pre" order because the node is visited "before" the recursive pre-order traversal of the left and right subtrees.
"""

def pre_order(node):
    if node:
        print(node.value)
        pre_order(node.left)
        pre_order(node.right)

登录后复制

与你交谈系列#3

"""
postorder - works by recursively doing a post-order traversal of the left subtree and the right subtree, followed by a visit to the root node.

what makes this traversal "post" is that visiting a node is done "after" the left and right child nodes are called recursively.
"""

def post_order(node):
    if node:
        post_order(node.left)
        post_order(node.right)
        print(node.value)

登录后复制

与你交谈系列#3

"""
inOrder - does a recursive In-order Traversal of the left subtree, visits the root node, and finally, does a recursive In-order Traversal of the right subtree.

What makes this traversal "in" order, is that the node is visited in between the recursive function calls. The node is visited after the In-order Traversal of the left subtree, and before the In-order Traversal of the right subtree.
"""

def in_order(node):
    if node:
        in_order(node.left)
        print(node.value)
        in_order(node.right)

登录后复制

与你交谈系列#3