树遍历

在计算机科学中，树遍历（也称为树搜索和漫步树）是图形遍历的一种形式，是指访问的过程（例如检索，更新或删除）在树数据结构中的每个节点，完全是一次。这样的遍历由访问节点的顺序进行分类。描述了以下二进制树的算法，但它们也可以推广到其他树木。

类型

与链接的列表，一维阵列和其他线性数据结构（按线性顺序遍历的一维阵列和其他线性数据结构）不同，树可能会以多种方式穿越。它们可能会以深度或广度优先的速度进行穿越。有三种常见的方法可以在深度阶段进行遍历：秩序，预订和后订单。除了这些基本的遍历外，还可以使用各种更复杂或混合的方案，例如深度限制的搜索，例如迭代深度深度搜索。后者以及广度优先的搜索也可用于遍历无限的树木，请参见下文。

树木遍历的数据结构

穿越树木涉及以某种方式迭代所有节点。因为从给定的节点中有多个可能的下一个节点（这不是线性数据结构），因此，假设顺序计算（不是并行），则必须将某些节点推迟- 以某种方式存储以供以后访问。这通常是通过堆栈（LIFO）或队列（FIFO）完成的。由于树是一种自我指的（递归定义）的数据结构，因此可以通过递归或更巧妙地以自然而清晰的方式来定义遍历。在这些情况下，递延节点被隐式存储在呼叫堆栈中。

深度优先的搜索可以通过堆栈轻松实现，包括递归（通过呼叫堆栈），而广度优先的搜索则可以通过队列（包括colecurscursility ocercursipalion coreue实施）来实现。

深度优先搜索

在深度优先搜索（DFS）中，搜索树在进入下一个兄弟姐妹之前会尽可能多地加深。

要使用深度优先搜索遍历二进制树，请在每个节点上执行以下操作：

1. 如果当前节点为空，则返回。
2. 按一定顺序执行以下三个操作：

   N：访问当前节点。

   L：递归横穿当前节点的左子树。

   R：递归横穿当前节点的右子树。

遍历的痕迹称为树的顺序化。遍历跟踪是每个访问节点的列表。没有根据前或后阶的顺序化来描述基础树的独特性。给定具有不同元素的树，预订或后订单与固定级配对足以独特地描述树。但是，预订后订购在树结构中留下了一些歧义。

相对于节点（在图中：红色，绿色或蓝色）的遍历的位置有三种方法，应进行节点的访问。正好的一种颜色的选择确切地决定了一个节点的一次访问，如下所述。访问所有三种颜色会导致相同节点的三倍访问，得出“全序”顺序化：

f -b -a -a -a -a -b -d -c -c -c -c -c -d -e -e -e -e -e -e -e -e -d -b -f - g -g -g -g -i -h -h -h -h -h -h -i -i -i -i - i- i- i- i- g -f

预订，NLR

1. 访问当前节点（在图中：位置红色）。
2. 递归遍历当前节点的左子树。
3. 递归遍历当前节点的右子树。

预订遍历是拓扑排序的，因为在完成任何子节点之前，要处理父节点。

后订单，LRN

1. 递归遍历当前节点的左子树。
2. 递归遍历当前节点的右子树。
3. 访问当前节点（在图中：位置蓝色）。

后顺序遍历可用于获取二进制表达树的后缀表达。

秩序，lnr

1. 递归遍历当前节点的左子树。
2. 访问当前节点（在图中：位置绿色）。
3. 递归遍历当前节点的右子树。

在排序的二进制搜索树中，在每个节点中，密钥大于其左子树中的所有键，并且比其右子树中的所有键都少，以上遍历遍历以上排序的顺序检索键。

反向预订NRL

1. 访问当前节点。
2. 递归遍历当前节点的右子树。
3. 递归遍历当前节点的左子树。

反向后订单，RLN

1. 递归遍历当前节点的右子树。
2. 递归遍历当前节点的左子树。
3. 访问当前节点。

反向内rnl

1. 递归遍历当前节点的右子树。
2. 访问当前节点。
3. 递归遍历当前节点的左子树。

在排序的二进制搜索树中，在每个节点中，密钥大于其左子树中的所有键，而右子树中的所有键都小，逆转顺序的遍历遍历以降序的顺序取回键。

任意树

要通过深度优先搜索遍历任意树（不一定是二进制树），请在每个节点上执行以下操作：

1. 如果当前节点为空，则返回。
2. 请访问当前节点进行预订遍历。
3. 对于每个i，从1到当前节点的子树的数量-1，或从后者到前者的反向遍历，请执行：
   1. 递归遍历当前节点的i -th子树。
   2. 请访问当前节点以进行固定遍历。
4. 递归遍历当前节点的最后一个子树。
5. 访问当前节点以获取后阶段遍历。

