首页 > 代码库 > 二叉树四种遍历非递归
二叉树四种遍历非递归
1 void levelOrder(Bitree* root){ 2 queue<Node*> nodeQueue; 3 Node* pointer=root; 4 if(pointer){ 5 nodeQueue.push(pointer); 6 } 7 while(!nodeQueue.empty()){ 8 pointer=nodeQueue.front(); 9 visit(pointer);10 nodeQueue.pop();11 if(pointer->left)nodeQueue.push(pointer->left);12 if(pointer->right)nodeQueue.push(pointer->right);13 }14 }
广度遍历，用队列存节点，访问后左右子节点入列，原节点弹出
1 void preOrder(Bitree* root){ 2 stack<Node*> nodeStack; 3 Node* pointer=root; 4 while(!nodeStack.empty()||pointer){ 5 if(pointer){ 6 visit(pointer); 7 if(pointer->right==NULL) nodeStack.push(pointer->right); 8 pointer=pointer->left; 9 }10 else{11 pointer=nodeStack.top();12 nodeStack.pop();13 }14 }15 }
先序遍历，向左扫，有右节点则右节点入栈，扫完一撇后指向栈顶，再扫一撇
1 void inOrder(Bitree* root){ 2 stack<Node*> nodeStack; 3 Node* pointer=root; 4 while(!nodeStack.empty()||pointer){ 5 if(pointer){ 6 nodeStack.push(pointer); 7 pointer=pointer->left; 8 } 9 else{10 pointer=nodeStack.top();11 visit(pointer);12 pointer=pointer->right;13 nodeStack.pop();14 }15 }16 }
中序遍历，先一撇节点入栈，直到NULL，然互扫栈顶，指向右节点继续
1 void posOrder(Bitree* root){ 2 stack<Node*> nodeStack; 3 Node* pointer=root; 4 Node* pre=root; 5 while(pointer){ 6 for(;pointer->left!=NULL;pointer=pointer->left) nodeStack.push(pointer); 7 while(pointer!=NULL&&(pointer->right==NULL||pointer->right==pre)){ 8 visit(pointer); 9 pre=pointer;10 if(nodeStack.empty()) return;11 pointer=nodeStack.top();12 nodeStack.pop();13 }14 nodeStack.push(pointer);15 pointer=pointer->right;16 }17 }
后序遍历，先一撇入栈，然后如果节点右儿子扫完或没右儿子，扫节点，指向栈顶；如果有右儿子，节点入栈，指向右儿子继续。
二叉树四种遍历非递归
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。