📄 二叉树asdf.cpp

📁 数据结构的2叉树由VC编写而成
💻 CPP
字号:
#include<stdlib.h>
#include<stdio.h>

typedef  char  TElemType;

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

//1.构造二叉树
void CreateBiTree(BiTree &T)
{     
	char ch;
	scanf("%c",&ch);
    if(ch==' ')          
		T = NULL;
    else
	{
		T =(BiTree) malloc (sizeof(BiTNode));
		T->data=ch;
		CreateBiTree (T->LChild);
		CreateBiTree (T->RChild);
	}
} 

//2.求根结点
void  Root(BiTree  &T) 
{    
	if (T!=NULL)
	{
		printf("根结点为：%c \n",T ->data);       
	}
} 

//3.打印 
void print_btree(BiTree &T,int level) 
{ 
	if(T==NULL)
		return; 
	print_btree(T->RChild,level+1); 	
	for(int i=0;i<level;i++) 
		printf(" "); 
	printf("%c\n",T->data); 
	print_btree(T->LChild,level+1); 
} 


//4.返回双亲      ??
void Parent(BiTree  T,char M)
{
	if (T!=NULL)   
	{  
		if(T ->LChild!=NULL)
			if(T->LChild->data==M)
				printf("双亲结点为：%c\n",T->data);
		if(T ->RChild!=NULL)
			if(T->RChild->data==M)
				printf("双亲结点为：%c\n",T->data);
		Parent(T ->LChild ,M);
		Parent(T ->RChild ,M); 
	}
}

//5.左孩子
void LeftChild(BiTree  T,char M)
{
	if (T!=NULL)   
	{   
		if(T->data==M)
			if(T ->LChild==NULL)
				printf("该结点没有左孩子\n");
			else
				printf("左孩子为：%c\n",T ->LChild->data);
		LeftChild(T ->LChild ,M);
		LeftChild(T ->RChild ,M); 
	}
}

//6.右孩子          
void RightChild(BiTree  T,char M)
{
	if (T!=NULL)   
	{   
		if(T->data==M)
			if(T ->RChild==NULL)
				printf("该结点没有右孩子\n");
			else
				printf("右孩子为：%c\n",T ->RChild->data);
		RightChild(T ->LChild ,M);
		RightChild(T ->RChild ,M); 
	}
}

//7.左兄弟
void LeftSibling(BiTree  T,char M)
{
	if (T!=NULL)   
	{  
		if(T ->LChild!=NULL)
			if(T->LChild->data==M)
				printf("该结点不是右孩子\n");
		if(T ->RChild!=NULL)
		{
			if(T->RChild->data==M)
			{ 
				if(T->LChild!=NULL)
					printf("左兄弟为：%c\n",T->LChild->data);
				else
					printf("该结点没有左兄弟\n");
			}
		}
		LeftSibling(T ->LChild ,M);
		LeftSibling(T ->RChild ,M); 
	}
}


     
//8.右兄弟
void RightSibling(BiTree  T,char M)
{
	if (T!=NULL)   
	{  
		if(T ->RChild!=NULL)
			if(T->RChild->data==M)
				printf("该结点不是左孩子\n");
		if(T ->LChild!=NULL)
		{
			if(T->LChild->data==M)
			{ 
				if(T->RChild!=NULL)
					printf("右兄弟为：%c\n",T->RChild->data);
				else
					printf("该结点没有右兄弟\n");
			}
		}
		RightSibling(T ->LChild ,M);
		RightSibling(T ->RChild ,M); 
	}
}

//9.判空
void  BiTreeEmpty(BiTree  &T) 
{    
	if(T==NULL)      
		printf("该树为空树。\n");
	else
		printf("该树不为空树。\n");
} 
         
//10.求深度
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); 
 } 


//11.先序遍历T
void  PreOrder(BiTree  &T) 
{    
	if (T!=NULL)
	{
		printf("%c ",T ->data);       
		PreOrder ( T ->LChild ); 
		PreOrder ( T ->RChild ); 
	}
} 

//12.中序遍历T
void  InOrder(BiTree  &T) 
{    
	if (T!=NULL)
	{
		InOrder( T ->LChild );    
		printf("%c ",T ->data);  
		InOrder( T ->RChild ); 
	}
} 


//13.后序遍历T
void  PostOrder(BiTree  &T) 
{    
	if (T!=NULL)
	{
		PostOrder( T ->LChild ); 
		PostOrder( T ->RChild ); 
		printf("%c ",T ->data);
	}
} 

//14.层序遍历T
void LevleOrder(BiTree &T)       //采用递归方法层次遍历二叉树T，从第一层开始，每层从左到右
{                                  
    BiTree Queue[100],b;               //一维数组表示队列，front和rear分别表示队首和队尾指针
    int front,rear;                    //定义整型类
    front=rear=0;                      //初始化队首和队尾指针front和rear
    if (T)                              //树非空
	{
		Queue[rear++]=T;                   //根结点入队列
		while (front!=rear)
		{
			b=Queue[front++];   //当队列非空 队首元素出队列，并访问这个结点
			printf("%c ",b->data);                
			if (b->LChild!=NULL) Queue[rear++]=b->LChild;    //左子树非空，则入队列
			if (b->RChild!=NULL) Queue[rear++]=b->RChild; //子树非空，则入队列
		}
	}
} 


