数据结构之树
定义                                                                      
    树是一种数据结构，它是由n（n>=1）个有限结点组成一个具有层次关系的集合
应用:
    文件夹的分类创建与快速查找

#include<stdio.h>
#include<malloc.h>
#include<graphics.h> 
#include<string.h>
#define MaxSize 100
typedef char ElemType;
typedef struct node{
	 ElemType data;
	 int x,y,ltag,rtag,pathlen;
	 struct node *lchild;
	 struct node *rchild;
}BTNode;

BTNode *CreateBTNode();
int BTNodeDepth(BTNode *);
void DispBTNode(BTNode *);
void PreOrder(BTNode *);
void InOrder(BTNode *);
void PostOrder(BTNode *);
void LevelOrder(BTNode *);
void LeafNodes(BTNode *);
void FindNodes(BTNode *,ElemType);
void PathLeaf(BTNode *,BTNode *,int);
void InitPreOrderThread(BTNode *);
BTNode *CreatePreOrderThread(BTNode *);
void PreOrderThread(BTNode *);
void InitInOrderThread(BTNode *);
BTNode *CreateInOrderThread(BTNode *);
void InOrderThread(BTNode *);
void InitPostOrderThread(BTNode *);
BTNode *CreatePostOrderThread(BTNode *);
void PostOrderThread(BTNode *);
void DestroyBTNode(BTNode *);
void DeleteNode(BTNode *,ElemType,BTNode *[],int);
void InsertNode(BTNode *,ElemType,ElemType,ElemType);

