Liny_@NotePad

沉迷ACG中

二叉树的非递归遍历

YOYO posted @ 2009年5月16日 00:15 in 【算法】与【数据结构】 with tags 数据结构 二叉树 遍历 , 2454 阅读

用栈实现即可

先序：

  1. void clr(node t[]){
  2.         stack<node*> st;
  3.         node* h = &t[0];
  4.         while(h||!st.empty()){
  5.                 while(h){
  6.                         visit(h->data);
  7.                         st.push(h->rchild);
  8.                         h = h->lchild;
  9.                 }
  10.                 if(!st.empty()){
  11.                         h = st.top();
  12.                         st.pop();
  13.                 }
  14.         }
  15. }

 

中序：

  1. void lcr(node t[]){
  2.         stack<node*> st;
  3.         node* h = &t[0];
  4.         while(h||!st.empty()){
  5.                 while(h){
  6.                         st.push(h);
  7.                         h = h->lchild;
  8.                 }
  9.                 if(!st.empty()){
  10.                         h = st.top();
  11.                         st.pop();
  12.                         visit(h->data);
  13.                         h = h->rchild;
  14.                 }
  15.         }
  16. }

 

后序：

  1. void lrc(node t[]){
  2.         stack<node*> st;
  3.         stack<int> flagst;
  4.         node* h = &t[0];
  5.         int flag = 0;
  6.         while(h||!st.empty()){
  7.                 while(h){
  8.                         st.push(h);
  9.                         flagst.push(0);
  10.                         h = h->lchild;
  11.                 }
  12.                 h = st.top();
  13.                 st.pop();
  14.                 flag = flagst.top();
  15.                 flagst.pop();
  16.                 while(flag){
  17.                         visit(h->data);
  18.                         if(!st.empty()){
  19.                                 h = st.top();
  20.                                 st.pop();
  21.                                 flag = flagst.top();
  22.                                 flagst.pop();
  23.                         }else{
  24.                                 return;
  25.                         }
  26.                 }
  27.                 st.push(h);
  28.                 flagst.push(1);
  29.                 h = h->rchild;
  30.         }
  31. }
  • 无匹配
Small_feed 评论 (0)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter