二叉树的中序遍历--------零基础学数据结构讲座(2)

二叉树的中序遍历的递归定义如下：

如果二叉树为空，则执行空操作。如果二叉树非空，则执行以下操作：

（1）中序遍历左子树。

（2）访问根结点。

（3）中序遍历右子树。

<shapetype id="_x0000_t75" stroked="f" filled="f" path="m@4@5l@4@11@9@11@9@5xe" o:preferrelative="t" o:spt="75" coordsize="21600,21600"><stroke joinstyle="miter"></stroke><formulas><f eqn="if lineDrawn pixelLineWidth 0"></f><f eqn="sum @0 1 0"></f><f eqn="sum 0 0 @1"></f><f eqn="prod @2 1 2"></f><f eqn="prod @3 21600 pixelWidth"></f><f eqn="prod @3 21600 pixelHeight"></f><f eqn="sum @0 0 1"></f><f eqn="prod @6 1 2"></f><f eqn="prod @7 21600 pixelWidth"></f><f eqn="sum @8 21600 0"></f><f eqn="prod @7 21600 pixelHeight"></f><f eqn="sum @10 21600 0"></f></formulas><path o:connecttype="rect" gradientshapeok="t" o:extrusionok="f"></path><lock aspectratio="t" v:ext="edit"></lock></shapetype><shape id="_x0000_i1025" o:ole="" type="#_x0000_t75" style="width: 115.5pt; height: 102.75pt"><imagedata o:title="" src="file:///C:/DOCUME~1/user/LOCALS~1/Temp/msohtml1/01/clip_image001.emz"></imagedata></shape>

二叉树的中序遍历非递归算法实现如下。

void InOrderTraverse(BiTree T)

/*中序遍历二叉树的非递归实现*/

{

BiTree stack[MaxSize]; /*定义一个栈，用于存放结点的指针*/

int top; /*定义栈顶指针*/

BitNode *p; /*定义一个结点的指针*/

top=0; /*初始化栈*/

p=T;

while(p!=NULL||top>0)

{

while(p!=NULL) /*如果p不空，访问根结点，遍历左子树*/

{

stack[top++]=p; /*将p入栈*/

p=p->lchild; /*遍历左子树*/

}

if(top>0) /*如果栈不空*/

{

p=stack[--top]; /*栈顶元素出栈*/

printf(“%<chmetcnv w:st="on" tcsc="0" numbertype="1" negative="False" hasspace="False" sourcevalue="2" unitname="C">2c</chmetcnv>”,p->data); /*访问根结点*/

p=p->rchild; /*遍历右子树*/

}

}

}