从二叉树的遍历谈递归和非递归算法二叉树是数据结构课程中一种重要的模型，在很多应用中都会用到，二叉树遍历有三种：前序遍历，中序遍历和后序遍历，所谓的先，中后是就根节点而言，二叉树的遍历的实现经典的算法是采用递归算法，递归算法比较简单易懂，实现起来也比较容易，这里主要是讨论如果用非递归算法来实现遍历，以取代递归算法，递归算法在运行时底层实际上也是用一个栈来保存中间过程，以便于回溯，所以非递归算法的实现本质上是构造一个栈，用来保存中间值。以二叉树的先序遍历为例，递归算法如下： void preVisit（Node root） { visit(root); -------1 preVisit(root.left);------2 preVisit(root.right);-----3 } 该程序执行时，执行1后，访问了根节点，然后执行2，第二行代码递归调用访问左子树，此时底层把root入栈，因为要访问右子树必须要知道根节点。 非递归算法实现上本质上和上面的过程一样，我们需要构造一个栈用来保存访问过的各个根节点。 |
郑重声明：资讯 【从二叉树的遍历谈递归和非递归算法- Windows Live】由 发布，版权归原作者及其所在单位，其原创性以及文中陈述文字和内容未经(企业库qiyeku.com)证实，请读者仅作参考，并请自行核实相关内容。若本文有侵犯到您的版权， 请你提供相关证明及申请并与我们联系（qiyeku # qq.com）或【在线投诉】，我们审核后将会尽快处理。
—— 相关资讯 ——
