无递归的二叉树遍历的直观解释

我已经看过许多文章和书籍(以及Stack Overflow答案),它们展示了如何使用显式堆栈而不是递归来迭代地执行预订,顺序和后序深度优先树遍历 . 例如:https://en.wikipedia.org/wiki/Tree_traversal#Depth-first_search_2

前序遍历很简单,但我认为其他的很复杂而且很明显 .

是否有任何来源(最好是文章或书籍)直观地解释这些算法,所以你可以看到有人会在一开始就提出这些算法?

回答(2)

3 years ago

  • 预订:通过访问节点处理节点,然后处理每个子节点 .

  • Inorder:通过处理左子节点,访问节点,然后处理右子节点来处理节点 .

  • PostOrder(DFS):通过处理每个子节点,然后访问节点来处理节点 .

在所有情况下,堆栈用于存储您不能立即执行的工作 . 预订案例最简单,因为您只需要推迟一种工作 - 处理子节点 .

预购:堆栈包含要处理的节点 . 要处理节点,请访问它,在堆栈上推送正确的子节点,然后处理左子节点 . 如果没有剩下的孩子,那么从堆栈中抓一个 .

顺序也很简单 . 堆栈必须存储要访问的节点和要处理的节点,但要处理的节点始终是刚访问的节点的正确子节点,因此:

Inorder:堆栈包含要访问的节点 . 当我们从堆栈中获取一个节点时,我们访问它,然后处理它的右子节点 . 当我们处理一个节点时,我们把它放在堆栈上,然后处理它的左子节点 .

后序很棘手,因为堆栈必须存储要访问的节点和要处理的节点,并且它们并不总是像在Inorder情况下那样简单相关 . 堆栈必须以某种方式指示哪个是哪个 .

你可以这样做:

后序:堆栈包含要访问或处理的节点以及已处理的子节点数 . 要处理堆栈中的条目(n,x),请访问节点n,如果它具有<= x children . 否则将(n,x 1)放在堆栈上并处理节点的第一个未处理的子节点 .

3 years ago

How to come up with an iterative solution without a stack

堆栈不是实现迭代树遍历所必需的!您可以通过在树节点数据结构中保留父指针来删除任何堆栈 . 这就是你想出来的方式:

什么是迭代解决方案?迭代解决方案是一种解决方案,其中代码的固定部分在循环中重复执行(几乎是迭代的确定性) . 循环的输入是系统的状态s1,输出是状态s2,循环使系统从状态s1进入状态s2 . 从初始状态s开始,到达最终所需状态时结束 .

所以我们的问题减少到找到:

  • 系统状态的表征,有助于我们实现这一目标 . 初始状态将与我们的初始条件一致,并且终端状态将与我们期望的结果一致

  • 查找作为循环的一部分重复执行的指令

(这有效地将树变成了状态机 . )

在树遍历中,每一步都访问一个节点 . 树的每个节点最多访问三次 - 一次来自父节点,一次来自leftChild,一次来自右子节点 . 我们在特定步骤中对节点的处理取决于它是三种情况中的哪一种 .

因此,如果我们捕获所有这些信息:我们正在访问哪个节点,以及它是哪种情况,我们就会对系统进行描述 .

捕获此信息的方法是存储对先前节点/状态的引用:

Node current;
Node previous;

如果previous = current.parent,那么我们将从父级访问 . 如果previous = current.leftChild,我们从左边访问,如果previous = current.rightChiild,我们正在访问右边 .

我们可以捕获此信息的另一种方式:

Node current; 
boolean visitedLeft;
boolean visitedRight;

如果visitedLeft和visitedRight都是假的,那么我们是从父母访问的,如果visitedLeft是真的但是visitRight是假的,我们正在从左边访问,如果visitedLeft和visitedRight都是真的,我们正在从右边访问(第四个state:visitedLeft false但visitedRight为false,在preOrder中永远不会到达) .

最初,我们从viisitedLeft = false,visitedRight = false和current = root开始 . 当遍历完成时,我们期望visitedLeft = true,visitedRight = true,current = null .

在里面指令作为循环的一部分重复运行,系统必须从一种状态移动到另一种状态 . 因此,在说明中,我们只告诉系统遇到任何状态时要做什么,以及何时结束执行 .

您可以将所有三个遍历组合在一个函数中:

void traversal(String typeOfTraversal){

    boolean visitedLeft = false;
    boolean visitedRight = false;
    TreeNode currentNode = this.root;

    while(true){

        if (visitedLeft == false && currentNode.leftChild != null){
            if(typeOfTraversal == "preOrder"){
                System.out.println(currentNode.key);
            }
            currentNode = currentNode.leftChild;
            continue;
        }

        if (visitedLeft == false && currentNode.leftChild == null){
            if(typeOfTraversal == "preOrder"){
                System.out.println(currentNode.key);
            }
            visitedLeft = true;
            continue;
        }

        if (visitedLeft == true && visitedRight == false && currentNode.rightChild != null){
            if(typeOfTraversal == "inOrder"){
                System.out.println(currentNode.key);
            }
            currentNode = currentNode.rightChild;
            visitedLeft = false;
            continue;
        }

        if (visitedLeft == true && visitedRight == false && currentNode.rightChild == null){
            if(typeOfTraversal == "inOrder"){
                System.out.println(currentNode.key);
            }
            visitedRight = true;
            continue;
        }

        if (visitedLeft == true && visitedRight == true && currentNode.parent != null){
            if(typeOfTraversal == "postOrder"){
                System.out.println(currentNode.key);
            }

            if (currentNode == currentNode.parent.leftChild){
                visitedRight = false;
            }
            currentNode = currentNode.parent;
        }

        if (visitedLeft == true && visitedRight == true && currentNode.parent == null){       
            if(typeOfTraversal == "postOrder"){
                System.out.println(currentNode.key);
            }
            break; //Traversal is complete.
        }

如果给定节点级锁定,则此算法允许并行遍历和更新树 . 除了分离非叶节点之外的任何原子操作都是安全的 .


How to come up with a stack-based solution

在考虑将递归解决方案转换为迭代解决方案时,或者为递归定义的问题提出迭代解决方案时,堆栈是有用的数据结构 . 调用堆栈是一种堆栈数据结构,它存储有关计算机程序的活动子例程的信息,是大多数高级编程语言在引擎盖下实现递归的方式 . 因此,在迭代解决方案中明确使用堆栈,我们只是模仿处理器在编写递归代码时所执行的操作 . Matt Timmermans的回答给出了为什么使用堆栈以及如何提出基于堆栈的显式解决方案的良好直觉 .

我已经写过如何在这里提出有两个堆栈的postOrder解决方案:Understanding the logic in iterative Postorder traversal implementation on a Binary tree .


基于父指针的方法比基于堆栈的方法消耗更多的内存 . 在堆栈上,仍然需要处理的节点的指针是瞬态的,只需要O(log n)堆栈空间的顺序,因为你只需要保留足够的它们以便在树中的单个路径(并在实践中) ,这可能会少) . 相反,将子指针与节点一起存储需要固定的O(n)空间 .