ds6_92.cpp

这是清华大学出版社的《数据结构》的电子文档讲义

// ds6_92.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "tree.h"

template<class Type> void lrChange(binaryTree<Type>& t, int max){
	binTreeNode<Type>* ptr=t.getRoot();
	binTreeNode<Type>* temp;
	stackArray<binTreeNode<Type>*> sp(max);
	if(ptr!=0) {
		sp.push(ptr);
		while(!sp.isEmpty()){
			ptr=sp.pop();
			if(t.leftChild(ptr)!=0 || t.rightChild(ptr)!=0){
				temp=t.leftChild(ptr);
				(*ptr).setLeft(t.rightChild(ptr));
				(*ptr).setRight(temp);
				}
			if(t.leftChild(ptr)!=0)sp.push(t.leftChild(ptr));
			if(t.rightChild(ptr)!=0)sp.push(t.rightChild(ptr));
			}
		}
	}

int main(int argc, char* argv[])
{
	int j;
	int c[10]={11,2,29,5,15,4,26,8,32,13};
	binaryTree<int> tr1(0);
	for(int i=0; i<10; i++){	
//		cin>>j;					//键盘输入：11,2,29,5,15,4,26,8,32,13
		j=c[i];
		tr1.insert(j);			//按左小右大插入树tr1
		}
	cout<<tr1;					//前序输出：11,2,5,4,8,29,15,13,26,32
	lrChange<int>(tr1,12);		//左右交换成为倒序树
	cout<<tr1;					//前序输出：11,29,32,15,26,13,2,5,8,4
	
	cout<<"前序输出:";
	preOrder<int>preor(tr1);
	for(preor.first(); +preor; ++preor)
		cout<<preor()<<", ";
	cout<<endl;
	cout<<"中序输出:";			//32,29,26,15,13,11,8,5,4,2
	inOrder<int>inor(tr1);
	for(inor.first(); +inor; ++inor)
		cout<<inor()<<", ";
	cout<<endl;
	cout<<"后序输出:";			//32,26,13,15,29,8,4,5,2,11
	postOrder<int>postor(tr1);
	for(postor.first(); +postor; ++postor)
		cout<<postor()<<", ";
	cout<<endl;

	cout<<"层次输出:";			//32,26,13,15,29,8,4,5,2,11
	levelOrder<int>levelor(tr1);
	for(levelor.first(); +levelor; ++levelor)
		cout<<levelor()<<", ";
	cout<<endl;

	return 0;
}