171.cpp

这是数据结构的一个遍历的简单算法,希望对初学者有所帮助.

	#include<stdio.h>
	#include<stdlib.h>
	#include<malloc.h>
	typedef struct TBiTree{

		int   data;                       /*输入的数据*/

		struct  TBiTree    *lchild,*rchild;    

	   /*结点的左右指针，分别指向结点的左右孩子*/

		}BiTNode,*BiTree;

 

	searchBST(BiTree t,int key,BiTree f,BiTree *p) /*查找函数*/

	{

		if(!t)  
		{
			*p=f;
			return (0);
		}         /*查找不成功*/

	else    if(key==t->data)    
			{
				*p=t;
				return (1);
			} 

	 /*查找成功*/

		else    if(key<t->data)   
			searchBST(t->lchild,key,t,p);  

			   /*在左子树中继续查找*/

	else    searchBST(t->rchild,key,t,p); 

	/*在右子树中继续查找*/

	}

 

	insertBST(BiTree *t,int key)  /*插入函数*/

	{

		BiTree p=NULL,s=NULL;
		if(!searchBST(*t,key,NULL,&p))   /*查找不成功*/

		{

			s=(BiTree)malloc(sizeof(BiTNode));

			s->data=key;

			s->lchild=s->rchild=NULL;

			if(!p)  *t=s;     /*被插结点*s为新的根结点*/

			else    if(key<p->data)  
				p->lchild=s;

	 /*被插结点*s为左孩子*/

					else    
						p->rchild=s;  

	/*被插结点*s为右孩子*/

			return (1);

		}

	else  return (0);

	 /*树中已有关键字相同的结点，不再插入*/

	}

	inorderTraverse(BiTree *t)  /*中序遍历函数*/

	{

		if(*t){

				if(inorderTraverse(&(*t)->lchild))                               /*中序遍历根的左子树*/

				{

					printf("%d  ",(*t)->data);  

	/*输出根结点*/

					if(inorderTraverse(&(*t)->rchild)); 

	/*中序遍历根的右子树*/

				}

		}

		else    return(1);

	}

 

	calculateASL(BiTree *t,int *s,int *j,int i) 

	/*计算平均查找长度*/

	{

		if(*t){

				i++;   /*i记录当前结点的在当前树中的深度*/

				*s=*s+i;   /*s记录已遍历过的点的深度之和*/

				if(calculateASL(&(*t)->lchild,s,j,i)) 

	 /*计算左子树的ASL*/

				{

					(*j)++;   /*j记录树中结点的数目*/

					if(calculateASL(&(*t)->rchild,s,j,i)) /*计算右子树的ASL*/

					{i--; return(1);}

				}

		}

		else    return(1);

	}

 

	BiTree Delete(BiTree t,int  key)   /*删除函数*/

	{

		BiTree    p=t,q=NULL,s,f;

 

		while(p!=NULL)   /*查找要删除的点*/

		{

			if(p->data==key)  break;

			q=p;

			if(p->data>key)   p=p->lchild;

			else    p=p->rchild;

		}

		if(p==NULL)   return  t;    /*查找失败*/

		if(p->lchild==NULL)     /*p指向当前要删除的结点*/

		{

			if(q==NULL)   t=p->rchild;  /*q指向要删结点的父母*/

			else    if(q->lchild==p)    q->lchild=p->rchild;  /*p为q的左孩子*/

					else    q->rchild=p->rchild;

	 /*p为q的右孩子*/

			free(p);

		}

		else{           /*p的左孩子不为空*/

			f=p;

			s=p->lchild;

			while(s->rchild)   /*左拐后向右走到底*/

			{

				f=s;

				s=s->rchild;

			}

			if(f==p)    f->lchild=s->lchild;  /*重接f的左子树*/

			else    f->rchild=s->lchild;   /*重接f的右子树*/

			p->data=s->data;

			free (s);

		}

		return  t;

	}

	void main()

	{

		BiTree  T=NULL;

		int   num;

		int   s=0,j=0,i=0;

		int   ch=0;

		BiTree  p=NULL;

 

		printf("please input a list of numbers end with zero:\n");
		printf("请输入工系列数字并以0结束\n");

		do{

			scanf("%d",&num);

			if(!num) 
				printf("you have finished your input!\\n");

			else    
				insertBST(&T,num);

		}while(num);

		printf("\\n\\n---the menu of the opperation---\\n");  /*主程序菜单*/
		printf("\n菜单如下！\n");

		printf("\\n  0:  退出exit" );

		printf("\\n  1:  中序遍历inorder travel the tree");

		printf("\\n  2:  平均长度the average search length for the tree");

		printf("\\n  3:  删除delete");

		while(ch==ch)

		{

			printf("\\n   choose the opperation to continue:");

			scanf("%d",&ch);

			switch(ch){

				case 0:   exit(0);    /*0－－退出*/
				case 1:   printf("   The result of the inorder traverse is:\\n   ");

         
	/*1－－中序遍历*/

						  break;

				case 2:   s=0;j=0;i=0;

						  calculateASL(&T,&s,&j,i); 

	 /*2－－计算平均查找长度*/

						  printf("   ASL=%d/%d",s,j);

						  break;

				case 3:   printf("   Please input the number you want to delete:");

						  scanf("%d",&num);  

	 /*3－－删除某个结点*/

						  if(searchBST(T,num,NULL,&p))

						  {

							T=Delete(T,num);

							printf("   You have delete the number successfully!\\n   ");

							inorderTraverse(&T);

						  }

						  else  printf("   No BiTree %d you want to delete!",num);

						  break;

           
	 }
	}
	}