//15.根据LR为0或1,插入c为T中p所指结点的左或右子树.p所指结点的原有左或右子树则成为c的右子树.
void InsertChild(BiTree &T, char M, int LR,BiTree &c)
{
	BiTree a;
	if (T!=NULL)   
	{   
		if(T->data==M)
			if(LR==0)
			{
				a=T->LChild;
				T->LChild=c;
				c->LChild=a;
			}
			else
			{
				a=T->RChild;
				T->RChild=c;
				c->RChild=a;
			}
		InsertChild(T ->LChild, M, LR, c);
		InsertChild(T ->RChild, M, LR, c); 
	}
}


//17.清空二叉树
void  ClearBiTree(BiTree  &T) 
{    
	if (T!=NULL)
	{      
		ClearBiTree( T ->LChild ); 
		ClearBiTree( T ->RChild ); 
		free(T);
		T = NULL; 
	}
} 

//16.根据LR为0或1,删除T中p所指结点的左或右子树
void DeleteChild(BiTree &T, char M, int LR) 
{
	if (T!=NULL)   
	{   
		if(T->data==M)
			if(LR==0)
				ClearBiTree(T->LChild);
			else
				ClearBiTree(T->RChild);
		DeleteChild(T ->LChild ,M,LR);
		DeleteChild(T ->RChild ,M,LR); 
	}
}

//18.销毁
void  DestroyBiTree(BiTree  &T) 
{    
	if (T!=NULL)
	{      
		ClearBiTree( T ->LChild ); 
		ClearBiTree( T ->RChild ); 
		free(T);
	}
} 


//19.退出
void Tuichu(void)
{
	exit(0);
}

void main()
{
	BiTree T,c;
	char M;    
	printf("**********二叉树的应用**********\n");
    printf("1, 构造二叉树\n");
    printf("2, 求根结点\n");
    printf("3, 打印\n");
    printf("4, 返回双亲\n");
    printf("5, 左孩子\n");
    printf("6, 右孩子 \n");
    printf("7, 左兄弟\n");
    printf("8, 右兄弟\n");
    printf("9,  判空\n");
    printf("10, 求深度\n");
    printf("11, 先序遍历T\n");
    printf("12, 中序遍历T\n");
    printf("13, 后序遍历T\n");
    printf("14, 层序遍历T\n");
    printf("15, 特定位置插入子树\n");
    printf("16, 删除结点子树\n");
    printf("17, 清空二叉树\n");
    printf("18, 销毁\n");
    printf("19, 退出\n");

    while(1)
    {
		int number,a,LR;
        printf("\n");
        printf("请选择：");
        scanf("%d",&number);
	    switch(number)
    	{
        case 1:
			printf("请构造一个二叉树：");
			getchar();
			CreateBiTree(T);
			printf("构造成功.\n");
            break;
        case 2:
			Root(T);
            break;
        case 3:
			print_btree(T, 0) ;
            break;
        case 4:
			getchar();
			printf("请输入你要查找双亲结点的结点：");
			scanf("%c",&M);
			if(M==T->data)
				printf("该结点没有双亲结.\n");
			Parent(T,M);
            break;
        case 5:
			getchar();
			printf("请输入你要查找左孩子的结点：");
			scanf("%c",&M);
			LeftChild(T,M);
            break;
        case 6:
			getchar();
			printf("请输入你要查找右孩子的结点：");
			scanf("%c",&M);
			RightChild(T,M);
            break;
        case 7:
			getchar();
			printf("请输入你要查找左兄弟结点的结点：");
			scanf("%c",&M);
			if(M==T->data)
				printf("该结点没有左兄弟.\n");
			LeftSibling(T,M);
            break;
        case 8:
			getchar();
			printf("请输入你要查找右兄弟结点的结点：");
			scanf("%c",&M);
			if(M==T->data)
				printf("该结点没有右兄弟.\n");
			RightSibling(T,M);
            break;
        case 9:
			BiTreeEmpty(T);
            break;
        case 10:
			printf("二叉树的深度为：%d\n",a=PostTreeDepth(T));
            break;
		case 11:
			printf("二叉树的先序遍历为：");
			PreOrder(T);
			printf("\n");
            break;
		case 12:
			printf("二叉树的中序遍历为：");
			InOrder(T);
			printf("\n");
            break;
		case 13:
			printf("二叉树的后序遍历为：");
			PostOrder(T);
			printf("\n");
			break;
		case 14:
			printf("二叉树的层序遍历为：");
			LevleOrder(T);
			printf("\n");
			break;
		case 15:
			printf("请构造一个与要原有二叉树不相交的二叉树：");
			getchar();
			CreateBiTree(c);
			printf("构造成功.\n");
			getchar();
			printf("请输入你要插入子树的二叉树结点：");
			scanf("%c",&M);
			printf("如果你要插入的是在左子数请输入0，否则请输入1：");
			scanf("%d",&LR);
			InsertChild(T, M, LR, c);
            break;
        case 16:
			getchar();
			printf("请输入你要删除子树的结点：");
			scanf("%c",&M);
			printf("如果你要删除的是左子数请输入0，否则请输入1：");
			scanf("%d",&LR);
			DeleteChild(T, M, LR);
			printf("该子树已删除\n");
            break;
        case 17:
			ClearBiTree(T);
			printf("该二叉树已清空\n");
            break;
        case 18:
			DestroyBiTree(T);
			printf("该二叉树已销毁\n");
            break;
        case 19:
			Tuichu();
            break;
        default:;
    	}
    }
}
💿 文件大小 3 K
👤 上传用户 hushanlyn
📂 所属分类数据结构
🏷️ 相关标签

#数据结构 #树 #编写
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -