二叉树递归遍历与非递归遍历 ゝ一世哀愁。 2022-08-02 14:43 236阅读 0赞 # 二叉树递归遍历与非递归遍历 # -------------------- * 二叉树递归遍历与非递归遍历 * 引言 * 递归式遍历 * 前序遍历 * 中序遍历 * 后序遍历 * 非递归式遍历 * 前序遍历 * 中序遍历 * 后序遍历 * 一种更简单的非递归式遍历 * 前序遍历 * 中序遍历 * 后序遍历 * 总结 -------------------- ## 引言 ## 由于二叉树是由递归定义的一种数据结构,因此递归式遍历也就是最符直觉的一种遍历方式。此外,由于递归的简洁性以及三种递归的高度统一,因此递归式遍历也是容易理解以及最简单好记的方式。然而,递归也会有其缺点,例如当一颗二叉树的深度很深的适合,采用递归的方式便有可能引起`segment fault`。因此,在必要的时候也需要将二叉树的遍历写成非递归的形式。 首先我们需要生成一棵树,来进行遍历以及测试,树的结构如下所示 ![BinaryTree][] 树结构节点定义如下: struct TreeNode { int val; TreeNode * left; //左子树 TreeNode * right; //右子树 TreeNode(int x):val(x),left(NULL),right(NULL) { } }; ## 递归式遍历 ## 树结构本身采用递归式定义,因此采用递归方式遍历也很直观和容易理解,各种遍历方式`c++`代码如下 ### 前序遍历 ### 先序遍历按照根节点->左子树->右子树的顺序进行遍历,首先我们先去方位其根节点,如果其存在左子树,便转向左子树遍历,遍历完左子树后,如果存在右子树,便转向右子树遍历,因此其代码如下 void Preorder_Recursive(TreeNode * root) { if(!root) //如果遇到空树或到达叶节点的孩子(NULL) { return; } cout << root->val <<" "; //操作根节点 if(root->left) { Preorder_Recursive(root->left); //转向左子树 } if(root->right) { Preorder_Recursive(root->right); //转向右子树 } } 调用上述函数的输出结果为: Preorder_Recursive 1 2 4 5 6 8 9 7 3 ### 中序遍历 ### 中序遍历是按照左子树->根节点->右子树的顺序遍历二叉树,因此其代码如下: void Inorder_Recursive(TreeNode * root) { if(!root) //如果遇到空树或到达叶节点的孩子(NULL) { return; } if(root->left) { Inorder_Recursive(root->left); //转向左子树 } cout << root->val << " "; //操作根节点 if(root->right) { Inorder_Recursive(root->right); //转向右子树 } } 输出结果为: Inorder_Recursive 4 2 6 8 9 5 7 1 3 ### 后序遍历 ### 后序遍历按照左子树->右子树->根节点的顺序进行遍历,因此其代码如下: void Postorder_Recursive(TreeNode * root) { if(!root) //如果遇到空树或到达叶节点的孩子(NULL) { return ; } if(root->left) { Postorder_Recursive(root->left); //转向左子树 } if(root->right) { Postorder_Recursive(root->right); //转向右子树 } cout << root->val << " "; //操作根节点 } 调用上述函数得到后序遍历序列为: Postorder_Recursive 4 9 8 6 7 5 2 3 1 ## 非递归式遍历 ## ### 前序遍历 ### 根据上述前序遍历的递归式代码我们将其改造成迭代式算法。 首先,我们观察下图所示的先序遍历的递归式代码的节点访问顺序, ![PreorderBinaryTree][] 前序遍历首先从根节点出发,一路向左,一直访问到最左边的节点,(图中的4号节点),如箭头1 2 所示。而后,转向其兄弟节点(也就是2号节点的右子树),继续重复如上过程。当访问完某个节点的右子树时(比如说8),即应当找到其某个双亲节点(比如说5)的还未访问的右子树继续访问。 如上,我们可以利用自己维护的栈结构实现算法如下: 1. 建立一指针`root`,令其指向二叉树的根节点 2. 如果栈为空则返回,不为空则循根节点->左子树的顺序一路向左访问节点并入栈 3. 当到达最左边节点时,栈中最上方元素出栈 4. 如果出栈元素有右子树,则令`root`指向它,并重复2、3步 5. 如果出栈元素无右子树,则继续出栈元素并重复4、 5步 将上述算法兑换为代码为: void Preorder_Iterative(TreeNode * root) { if(!root) { return; } stack<TreeNode*> s; while(root) { cout << root->val << " "; if(root->left) { s.push(root); root = root->left; } else if (root->right) { root = root->right; } else { while(!root->right && !s.empty()) { root = s.top(); s.pop(); } root = root->right; } } } 调用上述程序,得到先序遍历序列为 Preorder_iterative 1 2 4 5 6 8 9 7 3 ### 中序遍历 ### 同样,沿用刚才的习惯,首先画出中序遍历的节点访问轨迹 ![InorderBinaryTree][] 从上面的图中可以发现,中序遍历是从4号节点,也就是从最左边的节点开始访问。因此,我们先找到这棵树的最左边的节点进行访问。然后访问其双亲节点(2号节点),再次访问双亲节点的右子树的最左边的节点,不断重复上述步骤即可遍历完一棵二叉树。 > 如果一个节点没有左子树,那么最左边的节点就是它自己,比如6、8、9号节点 根据以上描述,总结算法大体如下: 1. 设立指针`root`,并指向二叉树的根节点 2. 找到`root`最左边的节点,并将沿路节点入栈 3. 元素出栈并令`root`指向它,访问之 4. 如果`root`有右子树,令`root`指向它,算法回到2 5. 如果`root`没有右子树,重复3、4、5 将其兑换为代码如下: void Inorder_Iterative(TreeNode * root) { if(!root) { return; } stack<TreeNode *> s; while(root) { while(root->left) //找到最左边的节点 { s.push(root); root = root->left; } cout << root->val << " "; //访问之 while(!root->right && !s.empty()) { root = s.top(); s.pop(); cout << root->val << " "; } root = root->right; } } 运行后得到中序遍历序列: Inorder_Iterative 4 2 6 8 9 5 7 1 3 ### 后序遍历 ### 后续遍历的迭代式写法是三种遍历里面最难的一种,不过按照我们上面的方法进行分析依然能够写出其算法。 首先我们画出后续遍历的访问轨迹图: ![LastorderBinaryTree][] 可以看出,其跟中序访问的起点都是一样的,都是首先找到最左边的节点并访问之。在一路向左找的过程中,将沿途经过节点都放入栈中。然后,在其双亲节点不出栈的情况下转到其兄弟节点(双亲节点的右子树),并继续找到最左边节点访问,转到其兄弟节点,……直到访问完最下层的右子树(如9号节点),才开始栈中元素退栈并访问。 但是这里会出现一个问题就是比如说将5号节点从栈中退出来时如果不去转向它的右子树(7号节点)访问,那么它的右子树就会访问不到,如果转向了的话,那么8号节点退栈时就会再次转向其右子树(9号节点)进行访问。显然9号节点已经是被访问过了的。 因此,我们这里可以对栈中元素做一标记,当已经经由它转向右子树了的标记为`false`,当这样的节点位于栈顶时,只需直接退栈并访问即可。对于未经它转向右子树的默认标记问`true`,当这种节点位于栈,不能直接退栈,而是要经由它转向它的右子树并将其标记为`false`,当它再次位于栈顶时,才可直接退栈并访问。 因此,对上面所说总结大体如下 1. 设立指针`root`,指向二叉树根节点 2. 一路向左走,走到最左边节点,并将沿途节点压人栈中,且标记为`true` 3. 访问栈顶节点 4. 如果栈顶节点标记为`true`,将其标记为`false`,令`root`指向其右子树 5. 如果栈顶节点标记为`false`,将其出栈并访问之 兑换为代码如下: struct TreeNodeWithMark { TreeNode * node; bool isFirst; TreeNodeWithMark(TreeNode * p):node(p),isFirst(true) { } }; void Lastorder_Iterative(TreeNode * root) { if(!root) { return; } TreeNodeWithMark * temp = NULL; stack<TreeNodeWithMark *> s; while(root || !s.empty()) { //找到最左边节点 while(root) { s.push(new TreeNodeWithMark(root)); root = root->left; } if(!s.empty()) { temp = s.top(); // 访问栈顶元素 if(temp->isFirst) //还未经其转到过右子树 { temp->isFirst = false; root = temp->node->right; } else //已经经过其转到过右子树 { s.pop(); cout << temp->node->val << " "; root = NULL; } } } } 调用上述代码,输出后序遍历序列: Lastorder_Iterative 4 9 8 6 7 5 2 3 1 ## 一种更简单的非递归式遍历 ## 迭代式的二叉树遍历虽然提高了程序的鲁棒性但是却不容易理解。即使已经弄明白了算法的思想但是手生的人想要快速写出这三种算法也应该不是一件容易的事情。 因此,下面将把三种迭代式算法作一统一,使其更加易记易理解。 ### 前序遍历 ### 先看这样一个先序遍历的迭代式遍历版本: void Preorder_Iterative_easy(TreeNode * root) { if(!root) { return; } stack<TreeNode*> s; s.push(root); while(!s.empty()) { root = s.top(); s.pop(); cout << root->val << " "; if(root->right) { s.push(root->right); } if(root->left) { s.push(root->left); } } } 执行输出为: Preorder_Iterative_easy 1 2 4 5 6 8 9 7 3 在这个算法中,通过`root`指针将其左子树以及右子树按先序遍历的倒序放入栈中,这样就可以按照先序遍历的顺序进行出栈并遍历。 基于这种想法,我们可以将中序遍历和后续遍历写成类似的形式,这样,三个算法之间唯一变化的就是`root`指针以及其左右子树的入栈顺序其余部分则可以保持不变。下面将介绍这种形式的中序遍历和后续遍历算法。 ### 中序遍历 ### 在上述形式的中序遍历以及后序遍历算法中,`root`指针在第一次出栈时不能对其进行操作(否则就会变成先序遍历了),因此,`root`指针还需要进行第二次入栈操作才能使其本身以及其左右子树在栈中形成正确的顺序并在第二次出栈时进行操作。因此,可以借鉴上面的迭代式后序遍历算法的做法,设置一标识位进行判断。 想清楚了做法,我们开始写代码: void Inorder_Iterative_easy(TreeNode * root) { if(!root) { return; } stack<TreeNodeWithMark*> s; s.push(new TreeNodeWithMark(root)); TreeNodeWithMark * curr; while(!s.empty()) { curr = s.top(); root = curr->node; s.pop(); if(curr->isFirst) { curr->isFirst = false; if(root->right) { s.push(new TreeNodeWithMark(root->right)); } s.push(curr); if(root->left) { s.push(new TreeNodeWithMark(root->left)); } } else { cout << root->val << " "; } } } 执行输出: Inorder_Iterative_easy 4 2 6 8 9 5 7 1 3 ### 后序遍历 ### 有了上面的遍历算法,再写后序遍历真的是简单无比: void Lastorder_Iterative_easy(TreeNode * root) { if(!root) { return; } stack<TreeNodeWithMark*> s; s.push(new TreeNodeWithMark(root)); TreeNodeWithMark * curr; while(!s.empty()) { curr = s.top(); root = curr->node; s.pop(); if(curr->isFirst) { curr->isFirst = false; s.push(curr); if(root->right) { s.push(new TreeNodeWithMark(root->right)); } if(root->left) { s.push(new TreeNodeWithMark(root->left)); } } else { cout << root->val << " "; } } } 执行输出: Lastorder_Iterative_easy 4 9 8 6 7 5 2 3 1 可以看出,这次三个算法的唯一不同就是`s.push(curr);`这条语句的位置。 这次,这三个算法的不同只是根节点的入栈顺序的不同,相信理解了其中的一个算法,其余的两个算法也能够很快速的写出。 不过,这种算法也有它的缺点,那就是额外多占用了O(n)的空间。 ## 总结 ## 综上所述,三种便利算法各有利弊。 递归式算法高度同一,最为简洁也最好理解,但是当二叉树的高度很大时往往会引起递归深度过深从而引起程序异常。 一般的迭代式算法不够简洁也不够统一,因此也不好理解,但是却换来了最好的性能优势。 最后的迭代式算法也对三种便利方式进行了统一,比一般的迭代式算法简洁也比一般的迭代式算法好理解,但是却损失了一定的性能。 总之,三种遍历方式没有绝对的谁好谁坏,到底使用哪种还是要看具体的应用场景。 本文到此结束,作者水平有限(还是个小菜鸟),算法也未经过更多样例测试验证,如若存在错误,欢迎指正。大家相互学习,共同提高:-D [BinaryTree]: /images/20220731/64ee08beae0d422e88c64a333d330905.png [PreorderBinaryTree]: /images/20220731/c684a5416a634aeb9654f8635fbab824.png [InorderBinaryTree]: /images/20220731/c1cc97934834411e8acb0a07c5235fec.png [LastorderBinaryTree]: /images/20220731/442f457336c444c88e70433cfef4f743.png
还没有评论,来说两句吧...