当前位置: 网站首页 > 易盛娱乐2

关于二叉树三种遍历的递归/非递归实现

2019-08-27来源:易盛娱乐2

关于二叉树三种遍历的递归/非递归实现

以下算法实例中,二叉树定义如下:

struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {}};

遍历完成的序列存储在vector

前序遍历

递归

class Solution {public: vector<int> pre;// 存放完成遍历的序列 vector<int> preorderTraversal(TreeNode* root) { if(root){ // 按照 根->左->右 的顺序遍历 pre.push_back(root->val); preorderTraversal(root->left); preorderTraversal(root->right); } return pre; }};

按照根->左->右的遍历顺序,递归代码的可读性是显而易见的。


非递归(迭代)

class Solution {public: vector<int> preorderTraversal(TreeNode* root) { vector<int> pre;// 存放完成遍历的序列 stack<TreeNode*> s;// 辅助栈 s.push(root); TreeNode* ptr = NULL; while(!s.empty()){ ptr = s.top(); // 指针指向栈顶元素,表示当前处理结点. s.pop(); // 出栈,表示经过本次循环,该结点处理完成. if(ptr){ // 若当前结点为空,则不作操作. pre.push_back(ptr->val);// 根结点入结果,完成根->左->右中“根”操作. s.push(ptr->right); // 右孩子入栈. s.push(ptr->left); // 左孩子入栈. /* 在栈访问到当前ptr指向的结点的孩子结点时,按照栈先入后出的特性, 会先对左孩子进行处理,再对右孩子进行处理, 完成了根->左->右中“左->右”操作. */ } ptr = NULL; } return pre; }};

非递归代码用到了栈结构辅助遍历,因为要服从根->左->右的遍历顺序,所以初始化从根节点开始,首先将根节点入栈,后进入while循环。

while循环的退出条件是辅助栈为空,即树遍历完,二者的等价性是显然的。

观察while循环内部的代码,参考注释,ptr每指向一个非空结点,就会完成以下操作:

    根节点入结果右孩子入栈左孩子入栈

特别地,无论该结点左右孩子是否为空,都遵循这一操作,每当ptr指向空结点的时候,即为递归遍历中$if(root)$判断失败的时候。

结合递归代码,找出迭代中每一步对应着递归算法的哪一步,能帮助理解。


中序遍历

递归

class Solution {public: vector<int> in; vector<int> inorderTraversal(TreeNode* root) { if(root){ inorderTraversal(root->left); in.push_back(root->val); inorderTraversal(root->right); } return in; }};

按照左->根->右的遍历顺序,不加赘述。


非递归(迭代)

class Solution {public: vector<int> inorderTraversal(TreeNode* root) { vector<int> in; stack<TreeNode*> s; TreeNode* ptr = root; while(ptr || !s.empty()){ while(ptr){ s.push(ptr); ptr = ptr->left; } // 服从左->根->右的遍历顺序. ptr = s.top(); // 指针指向栈顶元素,表示当前处理结点. s.pop(); // 出栈,表示经过本次循环,该结点处理完成. // 值得注意,ptr指向结点出栈后,当前栈顶元素即为ptr的“根”结点. if(ptr){ // 若当前结点为空,则不作操作. in.push_back(ptr->val); // 根结点入结果,完成左->根->右中“左”操作. ptr = ptr->right; // ptr指向当前结点的右结点,完成“右”操作. } } return in; }};

与前序遍历有所不同,开始时,ptr指向根节点,服从左->根->右的遍历顺序。

参考代码,最外层while循环加入了触发条件ptr,是为了初始时s为空服务的。

进入最外层while循环后,要将当前ptr所指向结点左孩子以及左孩子的左孩子...以此类推,依此压栈(即内层while循环),结合代码理解。

在退出内层while循环后,栈顶元素即为需要遍历的树最深且最“左”的结点,它没有左孩子(可能有右孩子,所以不一定是叶子结点);结合代码,进入$if(ptr)$判断后,直接将它入结果,实际上,可以认为已经完成了左->根->右中的“左”操作和“根”操作,而“左”操作是一次空操作。

中序遍历的理解需要足够的抽象思维,每一次的“左”操作,是对当前结点的左孩子进行访问,同时也是该左孩子作为一棵“子树”进行中序遍历的操作。并且顺序如下:

$NodeRightarrow visit Nodeightarrow left Rightarrow inorderTraversal(Nodeightarrow left)$

其中 $visit Nodeightarrow left $ 只是一条指令,并不会直接将$Nodeightarrow left$ 的值入结果。$Nodeightarrow left$ 的值会在$inorderTraversal(Nodeightarrow left)$中入结果。


后序遍历

递归

class Solution {public: vector<int> post; vector<int> postorderTraversal(TreeNode* root) { if(root){ postorderTraversal(root->left); postorderTraversal(root->right); post.push_back(root->val); } return post; }};

按照左->右->根的遍历顺序,不加赘述。


非递归(迭代)

class Solution {public: vector<int> postorderTraversal(TreeNode* root) { vector<int> post; stack<TreeNode*> s; s.push(root); while(!s.empty()){ TreeNode* ptr = s.top(); s.pop(); if(ptr != NULL){ post.push_back(ptr->val); s.push(ptr->left); s.push(ptr->right); // 与前序遍历相反,先压入左孩子,再压入右孩子; // 实际上完成了按照“根->右->左”顺序的遍历. } } reverse(post.begin(), post.end()); // 后序遍历服从左->右->根的遍历顺序,post记录了根->右->左顺序的遍历; // 将post反转,即可得到后序遍历序列. return post; }};

原本后序遍历的非递归实现较为复杂,以上提供一种巧妙的实现方法。

考虑后序遍历服从左->右->根的遍历顺序,建立一种新的遍历模式,即按照根->右->左的顺序遍历,正与后序遍历相反,因此,在完成遍历后将结果反转,即可得到后序遍历序列。

简单证明方法的正确性:

设n为结点数;

当n==0,满足;当n==1,满足;当n==2,根结点(a)及其左/右孩子(b),根->右->左的顺序遍历:ab;后序遍历:ba;满足。当n==3,根结点(a)及其左孩子(b),右孩子(c),根->右->左的顺序遍历:acb;后序遍历:bca;满足。当n更大时,分成若干个部分,每个小部分满足$nle3$的情况,显然,拼接后仍然满足情况。

以上总结了二叉树三种遍历的递归/非递归实现,作笔记用;

若文中内容有纰漏、错误,望斧正。

// Szp 2018/11/27