二叉树的四种遍历(非递归)迭代打印

最新推荐文章于 2024-04-12 18:08:20 发布

WibleL

最新推荐文章于 2024-04-12 18:08:20 发布

阅读量142

点赞数

分类专栏：二叉树

本文链接：https://blog.csdn.net/speroc/article/details/105288683

版权

二叉树专栏收录该内容

1 篇文章

订阅专栏

本文详细介绍了一种使用栈和队列实现的二叉树迭代遍历方法，包括前序、中序、后序和层次遍历，并提供了一个完整的C++代码示例，展示了如何在二叉树中查找节点和插入新节点。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

#include<iostream>
#include<stack>
#include<queue>
using namespace std;
template<typename Elem>
struct BinNode{
 Elem data;
 BinNode<Elem> *left;
 BinNode<Elem> *right;
 BinNode(Elem x){
  data=x;
  left=right=nullptr;
 }
};
template<typename Elem>
struct SNode
{
 BinNode<Elem> *p;
 int tag;
};
template<class Elem>
class BinTree{
protected:
 BinNode<Elem> *root;
 void rpreprint(BinNode<Elem> *r){//前序迭代遍历打印
  stack<BinNode<Elem>*> st;
  if(!r) return ;
  while(r){
   st.push(r);
   cout<<r->data<<' ';
   r=r->left;
   while(!r&&!st.empty()){
    r=st.top();
    st.pop();//直接弹栈,这个点已经遍历过了,把这个点的右节点遍历完之后,直接回到此点的父结点处
    r=r->right;
   }
  }
 }
 void rinprint(BinNode<Elem> *r){//中序迭代遍历打印
  stack<BinNode<Elem>*> st;
  if(!r) return ;
  while(r){
   st.push(r);
   r=r->left;
   while(!r&&!st.empty()){
    r=st.top();
    st.pop();
    cout<<r->data<<' ';//与前序的区别只有这里
    r=r->right;
   }
  }
 }
 void rpostprint(BinNode<Elem> *r){//后序迭代遍历打印!格外注意后序遍历
  //将父节点最后遍历完后要把临时指针设置为NULL!!!
  //不然你会发现这个场景似曾相似,没错它又会进栈然后搞左节点了
  stack<SNode<Elem>> st;
     BinNode<Elem> * p;//临时指针
     int tag;
     SNode<Elem> sdata;
     p=r;
     while (p||!st.empty()) {
         while (p) {
             //为该结点入栈做准备
             sdata.p=p;
             sdata.tag=0;//由于遍历是左孩子，设置标志位为0
             st.push(sdata);//压栈
             p=p->left;//以该结点为根结点，遍历左孩子
         }
         sdata=st.top();//取栈顶元素
         st.pop();//栈顶元素弹栈
         p=sdata.p;
         tag=sdata.tag;
         //如果tag==0，说明该结点还没有遍历它的右孩子
         if (tag==0) {
             sdata.p=p;
             sdata.tag=1;
             st.push(sdata);//更改该结点的标志位，重新压栈
             p=p->right;//以该结点的右孩子为根结点，重复循环
         }
         //如果取出来的栈顶元素的tag==1，说明此结点左右子树都遍历完了，可以调用操作函数了
         else{
             cout<<p->data<<' ';
             p=NULL;//!!!注意这里要设置为NULL,因为有二次进栈的可能
         }
  }
 }
 void rlevelprint(BinNode<Elem> *r){
  queue<BinNode<Elem>*> qu;
  qu.push(r);
  while(!qu.empty()){
   r=qu.front();
   qu.pop();
   cout<<r->data<<' ';
   if(r->left!=NULL){
    qu.push(r->left);
   }
   if(r->right!=NULL){
    qu.push(r->right);
   }
  }
 }
 BinNode<Elem> *rfind(Elem x,BinNode<Elem> *r){
  if(!r) return NULL;
  if(r->data==x) return r;
  BinNode<Elem> *found;
  found=rfind(x,r->left);
  return found?found:rfind(x,r->right);
 }
public:
 BinTree(){root=nullptr;}
 BinTree(Elem r){root=new BinNode<Elem>(r);}
 // ~BinTree(){}
 void preprint(){rpreprint(root);}
 void inprint(){rinprint(root);}
 void postprint(){rpostprint(root);}
 void levelprint(){rlevelprint(root);}
 BinNode<Elem> *find(Elem x){return rfind(x,root);}
 bool insert(Elem p,Elem x,int LorR){
  BinNode<Elem> *found;
  found=rfind(x,root);
  if(!found) return false;
  if(LorR){
   if(found->right) return false;
   found->right=new BinNode<Elem>(p);
  }else{
   if(found->left) return false;
   found->left=new BinNode<Elem>(p);
  }
  return true;
 }
};
int main(){
 BinTree<int>a(11);
 cout<<a.insert(22,11,0)<<endl;
 cout<<a.insert(33,11,1)<<endl;
 cout<<a.insert(44,22,0)<<endl;
 cout<<a.insert(55,22,1)<<endl;
 cout<<a.insert(66,33,0)<<endl;
 a.preprint();cout<<endl;
 a.inprint();cout<<endl;
 a.postprint();cout<<endl;
 a.levelprint();cout<<endl;
}

后续操作等待更新