tree1_inordert.cpp

是一本教程的实例代码,可以下载后直接运行,即可以得到答案.

#include "Tree1.h"                     //二叉树类
#include "Stack2.h"                    //链式栈类，模板

void inorderT(Tree1 &t1)               //二叉树中根次序遍历的非递归算法
{
    cout<<"中序遍历二叉树:  ";   
    Stack2<TreeNode1*> s2;             //创建空栈，数据元素是指向二叉树结点的指针
    TreeNode1 *p=t1.root;
    while(p!=NULL || !s2.isEmpty())    //p非空或栈非空时
       if(p!=NULL)
       {
            s2.push(p);                //p结点入栈
            p=p->left;                 //进入左子树
       }
       else                            //p为空且栈非空时
       {
            p=s2.pop();                //出栈的结点由p指向
            cout<<p->data<<"  ";       //访问结点
            p=p->right;                //进入右子树
       }
    cout<<endl;   
}    

void main()
{
    char *str="ABD.G...CE..FH...";     //标明空子树的先根次序
    cout<<"The Tree: "<<str<<endl;
    Tree1 t1(str);
    inorderT(t1);
}
/*
程序运行结果如下：
The Tree: ABD.G...CE..FH...
中序遍历二叉树:  D  G  B  A  E  C  H  F  
撤销二叉树: G D B E H F C A 
*/