📄 6_6.htm
字号:
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=gb_2312-80">
<META NAME="Generator" CONTENT="Microsoft Word 97">
<TITLE>第 2 章 线性表</TITLE>
</HEAD>
<BODY>
<B><FONT SIZE=3><P ALIGN="JUSTIFY">6. </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>后序遍历二叉树的非递归算法</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> typedef struct </B>Data<B> {	</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>					</B></FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>顺序栈中数据的结构定义</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> BiTNode 	*p;		</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>						</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>二叉树的结点指针</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> <B>int</B> 		tag;	 	</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>						</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>标志变量</P>
<P ALIGN="JUSTIFY">	</FONT><FONT SIZE=3> // </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>当</FONT><FONT SIZE=3> tag = 0 </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>时，表示该结点第一次入栈，暂不访问；</P>
<P ALIGN="JUSTIFY">	</FONT><FONT SIZE=3> // </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>当</FONT><FONT SIZE=3> tag = 1 </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>时，表示该结点第二次入栈，可以访问。</P>
</FONT><B><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>}</B></FONT><FONT SIZE=3> Data, <B>SElemType</B>;		</P>
<B><P ALIGN="JUSTIFY"> Status</B> PostOrderTraverse ( BiTree T, <B>Status </B>( *Visit ) ( TElemType e ) ) </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>{</P>
</B></FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> // </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>采用二叉链表存储结构，</FONT><FONT SIZE=3>Visit </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>是对数据元素操作的应用函数。</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> // </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>后序遍历二叉树</FONT><FONT SIZE=3> <I>T</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>的非递归算法，对每个数据元素调用函数</FONT><FONT SIZE=3> Visit</P>
<P ALIGN="JUSTIFY"> InitStack (S);</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>								</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>使用栈</FONT><FONT SIZE=3> <I>S</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>存放待访问的根结点</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> Data.p = T; </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> 							// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>令</FONT><FONT SIZE=3> <I>Data.</I>p </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>指向二叉树根结点</P>
</FONT><B><FONT SIZE=3><P ALIGN="JUSTIFY"> Do {</P>
</B><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><B><FONT SIZE=3>if</B> ( Data.p ) </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>{</B>				</FONT><FONT SIZE=3> 			 	// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>如果</FONT><FONT SIZE=3> <I>Data.</I>p </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>非空</P>
<P ALIGN="JUSTIFY">		</FONT><FONT SIZE=3> Data.tag = 0;		</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>				</FONT><FONT SIZE=3> 	// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>将</FONT><FONT SIZE=3> <I>Data.</I>tag </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>置零</P>
<P ALIGN="JUSTIFY">		</FONT><FONT SIZE=3> Push ( S, Data );	</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> 					// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>将</FONT><FONT SIZE=3> <I>Data.</I>tag </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>和</FONT><FONT SIZE=3> <I>Data.</I>p </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>一道送入栈</FONT><FONT SIZE=3> <I>S</I> </P>
<P ALIGN="JUSTIFY">	</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> Data.p = Data.p->lchild;	 		 		// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>将指针指向左子树根结点，遍历左子树</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	<B>}</FONT><FONT SIZE=3> </B>// if </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>结束</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><B><FONT SIZE=3>else {</B></FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>								</FONT><FONT SIZE=3> 	// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>如果</FONT><FONT SIZE=3> <I>Data.</I>p </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>为空</P>
<P ALIGN="JUSTIFY">		</FONT><FONT SIZE=3> Pop ( S, Data );	</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>		</FONT><FONT SIZE=3> 				// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>将</FONT><FONT SIZE=3> <I>Data.</I>tag </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>和</FONT><FONT SIZE=3> <I>Data.</I>p </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>一道弹出</P>
<P ALIGN="JUSTIFY">		</FONT><FONT SIZE=3> <B>if</B> ( Data.tag = 0 ) </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>{</B>	</FONT><FONT SIZE=3> 					// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>如果标志变量</FONT><FONT SIZE=3> <I>Data.</I>tag </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>为零</P>
<P ALIGN="JUSTIFY">	</FONT><FONT SIZE=3> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> 	Data.tag = 1;</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>			</FONT><FONT SIZE=3> 				// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>将</FONT><FONT SIZE=3> <I>Data.</I>tag </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>置为</FONT><FONT SIZE=3> 1</P>
<P ALIGN="JUSTIFY">	 </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> 	Push ( S, Data );	 					// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>将</FONT><FONT SIZE=3> <I>Data.</I>tag </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>和</FONT><FONT SIZE=3> <I>Data.</I>p </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>一道送入栈</FONT><FONT SIZE=3> <I>S</I> </P>
<P ALIGN="JUSTIFY">	 </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> 	Data.p = Data.p->rchild; 					// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>将指针指向右子树根结点，遍历右子树</P>
<P ALIGN="JUSTIFY">		</FONT><FONT SIZE=3> </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>}</B></FONT><FONT SIZE=3> // if </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>结束</P>
<P ALIGN="JUSTIFY">		</FONT><FONT SIZE=3> <B>else {</B></FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>					</FONT><FONT SIZE=3> 				// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>如果标志变量</FONT><FONT SIZE=3> <I>Data.</I>tag </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>为</FONT><FONT SIZE=3> 1</P>
<P ALIGN="JUSTIFY">	 </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>		</FONT><FONT SIZE=3>Visit ( Data.p );	 </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> 				// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>访问</FONT><FONT SIZE=3> <I>Data.</I>p </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>指向的结点</P>
<P ALIGN="JUSTIFY">	</FONT><FONT SIZE=3> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>		</FONT><FONT SIZE=3>Data.p = NULL;	 </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> 				// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>将</FONT><FONT SIZE=3> <I>Data.</I>p </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>指针置空</P>
<P ALIGN="JUSTIFY">		</FONT><FONT SIZE=3> </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>}</B></FONT><FONT SIZE=3> // else </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>结束</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	<B>}</B></FONT><FONT SIZE=3> // else </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>结束</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>}</FONT><FONT SIZE=3> while</B> ( <B>!</B> Data.p <B>||</B> StackEmpty (S) )</P>
<P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> <B>return</B> OK;</P>
</FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3><P ALIGN="JUSTIFY">}</B></FONT><FONT SIZE=3> // PostOrderTraverse</P></FONT></BODY>
</HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -