bitree.cpp

这里面有很多经典的算法

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

#include "stdafx.h"
#include "iostream.h"
struct node{
	int data;
	node * lchild,*rchild;
};
typedef struct nodee{
	node * vec[100];
	int f,r;
}quenen;

quenen q,q1;
int A[10000];
node *B[10000];
node *root;
void translevel(node *b);
void changecapital (node *t);
int F(int num)
{
	int temp=num;
	while(temp)
	{
		if(temp==1)
			return 1;
		if(temp%2)
			return 0;
		temp=temp/2;
	}
}                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                


void PrintTreeP(node * r)
{
	if(!r)
		return;
	cout<<r->data ;
	PrintTreeP(r->lchild );
	PrintTreeP(r->rchild );
}

void PrintTreeM(node * r)
{
	if(!r)
		return;
	
	PrintTreeM(r->lchild );
	cout<<r->data ;
	PrintTreeM(r->rchild );
}

void PrintTreeL(node * r)
{
	if(!r)
		return;
	
	PrintTreeL(r->lchild );	
	PrintTreeL(r->rchild );
	cout<<r->data ;
}

int main(int argc, char* argv[])
{
	root=NULL;
	int idx=4;
	cout<<"please input datas:"<<endl;
	while(!F(idx-2+1))
	{
		idx=1;
		while(idx++)
		{
			cin>>A[idx-2];
			if(A[idx-2]==-10000)
				break;
		}
		if(!F(idx-2+1))
		cout<<"input error,please input again:"<<endl;

	}

	
	if(idx<=2)
	{
		cout<<"Tree is null"<<endl;
		return 0;
	}

	B[0]=new node;
	B[0]->data =A[0];
	B[0]->lchild =NULL;
	B[0]->rchild =NULL;
	for(int i=0;i<idx-2;i++)
	{
		if(2*i+1>=idx-2)
			break;
		B[2*i+1]=new node;//建左子
	    B[2*i+1]->data =A[2*i+1];
	    B[2*i+1]->lchild =NULL;
	    B[2*i+1]->rchild =NULL;
        
	    B[2*i+2]=new node;//建右子
	    B[2*i+2]->data =A[2*i+2];
	    B[2*i+2]->lchild =NULL;
	    B[2*i+2]->rchild =NULL;
  
	    B[i]->lchild =B[2*i+1];
	    B[i]->rchild =B[2*i+2];

	}

	root=B[0];
	translevel(root);//二叉树层次遍历
	cout<<endl;
	PrintTreeP(root);//二叉树先根遍历
	cout<<endl;
	PrintTreeM(root);//二叉树中根遍历
	cout<<endl;
	PrintTreeL(root);//二叉树后根遍历
	cout<<endl;
	//changecapital (root);//二叉树改变大小写
	
	return 0;
}

void translevel(node *b)
{
	q.f=0;
	q.r=0;
	q1.f=0;
	q1.r=0;
	if(b)
		cout<<b->data<<" " ;
	cout<<endl;
	q.vec[q.r]=b;
	q.r=q.r+1;
	while(q.f <q.r || q1.f <q1.r)
	{
		while(q.f<q.r)
		{
			b=q.vec[q.f];
		    q.f=q.f+1;
		    if(b->lchild)
			{
				cout<<b->lchild->data <<" ";
			    q1.vec [q1.r]=b->lchild ;
			    q1.r=q1.r+1;
			}
			if(b->rchild)
			{
				cout<<b->rchild->data <<" ";
			    q1.vec [q1.r]=b->rchild ;
			    q1.r=q1.r+1;
			}
			cout<<endl;
		}
		
		while(q1.f<q1.r)
		{
			b=q1.vec[q1.f];
		    q1.f=q1.f+1;
		    if(b->lchild)
			{
				cout<<b->lchild->data <<" ";
			    q.vec [q.r]=b->lchild ;
			    q.r=q.r+1;
			}
			if(b->rchild)
			{
				cout<<b->rchild->data <<" ";
			    q.vec [q.r]=b->rchild ;
			    q.r=q.r+1;
			}			
		}

	  cout<<endl;
	}

}

void changecapital (node * t)
{//改变大小写
	if(!t)		
        return;
    if(t->data>='a'&&t->data<='z')
       t->data=t->data-32;
       cout<<t->data<<" ";
       changecapital(t->lchild );
       changecapital(t->rchild );
}