newp197.cpp

来自「数据结构的一些教程....比较适于初学者」· C++ 代码 · 共 41 行

//二叉树中序遍历游标模板为BiTrInIterator<T>的测试程序(P.196~197)
#include "BiTreeNode.h"
#include "BiTreeExample.h"
#include "LinStack.h"

void main(void)
{
	BiTreeNode<char> *root,*current;
	MakeCharTree(root,2);  //建立2号二叉树：图7-11(a)的二叉树(P.173)
	LinStack<BiTreeNode<char>* > s; 
	cout<<"中序遍历序列为:"<<endl;
	if(root==NULL) return;
	current=root;
	while(current->Left()!=NULL)
	{  
		s.Push(current);         //未到达最左子孙结点指针入栈
		current=current->Left();     //继续向左子树前进
	}   //返回最左子孙结点current(无左孩子但可能有右孩子)指针
    cout<<current->GetData()<<" ";
    bool iteComplete=true;
	while(iteComplete)
	{
		if(current->Right()!=NULL)
		{
          current=current->Right();
	      while(current->Left()!=NULL)
		  {  
		   s.Push(current);         //未到达最左子孙结点指针入栈
		   current=current->Left();     //继续向左子树前进
		  }   //返回最左子孙结点current(无左孩子但可能有右孩子)指针
          cout<<current->GetData()<<" ";
		}  //求右子树的最左子孙结点指针
		if(!s.StackEmpty())
		{
			current=s.Pop();  //退栈作为当前结点指针
            cout<<current->GetData()<<" ";
		}
		else iteComplete=false;
	}
}