数据结构——二叉链表创建二叉树（C语言版）

悠悠 2022-12-27 07:11 170阅读 0赞

### 数据结构——二叉链表创建二叉树 ###

*  一、思想（先序思想创建）：
 *  二、创建二叉树
 *   *  （1）传一级参数方法
     *  (2)传二级参数方法

# 一、思想（先序思想创建）： #

> 第一步先创建根节点,然后创建根节点左子树,开始递归创建左子树，直到递归创建到的节点下不继续创建左子树，也就是当下递归到的节点下的左子树指向NULL，结束本次左子树递归，返回这个节点的上一个节点，开始创建右子树，然后又开始以当下这个节点，继续递归创建左子树，左子树递归创建完，就递归创建右子树，直到递归结束返回到上一级指针节点（也就是根节点下），此时根节点左边子树创建完毕，开始创建右边子树，原理和根节点左边创建左右子树相同

# 二、创建二叉树 #

> 二叉树的操作通常使用递归方法，如果递归不太明白，建议去对此进行一下学习和练习。二叉树的操作可以分为两类，一类是需要改变二叉树的结构的，比如二叉树的创建、节点删除等等，这类操作，传入的二叉树的节点参数为二叉树指针的地址，这种参入传入，便于更改二叉树结构体的指针（即地址）。这里稍微有一点点绕，可能需要多思考一下

*  如下是二叉数创建的函数，这里我规定，节点值为整数，如果输入的数为-1，则表示结束继续往下创建子节点的操作。然后我们使用递归的方法以此创建左子树和右子树

**二叉树结构体初始化**

> 为了更方便的使用二叉树结构体，可以使用 typedef 对结构体进行命名

typedef struct Tree{
        
     
     int data;					//	存放数据域
     struct Tree *lchild;			//	遍历左子树指针
     struct Tree *rchild;			//	遍历右子树指针
     
    }Tree,*BitTree;

> 这里展示两种传参类型的创建方法，其中深意可多次参考理解，加深指针理解

## （1）传一级参数方法 ##

BitTree CreateLink()
    {
        
    	int data;
    	int temp;
    	BitTree T;
    	
    	scanf("%d",&data);		//	输入数据
    	temp=getchar();			//	吸收空格
    	
    	if(data == -1){
        			//	输入-1 代表此节点下子树不存数据，也就是不继续递归创建
    		
    		return NULL;
    
    	}else{
        
    		T = (BitTree)malloc(sizeof(Tree));			//		分配内存空间
    		T->data = data;								//		把当前输入的数据存入当前节点指针的数据域中
    		
    		printf("请输入%d的左子树: ",data);		
    		T->lchild = CreateLink();					//		开始递归创建左子树
    		printf("请输入%d的右子树: ",data);			
    		T->rchild = CreateLink();					//		开始到上一级节点的右边递归创建左右子树
    		return T;							//		返回根节点
    	}	
    	
    }

## (2)传二级参数方法 ##

BitTree CreateLink(BitTree *T)		//	次数 T为指向根节点的指针的地址
    {
        
    	int data;	
    	
    	scanf("%d",&data);
    
    	
    	if(data == -1){
        
    		
    		*T=NULL;				//	结束递归时，让指针当前节点的指针地址的 指针 指向NULL
    
    	}else{
        
    		
    		*T = (BitTree)malloc(sizeof(Tree));		//	对指向节点指针地址的指针 分配内存
    	
    		if(!(*T) ){
        			//	*T = NULL  表示分配内存失败，也就是结束递归创建了
    			printf("内存分配失败\n");
    			exit(-1);
    		}
    		
    		
    		(*T)->data = data;		//	给节点指针地址内的数据域，存入数据
    		
    		printf("请输入%d的左子树: ",data);
    		CreateLink(&(*T)->lchild);		//	开始遍历左子树
    		printf("请输入%d的右子树: ",data);
    		CreateLink(&(*T)->rchild);		//	开始遍历右子树，遍历的思想文章开头处解释
    			
    	}	
    	
    }

