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

一、思想(先序思想创建):

第一步先创建根节点,然后创建根节点左子树,开始递归创建左子树,直到递归创建到的节点下不继续创建左子树,也就是当下递归到的节点下的左子树指向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;	
} 

版权声明:本文为chinesekobe原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。