二叉树之非递归遍历
1、二叉树的遍历
目前创新互联已为上千的企业提供了网站建设、域名、雅安服务器托管、绵阳服务器托管、企业网站设计、绍兴网站维护等服务,公司将坚持客户导向、应用为本的策略,正道将秉承"和谐、参与、激情"的文化,与客户和合作伙伴齐心协力一起成长,共同发展。
为什么要有遍历操作:将线性结构-------->非线性结构;
将递归程序-------->非递归程序;
2、二叉树的三种递归遍历:
先序遍历:先访问根(父)结点,在访问左分支,最后访问右分支;
中序遍历:先访问左分支,在根结点,最后右分支;
后序遍历:先访问左分支,在访问右分支,最后访问根节点;
所有程序皆正确测试过,后面将给完整程序和测试程序,测试结果。
以下就是递归遍历,先序,中序,后序:
下面的都是在类外定义的函数,所以为模板函数:
//先序遍历 templatevoid BinTree ::prevOrder(BinTreeNode *t)const{ if(t == NULL){ return; }else{ cout< data<<" "; prevOrder(t->leftChild); prevOrder(t->rightChild); } } //中序遍历 template void BinTree ::inOrder(BinTreeNode *t)const{ if(t == NULL){ return; }else{ inOrder(t->leftChild); cout< data<<" "; inOrder(t->rightChild); } } //后序遍历 template void BinTree ::endOrder(BinTreeNode *t)const{ if(t == NULL){ return; }else{ endOrder(t->leftChild); endOrder(t->rightChild); cout< data<<" "; } }
3、二叉树的4种非递归遍历
(1)、深度优先用栈
先序的非递归遍历:栈先入后出,根结点入栈,栈不空,出栈访问,此时将右孩子入栈,在将左孩子入栈,栈不空,出栈访问,就是循环了;
代码如下:
templatevoid BinTree ::prevOrder_1(BinTreeNode * t)const{ stack *> st; //栈里面放的是指向节点的指针 BinTreeNode *tmp; if(t != NULL){ //根不为空 st.push(t); //根入栈 while(!st.empty()){ //栈非空 tmp = st.top(); //读栈顶元素 st.pop(); //出栈 cout< data<<" "; //访问 if(tmp->rightChild){ //右孩子存在 st.push(tmp->rightChild); //入栈 } if(tmp->leftChild){ //左孩子存在 st.push(tmp->leftChild); //入栈 } } } }
中序的非递归遍历:就是先把根及左分支一直压栈,栈不空,出栈访问,再看右孩子,有的话,压栈,结束条件想清楚就行。
代码如下:
templatevoid BinTree ::inOrder_1(BinTreeNode * t)const{ stack *> st; //栈里面放的是指向节点的指针 BinTreeNode *p = t; //用的是do while()循环 do{ while(p != NULL){ //将根和左子树一直入栈 st.push(p); p = p->leftChild; } if(!st.empty()){ //栈不空, p = st.top(); //读栈顶元素 st.pop(); //出栈 cout< data<<" "; //访问 p = p->rightChild; //此时往刚才栈顶元素的右孩子走; } //中序遍历时,当root出栈时,此时栈空,没有p!=NULL的话,将出错。 }while(p != NULL || !st.empty()); //为根的时候右边还要入栈。 }
后序的非递归遍历:思想就是要有一个标志,当为右边回来的时候才能访问根节点!!!
代码如下:
typedef enum{L, R}Tag; //枚举定义新的类型 template//定义一个类,为的是做标志 class stkNode{ public: stkNode(BinTreeNode *p = NULL) : ptr(p), tag(L){} public: //数据成员为公有,便于访问 BinTreeNode *ptr; Tag tag; //L R }; template void BinTree ::endOrder_1(BinTreeNode * t)const{ stkNode n; stack > st; //此时栈中存放的是对象! BinTreeNode *p = t; do{ while(p != NULL){ //不为空,一路向左入栈 n.ptr = p; //将指针给过去 n.tar = L; //记为左边入栈 st.push(n); p = p->leftChild; } bool isRun = true; //是否继续的标志 while(isRun && !st.empty()){ n = st.top(); //读栈顶 st.pop(); //出栈 switch(n.tag){ //根据L和R选择 case L: p = n.ptr; n.tag = R; //更改为R st.push(n); //压入栈 p = p->rightChild; //看有没有右孩子,有的话,结束循环,要入栈的; isRun = false; //特别重要,保证了右孩子的入栈! break; case R: cout< data<<" "; break; } } }while(!st.empty());//不用p1=NULL,因为当栈空时,最后一个节点刚好被访问完成。 }
画图跟踪后序如下:
(2)、广度优先用队列
层次遍历:根结点入队列,队列非空,出队访问,在将左右孩子入队,非空,访问,构成循环;
代码如下:
templatevoid BinTree ::levelOrder(BinTreeNode * t)const{ queue *> qu; //队列里面放的是指向节点的指针 BinTreeNode *p; if(t != NULL){ //根非空 qu.push(t); //根入队 while(!qu.empty()){ //队列非空 p = qu.front(); //读队首 qu.pop(); //出队 cout< data<<" "; //访问 if(p->leftChild){ //左孩子存在 qu.push(p->leftChild); //入队 } if(p->rightChild){ //右孩子存在 qu.push(p->rightChild); //入队 } } } }
网页名称:二叉树之非递归遍历
本文链接:http://myzitong.com/article/jjhjeo.html