tree.h

这个是二叉树的19个功能演示！ 初学者可以看看 希望可以交流交流

#include <stdio.h>
#include <stdlib.h>
#include <math.h> 

#define NONE 0
#define EXIST 1
#define ERROR 0
#define OK 1
#define MAXSIZE 50

typedef struct BiTNode
{
	char data;
	struct BiTNode *LChild;
	struct BiTNode *RChild;
}BiTNode,*BiTree;

typedef struct queue
 {  //二叉树结点队列
    BiTree elem;
    int front;
    int rear;
 }Queue,*LinkQueue;


void Main_Face()
{
	printf("\n");
	printf("★━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━★\n");
	printf("┃                ┏━━┓┏━━┓┏━━┓┏━━┓┏━━┓                ┃\n");
	printf("┃                ┃ 二 ┃┃ 叉 ┃┃ 树 ┃┃ 实 ┃┃ 验 ┃                ┃\n");
	printf("┃                ┗━━┛┗━━┛┗━━┛┗━━┛┗━━┛                ┃\n");
	printf("┃                                                        QQ:11641100 鬼眼┃\n");
	printf("☆━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━☆\n");	
	printf("★━━━━━━━━━━━☆━━━━━━━━━━━━☆━━━━━━━━━━━★\n");
	printf("┃      ※控制类※      ┃        ※遍历类※      ┃       ※查找类※     ┃\n");
	printf("☆━━━━━━━━━━━☆━━━━━━━━━━━━☆━━━━━━━━━━━☆\n");
	printf("┃ ●1.创建二叉树       ┃   ●7.先序遍历二叉树   ┃  ●12.元素的左孩子   ┃\n");
	printf("┃ ●2.插入新的结点     ┃   ●8.中序遍历二叉树   ┃  ●13.元素的右孩子   ┃\n");
	printf("┃ ●3.删除结点元素     ┃   ●9.后序遍历二叉树   ┃  ●14.元素的左兄弟   ┃\n");
	printf("┃ ●4.二叉树的根节点   ┃   ●10.层序遍历二叉树  ┃  ●15.元素的右兄弟   ┃\n");
	printf("┃ ●5.二叉树是否为空   ┃   ●11.输出树状图      ┃  ●16.元素的双亲结点 ┃\n");
	printf("┃ ●6.二叉树的深度     ┃                        ┃  ●17.元素的祖先     ┃\n");
	printf("☆━━━━━━━━━━━☆━━━━━━━━━━━━☆━━━━━━━━━━━☆\n");
	printf("┃    ※树操作※        ┃     ●18.输出叶子结点  ┃    ●19.销毁二叉树   ┃\n");
	printf("☆━━━━━━━━━━━☆━━━━━━━━━━━━☆━━━━━━━━━━━☆\n");
	printf("┃    ★☆★☆★☆★☆★☆★☆    0.退出     ★☆★☆★☆★☆★☆★☆     ┃\n");
	printf("★━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━★\n");



}



/*******************************************/
/*             初始化队列                  */
/*******************************************/


int InitQueue(LinkQueue &Q)
{
	Q->elem = (BiTree)malloc(MAXSIZE*sizeof(BiTNode));
	if(!Q->elem)  return ERROR;
	Q->front = Q->rear = 0;

	return OK;
	
}


/*******************************************/
/*            入队列                 */
/*******************************************/

int EnQueue(LinkQueue &Q,BiTree T)
{
	Q->rear = (Q->rear+1)%MAXSIZE;
	if(Q->rear==Q->front)  return ERROR;
	Q->elem[Q->rear]=*T;
	return OK;
}


/*******************************************/
/*             出队列                 */
/*******************************************/

BiTree DeQueue(LinkQueue &Q)
{
	BiTree r;
	r=(BiTree)malloc(sizeof(BiTNode));
	if(Q->front==Q->rear) return ERROR;
	*r=Q->elem[Q->front+1];
	Q->front=(Q->front+1)%MAXSIZE;
	return r;
}



