首页 > 代码库 > 非递归遍历二叉树【层次遍历，先序、中序、后序遍历】
非递归遍历二叉树【层次遍历，先序、中序、后序遍历】
一、层次遍历：借助队列实现
1 void LevelOrderTraversal(BiTree root) 2 { 3 BiTree e = root;//从根节点开始 4 Queue *q; 5 InitQueue(q); 6 7 if(e)//若根结点非空，则入队列 8 { 9 EnQueue(q,e);10 }11 12 while(!QueueEmpty(q))13 {14 DelQueue(q,e); 15 Visit(e);16 if(e->leftChild)//左孩子不空，入队列 17 {18 EnQueue(q,e->leftChild);19 }20 if(e->rightChild)//右孩子不空，入队列 21 {22 EnQueue(q,e->rightChild);23 }24 } 25 }
二、先序、中序、后序遍历：借助栈实现
（1）先序遍历
void PreorderTranversal(BiTree root){ Stack *s; InitStack(s); //栈底指针 BiTree e = root; //根节点 while(e!=null || !StackEmpty(s)){ while(e!=null){ visit(e)； Push(s,e);//入栈 e= e->leftChild; } if(!StackEmpty(s)){ GetTop(s,e); visit(e); Pop (s,e);//出栈 e =e->rightChild;//在此以右节点为根节点循环以上过程 } }
（2）中序遍历
1 void InorderTranversal(BiTree root){ 2 Stack *s; 3 InitStack(s); //栈底指针 4 BiTree e = root; //根节点 5 while(e!=null || !StackEmpty(s)){ 6 while(e!=null){ 7 Push(s,e);//入栈 8 e= e->leftChild; 9 }10 11 if(!StackEmpty(s)){12 GetTop(s,e);13 visit(e);14 Pop (s,e);//出栈 15 e =e->rightChild;//在此以右节点为根节点循环以上过程16 }17 }（3）后序遍历
1 typedef struct AssistNode{ 2 BiTree bi; 3 int isFirst= false;//表示是第一次还是第二次出栈 4 }*Assist; 5 6 void PostorderTranversal(BiTree root){ 7 //此处Stack结构中的元素为Assist类型 8 Stack *s; 9 InitStack(s); //栈底指针10 BiTree e = root; //根节点11 while(e!=null || !StackEmpty(s)){12 while(e!=null){13 Assist assist=(Assist*)malloc(sizeof(Assist));14 //将e封装到assist里面并加标记15 assist->bi= e;16 assist->isFirst= true;17 Push(s,assist);//入栈18 e= e->leftChild;19 }20 21 if(!StackEmpty(s)){22 GetTop(s,assist);23 Pop (s,assist);//出栈24 if(assist->isFirst=true){25 //如果是第一次取出，则以该节点作为根节点循环26 assist->isFirst=false;27 Push(s,assist);28 e=assist->bi->rightChild;29 }else{30 //如果是第二次取出，则访问，并在下个循环中向上一级访问（取出的新的节点为其父节点）31 visit(assist->bi);32 e=null;33 }34 }35 }
非递归遍历二叉树【层次遍历，先序、中序、后序遍历】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。