DIY 二叉树的先序非递归遍历 Dear 丶 2022-08-10 05:49 120阅读 0赞 DIY 二叉树的先序非递归遍历 **在实现二叉树的非递归遍历的过程中，需要用到一个栈和一个队列；** **定义一个bool型常量ok = true;当ok为true是，进入循环，定义指针p，指向根节点；** **判断p有几个孩子 \{** ** 如果有两个孩子，则入队；** ** 入栈；** ** 如果有一个孩子，判断是左孩子还是右孩子 \{** ** 如果是左孩子 p 指向它的左孩子；** ** 如果是右孩子 p 指向它的右孩子；** ** \}** ** 如果没有孩子，判断是否栈空\{** ** 如果栈不空，取栈顶，p指向栈顶元素的右孩子；** ** 如果栈空，ok = false；** ** \}** **\}** **然后把队列中的元素输出，即得到的就是二叉树的先序** void PreambleTraverse(LinkTree T) { //T指向树的根节点 stack <LinkTree> S; queue <LinkTree> Q; LinkTree p = T; LinkTree q; bool ok = true; while(ok) { if(p -> L && p -> R) S.push(p); Q.push(p); if(p -> L) p = p -> L; else if(p -> R) p = p -> R; else { if(!S.empty()){ q = S.top(); p = q -> R; S.pop(); } else ok = false; } } while(!Q.empty()) { q = Q.front(); Q.pop(); cout << q -> data; } cout << endl; }
还没有评论，来说两句吧...