搞笑图片网站源码,网站seo需要用到哪些工具,wordpress没有登录口,查信息的网站有哪些这里涉及到二叉树的非递归操作有#xff1a;先序遍历、中序遍历、后序遍历数据结构树结点#xff1a;structNode { chardata; Node *left; Node *right; };标志#xff1a;enumTag{goLeft, goRight, goBack };goLeft指示访问左子树goLeft指示访问右子树#xf…这里涉及到二叉树的非递归操作有先序遍历、中序遍历、后序遍历 数据结构 树结点struct Node { char data; Node * left; Node * right; }; 标志enum Tag{goLeft, goRight, goBack }; goLeft指示访问左子树 goLeft指示访问右子树左子树已访问 goBack指示回溯(左右子树均已访问) 两个栈:vectorNode * vec_node; vectorTag vec_flag; 两个栈同时消长、空 所有操作相同的部分Node *curNode vec_node.back();//栈顶Tag curFlag vec_flag.back(); //栈顶switch(curFlag) { case goLeft: //更改标志 vec_flag.pop_back(); vec_flag.push_back(goRight); //左子树入栈 if(curNode-left ! NULL) { vec_node.push_back(curNode-left); vec_flag.push_back(goLeft); } break; case goRight: //更改标志 vec_flag.pop_back(); vec_flag.push_back(goBack); //右子树入栈 if(curNode-right ! NULL) { vec_node.push_back(curNode-right); vec_flag.push_back(goLeft); } break; case goBack: //结点出栈 vec_flag.pop_back(); vec_node.pop_back(); break; default: break; }//switch-end 几种操作唯一不同的是需要的操作放置的位置不同。 先序遍历打印结点放在goLeft中 中序遍历打印结点放在goRight中 后续遍历打印结点放在goBack中 打印所有路径在goBack中判断是否为叶子结点如果是打印栈中所有路径如果否直接出栈 详细代码见下面:(注意其中红色的地方是唯一差别的地方#include iostream #include vector #include cstdlibusing namespace std;struct Node { char data; Node * left; Node * right; };enum Tag{goLeft, goRight, goBack };void PreOrder(Node *root) { assert(root ! NULL); vectorNode * vec_node; vectorTag vec_flag; //init vec_node.push_back(root); vec_flag.push_back(goLeft); while(!vec_node.empty()) { Node *curNode vec_node.back(); Tag curFlag vec_flag.back(); switch(curFlag) { case goLeft: cout curNode-data ; vec_flag.pop_back(); vec_flag.push_back(goRight); if(curNode-left ! NULL) { vec_node.push_back(curNode-left); vec_flag.push_back(goLeft); } break; case goRight: vec_flag.pop_back(); vec_flag.push_back(goBack); if(curNode-right ! NULL) { vec_node.push_back(curNode-right); vec_flag.push_back(goLeft); } break; case goBack: vec_flag.pop_back(); vec_node.pop_back(); break; default: break; }//switch-end }//while-end }void InOrder(Node *root) { assert(root ! NULL); vectorNode * vec_node; vectorTag vec_flag; //init vec_node.push_back(root); vec_flag.push_back(goLeft); while(!vec_node.empty()) { Node *curNode vec_node.back(); Tag curFlag vec_flag.back(); switch(curFlag) { case goLeft: vec_flag.pop_back(); vec_flag.push_back(goRight); if(curNode-left ! NULL) { vec_node.push_back(curNode-left); vec_flag.push_back(goLeft); } break; case goRight: cout curNode-data ; vec_flag.pop_back(); vec_flag.push_back(goBack); if(curNode-right ! NULL) { vec_node.push_back(curNode-right); vec_flag.push_back(goLeft); } break; case goBack: vec_flag.pop_back(); vec_node.pop_back(); break; default: break; }//switch-end }//while-end }void PostOrder(Node *root) { assert(root ! NULL); vectorNode * vec_node; vectorTag vec_flag; //init vec_node.push_back(root); vec_flag.push_back(goLeft); while(!vec_node.empty()) { Node *curNode vec_node.back(); Tag curFlag vec_flag.back(); switch(curFlag) { case goLeft: vec_flag.pop_back(); vec_flag.push_back(goRight); if(curNode-left ! NULL) { vec_node.push_back(curNode-left); vec_flag.push_back(goLeft); } break; case goRight: vec_flag.pop_back(); vec_flag.push_back(goBack); if(curNode-right ! NULL) { vec_node.push_back(curNode-right); vec_flag.push_back(goLeft); } break; case goBack: cout curNode-data ; vec_flag.pop_back(); vec_node.pop_back(); break; default: break; }//switch-end }//while-end }/* 打印从根到叶子结点之路径 */void PrintPath( const vectorNode * v ) { vector Node *::const_iterator vi; for( vi v.begin(); vi!v.end(); vi ) { Node * n reinterpret_cast Node *(*vi); cout n-data ; } cout endl; }void PrintAllPaths(Node *root) { assert(root ! NULL); vectorNode * vec_node; vectorTag vec_flag; //init vec_node.push_back(root); vec_flag.push_back(goLeft); while( !vec_node.empty()) { Node *curNode vec_node.back(); Tag curFlag vec_flag.back(); switch(curFlag) { case goLeft: vec_flag.pop_back(); vec_flag.push_back(goRight); if(curNode-left ! NULL) { vec_node.push_back(curNode-left); vec_flag.push_back(goLeft); } break; case goRight: vec_flag.pop_back(); vec_flag.push_back(goBack); if(curNode-right ! NULL) { vec_node.push_back(curNode-right); vec_flag.push_back(goLeft); } break; case goBack: if(NULL curNode-left NULL curNode-right) PrintPath(vec_node); vec_flag.pop_back(); vec_node.pop_back(); break; default: break; }//switch-end }//while-end}int main() { Node root, b, c, d, e, f, g, h; root.dataa; root.leftb; root.righte; b.datab; b.leftc; b.rightd; c.datac; c.leftNULL; c.rightNULL; d.datad; d.leftNULL; d.rightNULL; e.datae; e.leftf; e.rightg; f.dataf; f.leftNULL; f.rightNULL; g.datag; g.leftNULL; g.righth; h.datah; h.leftNULL; h.rightNULL; cout Print all paths:\n; PrintAllPaths(root); cout \n; cout PostOrder:\n; PostOrder(root); cout \n; cout PreOrder:\n; PreOrder(root); cout \n; cout InOrder:\n; InOrder(root); cout \n\n; system(PAUSE); return 0; } 运行结果转载于:https://www.cnblogs.com/chio/archive/2007/10/24/935784.html
