递归后根遍历.cpp

2元树的先根遍历算法

#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
#define MAX 100

struct node{
	struct node * lchild;
	struct node * rchild;
	int data;
};
typedef struct node *BTREE;
typedef node * tree;

//void EMPTY(tree T); //建立一个空树
//void CREATEBT (char v, tree* LT , tree* RT);//建立一株新2元树

BTREE CREATBT();
void POSTORDER(tree T ); //后根遍历
//void INORDER  (BTREE BT); //中根遍历

//void PREORDER (BTREE BT); //先根遍历
//void LCHILD(BTREE BT);//返回左儿子，若无则返回空
//void RCHILD(BTREE BT);//返回右儿子，若无则返回空
//void DATA (BTREE BT);//返回2元树T根节点的数据域的值
//void ISEMPTY (BTREE T);//判断2元树T是否为空

void main ()
{
	BTREE BT;
	BT=CREATBT();
	POSTORDER(BT);
}

BTREE CREATBT()
{
	struct node * s[MAX];

	int i ,j ;
	int ch;
	struct node *bt,*p;
	cin>>i>>ch;
	while(i!=0&&ch!=0)
	{
		p=(BTREE)malloc(sizeof(BTREE));
		p->data=ch;
		p->lchild=NULL;
		p->rchild=NULL;
		s[i]=p;
		if(i==1)
			bt=p;
		else
		{
			j=i/2; //父节点的编号
			if(i%2==0)
				s[j]->lchild=p; //i是j的左儿子
			else
				s[j]->rchild=p; //i是j的右儿子
		}
		cin>>i>>ch;
	}
	return bt;
}
/*void PREORDER (BTREE BT)
{
	if(BT!=NULL)
	{
		printf("%d",BT->data);
		PREORDER(BT->lchild);
		PREORDER(BT->rchild);
	}
}
*/

/*void INORDER  (BTREE BT)
{
	if(BT!=NULL)
	{
		INORDER(BT->lchild);
		printf("%d",BT->data);
		INORDER(BT->rchild);
	}
}*/
void POSTORDER(BTREE BT )
{
	if(BT!=NULL)
	{
		POSTORDER(BT->lchild);
		POSTORDER(BT->rchild);
		printf("%d",BT->data);
	}
}