取决于手头的问题，预订，后订单，尤其是子树的数量 - 1级操作可能是可选的。同样，在实践中，可能需要预订，后订单和固定操作之一。例如，插入三元树时，通过比较项目进行预购操作。之后可能需要进行后订单操作来重新平衡树。

广度优先搜索

在广度优先的搜索（BFS）或级别搜索中，在进入下一个深度之前，尽可能地拓宽了搜索树。

其他类型

还有一些树遍历算法，它们既不将其分类为深度优先搜索也不是广度优先的搜索。一种这样的算法是蒙特卡洛树搜索，它集中于分析最有希望的动作，以搜索树的扩展为基于搜索空间的随机采样。

申请

预订遍历可用于从表达树中制作前缀表达式（抛光符号）：预 - 遍历表达树。例如，遍历预购屈服中所描绘的算术表达“ + * a - b c + d e ”。在前缀表示法中，只要每个操作员都有固定数量的操作数，就无需任何括号。预购遍历还用于创建树的副本。

后遍历可以生成二进制树的后缀表示形式（反向抛光符）。遍历后阶的算术表达的遍历“ a b c - * d e + +”；后者可以轻松地转换为机器代码，以通过堆栈机评估表达式。后订单遍历也用于删除树。释放孩子后，每个节点都会被释放。

根据设置二进制搜索树的比较器，在二进制搜索树上非常常用于二进制搜索树，因为它可以从基础设置中返回值。

实施

深度优先搜索实现

预订实施

procedure preorder(node)
    if node = null
        return
    visit(node)
    preorder(node.left)
    preorder(node.right) 

procedure iterativePreorder(node)
    if node = null
        return
    stack ← empty stack
    stack.push(node)
    while not stack.isEmpty()
        node ← stack.pop()
        visit(node)
        // right child is pushed first so that left is processed first
        if node.right ≠ null
            stack.push(node.right)
        if node.left ≠ null
            stack.push(node.left)

后订单实施

procedure postorder(node)
    if node = null
        return
    postorder(node.left)
    postorder(node.right)
    visit(node)

procedure iterativePostorder(node)
    stack ← empty stack
    lastNodeVisited ← null
    while not stack.isEmpty() or node ≠ null
        if node ≠ null
            stack.push(node)
            node ← node.left
        else
            peekNode ← stack.peek()
            // if right child exists and traversing node
            // from left child, then move right
            if peekNode.right ≠ null and lastNodeVisited ≠ peekNode.right
                node ← peekNode.right
            else
                visit(peekNode)
                lastNodeVisited ← stack.pop()

固定实施

procedure inorder(node)
    if node = null
        return
    inorder(node.left)
    visit(node)
    inorder(node.right)

procedure iterativeInorder(node)
    stack ← empty stack
    while not stack.isEmpty() or node ≠ null
        if node ≠ null
            stack.push(node)
            node ← node.left
        else
            node ← stack.pop()
            visit(node)
            node ← node.right

预订的另一种变体

如果树由数组表示（第一个索引为0），则可以计算下一个元素的索引：

procedure bubbleUp(array, i, leaf)
    k ← 1
    i ← (i - 1)/2
    while (leaf + 1) % (k * 2) ≠ k
        i ← (i - 1)/2
        k ← 2 * k
    return i
procedure preorder(array)
    i ← 0
    while i ≠ array.size
        visit(array[i])
        if i = size - 1
            i ← size
        else if i < size/2
            i ← i * 2 + 1
        else
            leaf ← i - size/2
            parent ← bubble_up(array, i, leaf)
            i ← parent * 2 + 2

前进到下一个或上一个节点

这 node 可以从二进制搜索树中发现 bst 通过标准搜索功能，该功能在没有父母指针的情况下显示在此处，即使用 stack 持有祖先的指针。

procedure search(bst, key)
    // returns a (node, stack)
    node ← bst.root
    stack ← empty stack
    while node ≠ null
        stack.push(node)
        if key = node.key
            return (node, stack)
        if key < node.key
            node ← node.left    
        else
            node ← node.right
    return (null, empty stack)

wordernext中的功能返回订购的邻居 node，要幺在 dir=1）或订购式cessor （用于 dir=0）和更新 stack，使得二进制搜索树可以在给定方向上依次依次进行订购和搜索 dir 进一步。

procedure inorderNext(node, dir, stack)
    newnode ← node.child[dir]
    if newnode ≠ null
        do
            node ← newnode
            stack.push(node)
            newnode ← node.child[1-dir]
        until newnode = null
        return (node, stack)
    // node does not have a dir-child:
    do
        if stack.isEmpty()
            return (null, empty stack)
        oldnode ← node
        node ← stack.pop()   // parent of oldnode
    until oldnode ≠ node.child[dir]
    // now oldnode = node.child[1-dir],
    // i.e. node = ancestor (and predecessor/successor) of original node
    return (node, stack)