**（1）一级参数完整例子：**

#include<stdio.h>
    #include<stdlib.h>
    
    typedef struct Tree{
        
     
     int data;					//	存放数据域
     struct Tree *lchild;			//	遍历左子树指针
     struct Tree *rchild;			//	遍历右子树指针
     
    }Tree,*BitTree;
    
    BitTree CreateLink()
    {
        
    	int data;
    	int temp;
    	BitTree T;
    	
    	scanf("%d",&data);		//	输入数据
    	temp=getchar();			//	吸收空格
    	
    	if(data == -1){
        			//	输入-1 代表此节点下子树不存数据，也就是不继续递归创建
    		
    		return NULL;
    
    	}else{
        
    		T = (BitTree)malloc(sizeof(Tree));			//		分配内存空间
    		T->data = data;								//		把当前输入的数据存入当前节点指针的数据域中
    		
    		printf("请输入%d的左子树: ",data);		
    		T->lchild = CreateLink();					//		开始递归创建左子树
    		printf("请输入%d的右子树: ",data);			
    		T->rchild = CreateLink();					//		开始到上一级节点的右边递归创建左右子树
    		return T;							//		返回根节点
    	}	
    	
    }
    
    void ShowXianXu(BitTree T)			//		先序遍历二叉树
    {
        
    	if(T==NULL)
    	{
        
    		return;
    	}
    	printf("%d ",T->data);
    	ShowXianXu(T->lchild);			//	递归遍历左子树
    	ShowXianXu(T->rchild);			//	递归遍历右子树
    }
    
    int main()
    {
        
    	BitTree S;
    	printf("请输入第一个节点的数据:\n");
    	S = CreateLink();			//		接受创建二叉树完成的根节点
    	ShowXianXu(S);				//		先序遍历二叉树
    	
    	return 0;	
    }

**（2）二级参数完整例子**

#include<stdio.h>
    #include<stdlib.h>
    typedef struct Tree{
        
    	
    	int data;
    	struct Tree *lchild;
    	struct Tree *rchild;
    }Tree,*BitTree;
    
    BitTree CreateLink(BitTree *T)		//	次数 T为指向根节点的指针的地址
    {
        
    	int data;	
    	
    	scanf("%d",&data);
    
    	
    	if(data == -1){
        
    		
    		*T=NULL;				//	结束递归时，让指针当前节点的指针地址的 指针 指向NULL
    
    	}else{
        
    		
    		*T = (BitTree)malloc(sizeof(Tree));		//	对指向节点指针地址的指针 分配内存
    	
    		if(!(*T) ){
        			//	*T = NULL  表示分配内存失败，也就是结束递归创建了
    			printf("内存分配失败\n");
    			exit(-1);
    		}
    		
    		
    		(*T)->data = data;		//	给节点指针地址内的数据域，存入数据
    		
    		printf("请输入%d的左子树: ",data);
    		CreateLink(&(*T)->lchild);		//	开始遍历左子树
    		printf("请输入%d的右子树: ",data);
    		CreateLink(&(*T)->rchild);		//	开始遍历右子树，遍历的思想文章开头处解释
    			
    	}	
    	
    }
    
    void ShowXianXu(BitTree T)		//	先序遍历二叉树
    {
        
    	if(T==NULL)
    	{
        
    		return;
    	}
    	printf("%d ",T->data);
    	ShowXianXu(T->lchild);		//	遍历左子树
    	ShowXianXu(T->rchild);		//	遍历右子树
    }
    
    int main()
    {
        
    	BitTree *S;			//	创建指向这个结构体指针地址 的指针
    	printf("请输入第一个节点的数据:\n");
    	CreateLink(&S);		//	传二级指针地址
    	ShowXianXu(S);		
    	
    	return 0;	
    }