/*******************************************/
/*             队列判空                  */
/*******************************************/
int empty(LinkQueue Q) //是否队空
{
	if(Q->front==Q->rear)
 return ERROR;
 return OK;
}



/*******************************************/
/*             初始化二叉树                  */
/*******************************************/

int InitBiTree(BiTree &T)
{
	T=(BiTree)malloc(sizeof(BiTNode));
	if(!T) return ERROR;
	else
	{
	T->data=NULL;
	T->LChild=NULL;
	T->RChild=NULL;
	return OK;
	}
}



/*******************************************/
/*             层次遍历二叉树              */
/*******************************************/


void Leveltraverse(BiTree T) //层次遍历   
{   
	LinkQueue Q;
	InitQueue(Q);
	if (T)
	EnQueue(Q,T);
	printf("【层序遍历结果是】→");
	
	while (empty(Q))
	{   
		T=DeQueue(Q); 
		printf("%3c",T->data);
		if (T->LChild)
		EnQueue(Q,T->LChild);  
		if (T->RChild)
		EnQueue(Q,T->RChild);    
	}   
}   


/*******************************************/
/*             竖向输出树状图             */
/*******************************************/
 	
void DisplayTree(BiTree T,int k) 
 {   
 	 
	if(T == NULL) return; 
	if(T->RChild) 
	{ 
		DisplayTree(T->RChild, k + 1 ); 	
	} 

	for( int i = 0; i < k; i++ ) 
	{ 
		printf("    "); 
    } 
	printf("%c\n", T->data); 


	if( T->LChild ) 
	{ 
		DisplayTree( T->LChild,k + 1 ); 
	} 
} 
 

/*******************************************/
/*            清理屏幕函数                 */
/*******************************************/


void Clear()
{
	printf("\n\n");
	system("pause");
	system("cls");
}



/*******************************************/
/*             创建二叉树                  */
/*******************************************/

void CreateBiTree (BiTree &T)
{
	char ch;
   
	if((ch=getchar())=='.')
	{
        T=NULL;
	}
	else
	{
		T=(BiTree)malloc(sizeof(BiTNode));
		T->data = ch;
		CreateBiTree(T->LChild);
		CreateBiTree(T->RChild);
	}

}


/*******************************************/
/*             求二叉树的根                 */
/*******************************************/

int Root(BiTree T)
{
    if(T==NULL)
	{
		return NONE;
	}
	else
	{
		return EXIST;
	}
}



/*******************************************/
/*             递归先序遍历                  */
/*******************************************/

void PreOrderTraverse(BiTree T)
{
	if(T!=NULL)
	{
		printf("%3c",T->data);
		PreOrderTraverse(T->LChild);
		PreOrderTraverse(T->RChild);
	}
}



/*******************************************/
/*             递归中序遍历                 */
/*******************************************/

void InOrderTraverse(BiTree T)
{
	if(T!=NULL)
	{		
		InOrderTraverse(T->LChild);
		printf("%3c",T->data);
		InOrderTraverse(T->RChild);
	}
}
      

/*******************************************/
/*             递归后序遍历                 */
/*******************************************/

void PostOrderTraverse(BiTree T)
{
	if(T!=NULL)
	{
		PostOrderTraverse(T->LChild);
		PostOrderTraverse(T->RChild);
		printf("%3c",T->data);
	}
}



/*******************************************/
/*             二叉树   判空               */
/*******************************************/

void BiTreeEmpty(BiTree T)
{
	if(T->data==NULL)
	{
		printf("【该树为空】");
	}
	else
	{
		printf("【该树不为空】");
	}
}



/*******************************************/
/*             求二叉树的深度             */
/*******************************************/

