您的位置:时时彩走势图 > 重庆时时五星彩走势图-服务器运维 > 如果只在栈中保留指向结点的指针

如果只在栈中保留指向结点的指针

2020-05-06 16:55

前序、中序、后序的非递归遍历中,要数后序最为艰难,如若只在栈中保留指向结点的指针,那是非常不够的,必需有局地十二分的新闻寄放在栈中。方法有许多,这里只举一种,先定义栈结点的数据结构

复制代码 代码如下:typedef struct{Node * p; int rvisited;}SNode //Node 是二叉树的结点结构,rvisited==1象征p所指向的结点的右结点已被访问过。

lastOrderTraverse{ //首先,从根节点最初,往左下方走,向来走到头,将路线上的每四个结点入栈。 p = bt; while; //push到栈中三个信息,一是结点指针,一是其右结点是还是不是被访谈过 bt = bt.lchild; }

//然后跻身循环体 while{ //只要栈非空 sn = Stack.getTop(卡塔尔; // sn是栈顶结点

//注意,自便三个结点N,只要她有左孩子,则在N入栈之后,N的左孩子必然也随着入栈了,所以当大家获得栈顶成分的时候,能够确信这几个成分要么未有左孩子,要么其左孩子已经被访问过,所以这时我们就不关切它的左孩子了,大家只关注其右孩子。

//若其右孩子曾经被访谈过,或是该因素没有右孩子,则由后序遍历的定义,那时得以visit那个结点了。 if(!sn.p.rchild || sn.rvisited卡塔尔(قطر‎{ p = pop; } else //若它的右孩子存在且rvisited为0,表明以前还尚无动过它的右孩子,于是就去管理一下其右孩子。 { //那个时候我们要从其右孩子结点开首一贯往左下方走,直至走到尽头,将这条路线上的保有结点都入栈。

//当然,入栈从前要先将该结点的rvisited设成1,因为其右孩子的入栈意味着它的右孩子确定先于它被访谈(那很好精通,因为大家总是从栈顶抽取成分来举办visitState of Qatar。因而可以预知,下一遍该因素再处于栈顶时,其右孩子确定已被visit过了,所以这里能够将rvisited设置为1。 sn.rvisited = 1;

//往左下方走到尽头,将路线上有着因素入栈 p = sn.p.rchild; while; p = p.lchild; } }//这一轮循环已终止,刚刚入栈的这么些结点我们没有必要管它了,下一轮循环会将那个结点照管的很好。 }}

本文由时时彩走势图发布于重庆时时五星彩走势图-服务器运维,转载请注明出处:如果只在栈中保留指向结点的指针

关键词: