首页 > 代码库 > 二叉树非递归遍历
二叉树非递归遍历
1.非递归先序遍历
要点：总是先访问根root，而将root的右结点压入栈中，当root没有左结点时，取出栈顶元素给root。
void preorder(node* root){ if(root==NULL) return; stack<node*> s; while(true){ cout<<root->data<<endl; if(root->right!=NULL) s.push(root->right); if(root->left!=NULL) root = root->left; else if(s.empty()) return; else{ root = s.top(); s.pop(); } }}
2.非递归中序遍历
要点：从根结点开始将左结点压栈，直到没有左结点为止，然后访问栈顶元素并出栈，完了之后，检查栈顶元素是否有右结点，如果有，还需将其压栈。
void inorder(node* root){ if(root==NULL) return; stack<node*> s; s.push(root); while(true){ root = s.top(); while(root->left!=NULL) s.push(root = root->left); do{ root = s.top(); cout<<root->data<<endl; s.pop(); }while(root->right==NULL&&!s.empty()); if(root->right!=NULL) s.push(root->right); else return; }}
3.非递归后序遍历
要点：先沿着最左路径将最左的一条路径上的结点压入栈，当栈顶元素既没有左结点也没有右结点时，访问该元素。弹出栈，然后判断刚被弹出的结点是新栈顶元素的左结点还是右结点，如果是左结点，将其右结点压入栈中；如果是右结点，可以继续访问新的栈顶元素。
void postorder(node* root){ if(root==NULL) return; stack<node*> s; s.push(root); while(true){ root = s.top(); while(root->left!=NULL) s.push(root = root->left); if(root->right!=NULL) s.push(root->right); else{ do{ root = s.top(); s.pop(); cout<<root->data<<endl; if(s.empty()) return ; }while(root==s.top()->right||s.top()->right==NULL); s.push(s.top()->right); } }}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。