int PostTreeDepth(BiTree T) 
{
    int hl, hr, max;
    if (T!=NULL)
    {
      hl = PostTreeDepth ( T->LChild );  
      hr = PostTreeDepth ( T->RChild ); 
      max = hl>hr ? hl:hr;              
      return(max+1);                
    }
    else 
		return 0; 
} 


/*******************************************/
/*             横向输出树状图             */
/*******************************************/


void PrintSpace(int t)
{
	for(int i=0;i<(10-2*t);i++)
	{
		printf(" ");
	}
	
}

void DisplayTree1(BiTree T)
{
	LinkQueue W;
	int i,j,k,t;
	k=PostTreeDepth(T);
	InitQueue(W);
	BiTree p;
	char a[100];
	int count=0;
	
	if (T)
	EnQueue(W,T);
	
	for(i=0;i<100;i++)
	{
		a[i]=0;
	}
	
	
	
	while (empty(W))
	{   
		T=DeQueue(W); 
		a[count++]=T->data;
		
		
		
		if (T->LChild)
		{
		EnQueue(W,T->LChild); 
		} 
		
			else
		{   
			p=(BiTree)malloc(sizeof(BiTNode));
			p->data='#';
			p->LChild=NULL;
			p->RChild=NULL;
			EnQueue(W,p);  
			}
	
		if (T->RChild)
		{
		EnQueue(W,T->RChild);  
		} 
		else
		{   
			p=(BiTree)malloc(sizeof(BiTNode));
			p->data='#';
			p->LChild=NULL;
			p->RChild=NULL;
			EnQueue(W,p);  
			}

		
	} 
	
	
	i=0;
	printf("【横向树状图】→\n");

		for(t=1;t<=k;t++)
		{
			 PrintSpace(t);
		for(j=1;j<=pow(2,t-1);j++)
		{
			 PrintSpace(t);
		printf("%c",a[i]);
		i++;
		}
		printf("\n");
		}
	
}


/*******************************************/
/*             插入一个结点               */
/*******************************************/


BiTree SearchNode(BiTree &T,char P)
{
	BiTree p;
	if(!T) return NULL;
	else
	{
		if(T->data==P)
		{
			return T;
		}
	
			p = SearchNode(T->LChild,P);			
            if(p) 
                return p;               
            else
            return SearchNode(T->RChild,P);        			
	}	
	return NULL;
}






void InsertChild(BiTree &T,char P,char LR,char c)
{
	BiTree p,getNode;
	p=(BiTree)malloc(sizeof(BiTNode));
	getNode=SearchNode(T,P);
	if(LR=='L'||LR=='l')
	{
		if(getNode->LChild!=NULL)
		{
			printf("该双亲结点已经有左孩子\n");
			return;
		}
		
		getNode->LChild = p;
		p->LChild=NULL;
		p->RChild=NULL;
		p->data = c;
	}
	
	if(LR=='R'||LR=='r')
	{
		if(getNode->RChild!=NULL)
		{
			printf("该双亲结点已经有右孩子\n");
			return;
		}
		
		getNode->RChild = p;
		p->LChild=NULL;
		p->RChild=NULL;
		p->data = c;
	}	
}




/*******************************************/
/*             删除一个结点               */
/*******************************************/

void DeleteChild(BiTree &T,char P,char LR)
{
	BiTree getNode,p;
	getNode=SearchNode(T,P);
	if(LR=='L'||LR=='l')
	{
		p=getNode->LChild;
		getNode->LChild=NULL;
		free(p);
	}
	
	if(LR=='R'||LR=='r')
	{
		p=getNode->RChild;
		getNode->RChild=NULL;
		free(p);
	}	
}



/*******************************************/
/*             置空                       */
/*******************************************/

int ClearTree(BiTree &T)
{
	if(!T)
	{
		return ERROR;
	}
	else
	{
		if(T->LChild) 
		{
			ClearTree(T->LChild);
			free(T->LChild);
		}
		if(T->RChild) 
		{
			ClearTree(T->RChild);
			free(T->RChild);
		}
		T->LChild = NULL;
		T->RChild = NULL;
		T->data = NULL;
		return OK;
		}
}




