1.cpp

面向对象的c++数据结构关于数组的处理及变通

#include "stdio.h" 
#include "stdlib.h" 
#include "string.h" 
#define null 0 

struct node 
{ 
char data; 
struct node *lchild; 
struct node *rchild; 
}; 

//先序，中序 建树 
struct node *create(char *pre,char *ord,int n) //n记录树的结点个数
{ 
	struct node * head; 
	int ordsit; 
	
	head=null; 
	if(n<=0) 
	{ 
		return null; 
	} 
	else 
	{ 
		head=(struct node *)malloc(sizeof(struct node)); 
		head->data=*pre; 
		head->lchild=head->rchild=null; 
		ordsit=0; 
		while(ord[ordsit]!=*pre) 
		{ 
			ordsit++; 
		} 
		head->lchild=create(pre+1,ord,ordsit); 
		head->rchild=create (pre+ordsit+1,ord+ordsit+1,n-ordsit-1); 
		return head; 
	} 
} 


//中序递归遍历 
void inorder(struct node *head) 
{ 
	if(!head) 
		return; 
	else 
	{ 
		inorder(head->lchild ); 
		printf("%c",head->data ); 
		inorder(head->rchild ); 
	} 
} 



//中序非递归遍历 

void inorder1(struct node *head) 
{ 
	struct node *p; 
	struct node *stack[20]; 
	int top=0; 
	
	p=head; 
	while(p||top!=0) 
	{ 
		while (p) 
		{ 
			stack[top++]=p; 
			p=p->lchild ; 
		} 
		p=stack[--top]; 
		printf("%c ",p->data ); 
		p=p->rchild ; 
	} 
} 


//主函数 
int main() 
{ 
	struct node * head; 
	char pre[30],ord[30]; 
//	pre[30] = {'-','+','a','*','b','%','c','d','/','e','f' };
	//ord[30] = "a+b*c%d-e/f ";
	int n; 
	
	gets(pre); 
	gets(ord); 
	n=strlen(pre); 
	head=create(pre,ord,n); 
	inorder(head); 
	printf("\n"); 
	inorder1(head); 
	printf("\n"); 
}