BTNode *pre;
int s = 0;
int main(){
	BTNode *b;
	int a;
	b=NULL;
	b=CreateBTNode();
	a = BTNodeDepth(b);
	if(a>5){
		printf("The hight of btree can not over 5");
		return 0;
	}
	return 0;
}
BTNode *CreateBTNode(){
	 BTNode *b=NULL,*p=NULL;
	 FILE *fp;
	 char str[MaxSize],ch;
	 BTNode *st[MaxSize];
	 int j,k,i = -1,x=0;
	 fp = fopen("tree.txt","r");
	 while(!feof(fp)){
		str[x]=fgetc(fp);
		x++;
	}
	 for(j=0;str[j];j++){
		 ch = str[j];
		 switch(ch){
			 case '(':i++;st[i] = p;k = 1;break;
			 case ',':k = 2;break;
			 case ')':i--;break;
			 case ' ':break;
			 default:	
				p = (BTNode *)malloc(sizeof(BTNode));
				p->data = ch;
				p->lchild = p->rchild = NULL;
				p->x = p->y = 0;
				p->ltag = p->rtag = 0;
				if(b==NULL)
					b = p;
				else{
					switch(k){
						case 1:st[i]->lchild = p;break;
						case 2:st[i]->rchild = p;break;
					}
				}
		 }
	 }
	 return b;
}
int BTNodeDepth(BTNode *b){
	int lchilddep,rchilddep;
	if(b==NULL)
		return 0;
	else{
		lchilddep = BTNodeDepth(b->lchild);
		rchilddep = BTNodeDepth(b->rchild);
		return (lchilddep>rchilddep)?(lchilddep+1):(rchilddep+1);
	}
	
}
void DispBTNode(BTNode *b){
	if(b!=NULL){
		printf("%c",b->data);
		if(b->lchild!=NULL||b->rchild!=NULL){
			printf("(");
			DispBTNode(b->lchild);
			if(b->rchild!=NULL)
				printf(",");
			DispBTNode(b->rchild);
			printf(")");
		}
	}
}
void PreOrder(BTNode *b){
	if(b!=NULL){
		circlegraph(b,2,4);
		delay(900000000);
		circlegraph(b,1,4);
		PreOrder(b->lchild);
		PreOrder(b->rchild);
	}
}
void InOrder(BTNode *b){
	if(b!=NULL){
		InOrder(b->lchild);
		circlegraph(b,2,4);
		delay(900000000);
		circlegraph(b,1,4);
		InOrder(b->rchild);
	}
}
void PostOrder(BTNode *b){
	if(b!=NULL){
		PostOrder(b->lchild);
		PostOrder(b->rchild);
		circlegraph(b,2,4);
		delay(900000000);
		circlegraph(b,1,4);
	}
}
void LevelOrder(BTNode *b){
	BTNode *Qu[MaxSize];
	int front,rear;
	front = rear = 0;
	if(b!=NULL){
		circlegraph(b,2,4);
		delay(900000000);
		circlegraph(b,1,4);
		rear++;
		Qu[rear]=b;
		while(rear!=front){
			front++;
			b=Qu[front];
			if(b->lchild!=NULL){
				circlegraph(b->lchild,2,4);
				delay(900000000);
				circlegraph(b->lchild,1,4);
				rear++;
				Qu[rear]=b->lchild;
			}
			if(b->rchild!=NULL){
				circlegraph(b->rchild,2,4);
				delay(900000000);
				circlegraph(b->rchild,1,4);
				rear++;
				Qu[rear]=b->rchild;
			}
		}
	}
}
void DeleteNode(BTNode *b,ElemType c,BTNode *path[],int pathlen){
	if(b!=NULL){
		if(b->data==c){
			if(path[pathlen-1]->lchild->data==c)
				path[pathlen-1]->lchild = NULL;
			if(path[pathlen-1]->rchild->data==c)
				path[pathlen-1]->rchild = NULL;
			DestroyBTNode(b);
		}
		if(b->lchild!=NULL||b->rchild!=NULL){
			path[pathlen]=b;
			pathlen++;
			DeleteNode(b->lchild,c,path,pathlen);
			DeleteNode(b->rchild,c,path,pathlen);
			pathlen--;
		}
	}
}
void DestroyBTNode(BTNode *b){
	if(b!=NULL){
		DestroyBTNode(b->lchild);
		DestroyBTNode(b->rchild);
		free(b);
	}
}
void InsertNode(BTNode *b,ElemType node,ElemType location,ElemType direction){
	if(b!=NULL){
		BTNode *p;
		BTNode *p1;
		if(b->data == location){
			if(direction == 'l'||direction == 'L'){
				if(b->lchild!=NULL){
					p1 = b->lchild;
				}else
					p1 = NULL;
				p = (BTNode *)malloc(sizeof(BTNode));
				p->data = node;
				p->lchild = p->rchild = NULL;
				p->x = p->y = 0;
				p->ltag = p->rtag = 0;
				b->lchild = p;
				p->lchild = p1;
			}
			if(direction == 'r'||direction == 'R'){
				if(b->rchild!=NULL){
					p1 = b->lchild;
				}else
					p1 = NULL;
				p = (BTNode *)malloc(sizeof(BTNode));
				p->data = node;
				p->lchild = p->rchild = NULL;
				p->x = p->y = 0;
				p->ltag = p->rtag = 0;
				b->rchild = p;
				p->rchild = p1;
			}
		}
		if(b->lchild!=NULL||b->rchild!=NULL){
			InsertNode(b->lchild,node,location,direction);
			InsertNode(b->rchild,node,location,direction);
		}
	}
}
void LeafNodes(BTNode *b){
	if(b!=NULL){
		if(b->lchild==NULL&&b->rchild==NULL){
			circlegraph(b,2,4);
			delay(900000000);
		}
		else{
			LeafNodes(b->lchild);
			LeafNodes(b->rchild);
		}
	}
}
void FindNodes(BTNode *b,ElemType a){
	if(b!=NULL){
		if(b->data == a){
			circlegraph(b,YELLOW,BLACK);
			delay(900000000000000);
		}else{
			circlegraph(b,GREEN,RED);
			delay(90000000);
			circlegraph(b,1,4);
		}
		if(b->lchild!=NULL||b->rchild!=NULL){
			FindNodes(b->lchild,a);
			FindNodes(b->rchild,a);
		}
	}
}
/*节点到根节点的路径长度函数,b 为根节点,c 为当前节点,pathlen 为路径长度*/
void PathLeaf(BTNode *b,BTNode *c,int pathlen){
	if(b!=NULL){
		if(b->lchild!=NULL||b->rchild!=NULL){
			pathlen++;
			PathLeaf(b->lchild,c,pathlen);
			PathLeaf(b->rchild,c,pathlen);
			pathlen--;
		}
		if(b==c){
			c->pathlen = pathlen+1;
		}
	}
}
/*对二叉树P进行先序线索化*/
void InitPreOrderThread(BTNode *p){
	if(p!=NULL){ 
		InitPreOrderThread(p->rchild);
		InitPreOrderThread(p->lchild);
		if(p->lchild==NULL){
			p->lchild = pre;
			p->ltag = 1;
		}else
			p->ltag = 0;
		if(pre ->rchild==NULL){
			pre->rchild = p;
			pre->rtag = 1;
		}else
			pre->rtag = 0;
		pre = p;
	}
}
/*先序线索化二叉树*/
BTNode *CreatePreOrderThread(BTNode *b){
	BTNode *root;
	root = (BTNode *)malloc(sizeof(BTNode));
	if(!root){
		return root;
	}
	root->ltag = 0;
	root->rtag = 1;
	root->rchild = b;
	if(b==NULL){
		root->lchild = root;
	}else{
		root->lchild = b;
		pre = root;
		InitPreOrderThread(b);
		pre->rchild = root;
		pre->rtag = 1;
		root->rchild = pre;
	}
	return root;
}
/*先序线索化二叉树tb实现先序遍历*/
void PreOrderThread(BTNode *root){
	BTNode *b = root->lchild;
	while(b!=root){
		preorderthread_line_graph(b,root,GREEN,3);
		delay(900000000000000);
		b = b->lchild;
	}
}
/*对二叉树P进行中序线索化*/
void InitInOrderThread(BTNode *p){
	if(p!=NULL){ 
		InitInOrderThread(p->lchild);
		if(p->lchild==NULL){
			p->lchild = pre;
			p->ltag   = 1;
		}else
			p->ltag = 0;
		if(pre ->rchild==NULL){
			pre->rchild = p;
			pre->rtag = 1;
		}else
			pre->rtag = 0;
		pre = p;
		InitInOrderThread(p->rchild);
	}
}
/*中序线索化二叉树*/
BTNode *CreateInOrderThread(BTNode *b){
	BTNode *root;
	root = (BTNode *)malloc(sizeof(BTNode));
	if(!root){
		return root;
	}
	root->ltag = 0;
	root->rtag = 1;
	root->rchild = b;
	if(b==NULL){
		root->lchild = root;
	}else{
		root->lchild = b;
		pre = root;
		InitInOrderThread(b);
		pre->rchild = root;
		pre->rtag = 1;
		root->rchild = pre;
	}
	return root;
}
/*中序线索化二叉树tb实现中序遍历*/
void InOrderThread(BTNode *tb){
	BTNode *p;
	p = tb->lchild;
	while(p!=tb){
		while(p->ltag==0)
			p = p->lchild;
		inorderthread_line_graph(p,tb,GREEN,3);
		delay(9000000000000000);
		while(p->rtag==1&&p->rchild!=tb){
			p = p->rchild;
			inorderthread_line_graph(p,tb,GREEN,3);
			delay(9000000000000000);
		}
		p = p->rchild;
	}
}
/*对二叉树P进行后序线索化*/
void InitPostOrderThread(BTNode *p){
	if(p!=NULL){ 
		InitPostOrderThread(p->lchild);
		InitPostOrderThread(p->rchild);
		if(p->lchild==NULL){
			p->lchild = pre;
			p->ltag = 1;
		}else
			p->ltag = 0;
		if(pre ->rchild==NULL){
			pre->rchild = p;
			pre->rtag = 1;
		}else
			pre->rtag = 0;
		pre = p;
	}
}
/*后序线索化二叉树*/
BTNode *CreatePostOrderThread(BTNode *b){
	BTNode *root;
	root = (BTNode *)malloc(sizeof(BTNode));
	if(!root){
		return root;
	}
	root->ltag = 0;
	root->rtag = 1;
	root->rchild = b;
	if(b==NULL){
		root->lchild = root;
	}else{
		root->lchild = b;
		pre = root;
		InitPostOrderThread(b);
		root->rchild = pre;
	}
	return root;
}
/*后序线索化二叉树tb实现后序遍历*/
void PostOrderThread(BTNode *b){
	if(b->ltag==0)
		PostOrderThread(b->lchild);
	if(b->rtag==0)
		PostOrderThread(b->rchild);
	postorderthread_line_graph(b,GREEN,3);
	delay(900000000000000000);
}