请注意，该函数不使用键，这意味着顺序结构由二进制搜索树的边缘完全记录。对于没有方向改变的遍历，（摊销）平均复杂性为因为全部遍历大小的步骤 1步向上，1个边缘向下。最严重的复杂性是和作为树的高度。

以上所有实现都需要与树高度成比例的堆栈空间，这是递归的调用堆栈，而迭代式（祖先）堆栈的堆栈堆叠。在一棵平衡的树中，这可能是相当多的。通过迭代实现，我们可以通过维护每个节点中的母体指针或线程（下一节）来删除堆栈需求。

莫里斯使用螺纹

通过使每个左子指针（否则将是null）指向节点（如果存在的话）和每个正确的子指针（否则将是null）指向In-的二进制树是二进制树的螺纹。订购节点的继任者（如果存在）。

优点：

1. 避免递归，该递归使用呼叫堆栈并消耗内存和时间。
2. 该节点保留其父母的记录。

缺点：

1. 树更复杂。
2. 我们一次只能进行一次遍历。
3. 当两个孩子都不存在并且两个节点的值都指向其祖先时，这更容易出现错误。

Morris Traversal是使用螺纹的固定遍历的实现：

1. 创建指向内连载器的链接。
2. 使用这些链接打印数据。
3. 还原更改以还原原始树。

广度优先搜索

另外，下面列出的是基于简单的基于队列的级别遍历的伪代码，并且需要与给定深度处最大节点数量成比例的空间。这可能是节点总数的一半。可以使用迭代深度深度搜索来实现这种类型的遍历的更高效率方法。

procedure levelorder(node)
    queue ← empty queue
    queue.enqueue(node)
    while not queue.isEmpty()
        node ← queue.dequeue()
        visit(node)
        if node.left ≠ null
            queue.enqueue(node.left)
        if node.right ≠ null
            queue.enqueue(node.right)

如果树由数组表示（第一个索引为0），则在所有元素中都足够迭代：

procedure levelorder(array)
    for i from 0 to array.size
        visit(array[i])

无限的树

虽然通常是针对具有有限数量的节点（因此有限的深度和有限的分支因子）的树木进行的，但也可以为无限的树木进行。这在功能编程（尤其是在懒惰评估中）中特别感兴趣，因为无限数据结构通常很容易定义和使用，尽管没有（严格地）评估它们，因为这需要无限的时间。一些有限的树太大而无法明确表示，例如用于国际象棋或棋子的游戏树，因此分析它们就像无限一样有用。

遍历的基本要求是最终访问每个节点。对于无限的树，简单的算法通常会失败。例如，给定无限深度的二进制树，深度优先的搜索将沿着树的一侧（左侧）下降，从不访问其余的搜索，实际上永远不会访问订购或后阶段的遍历访问任何节点，因为它尚未达到叶子（实际上永远不会）。相比之下，广度（级别的）遍历将横穿无限深度的二元树，而实际上将横穿任何具有有界分支因子的树。

另一方面，给定深度2的树，根部有很多孩子，每个孩子都有两个孩子，深度优先的搜索将访问所有节点，因为一旦它耗尽了孙子（孙子的孩子）（一个节点） ，它将继续进行下一个节点（假设它不是后订单，在这种情况下，它永远不会达到根）。相比之下，广度优先的搜索将永远不会到达孙子，因为它试图先耗尽孩子。

可以通过无限的序数数进行更复杂的运行时间分析；例如，上面的深度2树的广度优先搜索将采用ω ·2步：第一级的ω，然后在第二层进行另一个ω。

因此，简单的深度优先或广度优先的搜索不会横穿每棵无限的树，并且在非常大的树上也不有效。但是，杂种方法可以通过对角线参数（“对角线”（垂直和水平的组合）横穿任何（次）无限树，这与深度和宽度的组合相对应）。

具体而言，鉴于无限分支的无限深度树，标记了根（）的子女（1），（2），...，孙子（1，1），（1，2），.. 。，（2 ，1），（2，2），...，等等。因此，节点是在有限（可能是空的）正数的一对一对应的中许多序列总和到给定值，因此所有条目都可以到达给定的自然数的有限数量，特别是2 ^{n -1}的组成，为n≥1 ），这给出了遍历。明确：

1. ()
2. (1)
3. (1, 1) (2)
4. (1, 1, 1) (1, 2) (2, 1) (3)
5. (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) (4)

ETC。

这可以解释为将无限的深度二进制树映射到这棵树上，然后应用广度优先搜索：替换将父节点连接到其第二个和以后的孩子的“朝下”边缘，从第一个孩子到第二个孩子孩子，从第二个孩子到第三个孩子等。是额外的，只能下降），这显示了无限二进制树与上述编号之间的对应关系；条目的总和（负一个）对应于距根的距离，这与无限二进制树的深度n -1处的2 ^{n -1}节点一致（2对应于二进制）。