/*******************************************/
/*            销毁树                      */
/*******************************************/

int DestroyTree(BiTree &T)
{
	if(!T)
	{
		return ERROR;
	}
	else
	{
		free(T);
		return OK;
	}	
}


/*******************************************/
/*            搜索左孩子                     */
/*******************************************/

BiTree SearchLChild(BiTree T,char e)
{
    BiTree q;
	while(T)
	{
		if(T->data==e)
	    {
	    	if(T->LChild!=NULL)
	    	{
	    		return T;
	    	} 	
	    }
	    
	        q=SearchLChild(T->LChild,e);
	        if(q)
	        return q;	      
	        else return SearchLChild(T->RChild,e);
	}

return NULL;
}




/*******************************************/
/*            搜索右孩子                     */
/*******************************************/

BiTree SearchRChild(BiTree T,char e)
{

    BiTree q;
	while(T)
	{
		if(T->data==e)
	    {
	    	if(T->RChild!=NULL)
	    	{	    		
	    		return T;
	    	}
	    		    	
	    }
	        q=SearchRChild(T->LChild,e);
	        if(q)
	        return q;	      
	        else return SearchRChild(T->RChild,e);
	}

return NULL;
}


/*******************************************/
/*             查找双亲结点               */
/*******************************************/


BiTree SearchParent(BiTree T,char e)
{
	BiTree q;
		
	  if(T==NULL) return NULL;
	  else
	  {
	  	
	  	    if(T->LChild!=NULL)//有左孩子进入循环
	  	    {
			if(T->LChild->data==e)//看到左孩子的跟我们输入的结点匹配
			{
				return T;//老爸返回给主函数
			}	
	  	    }
	  	    
	  	    
	  	    if(T->RChild!=NULL)//有右孩子进入循环  下面同上
	  	    {
			if(T->RChild->data==e)
			{
				return T;
			}	
	  	    }
	  	    
	  	    //递归寻找

				q=SearchParent(T->LChild,e);//找左边的树
				if(q)//知道匹配
				return q;//返回匹配
				else
				return SearchParent(T->RChild,e);//否则找右边的  
	  }
		
		

}



/*******************************************/
/*            找左兄弟                 */
/*******************************************/


BiTree SearchLBrother(BiTree T,char e)
{
	BiTree Parent;
	Parent=SearchParent(T,e);
	if(Parent->LChild!=NULL&&Parent->LChild->data!=e)
	{
		return Parent;
	}
	else
	{
		return NULL;
	}
		
}


/*******************************************/
/*               查找右兄弟                */
/*******************************************/

BiTree SearchRBrother(BiTree T,char e)
{
	BiTree Parent;
	Parent=SearchParent(T,e);
	if(Parent->RChild && Parent->RChild->data!=e)
	{
		return Parent;
	}
	else
	{
		return NULL;
	}
	
	
}

/*******************************************/
/*             查找祖先                 */
/*******************************************/

void ParentParent(BiTree T,char P)
{
	BiTree q;
	//p=SearchNode(T,P);
		
	q=SearchParent(T,P);
	if(q)
	{		
	printf("%3c",q->data);
	P=q->data;
	ParentParent(T,P);
	}
	else
	{
		return;
	}
	
}

/*******************************************/
/*             查找所有叶子结点                */
/*******************************************/


BiTree SearchTreeNode(BiTree T)
{
	BiTree q;
	if(T==NULL) return NULL;
	else
	{
	if(T->LChild==NULL&&T->RChild==NULL)
	{
		printf("%3c",T->data);
		
	}
	    
	    q=SearchTreeNode(T->LChild);
	    if(q)
	    return q;
	    else
	    return SearchTreeNode(T->RChild);
	}	
}