如何创建一颗完全二叉树(C语言)

程序员文章站 2022-05-06 23:37:59

...

先介绍以下本人自己的二叉树的大概结构

前几天刚学到二叉树，然后我就自己想着如何使用我最爱的C语言创建一棵完全二叉树

知识点：

二叉树

如何创建一颗完全二叉树(C语言)

空的队列（头节点不储存数据）

如何创建一颗完全二叉树(C语言)

非空队列（头节点不储存数据）

如何创建一颗完全二叉树(C语言)

删除节点，即从队列中取出数据

如何创建一颗完全二叉树(C语言)

思路

用户每输入一个非0（NoInfo）数据，我们都malloc一个QueueNode类型的节点来储存数据，并把存入队列中，用QueueNode类型的节点来保存数据，并更改Q里面的数据，然后就是把这个数据插入到二叉树里面。再从队列中取出来一个数据，将接下来输入的两个数据分别同样malloc一个QueueNode类型的节点来存放数据，并把它存入队列中，然后把这两个数据插入取出的这个节点的左右孩子里面

typedef int ElementType;//输入的数据的类型
#define NoInfo 0//如果输入是0，则输入结束
////////////////////////////////////////////////////////////////////
typedef struct TreeNode* BinTree; 
struct TreeNode//二叉树节点
{
	ElementType Data;
	BinTree Left;
	BinTree Right;
};
/////////////////////////////////////////////////////////////////////
typedef struct QueueNode*PtrToNode;//队列中的节点
struct QueueNode
{
	BinTree Data;//指着储存数据的那块内存
	PtrToNode Next;//指着下一个节点
};
typedef PtrToNode Position;
typedef struct QNode* PtrToQNode;//队列的头尾数据和队列的长度
struct QNode
{
	Position Front, Rear;
	int Size;//队列中节点的个数
};
typedef PtrToQNode Queue;

队列的操作

创建一个空队列

Queue CreateQueue()//创建一个空队列,里面没有除了头节点外的其他任何节点
{
	Queue Q = (Queue)malloc(sizeof(struct QNode));
	Q->Front = Q->Rear = (Position)malloc(sizeof(struct QueueNode));//刚开始指针都指着头节点，为这个头节点申请了一块内存
	Q->Size = 0;
	Q->Front->Next = Q->Front->Data = NULL;
	return Q;
}

如何创建一颗完全二叉树(C语言)

入队

void AddQ(Queue Q, BinTree BT)
{
	Q->Size++;
	Position Temp = Q->Rear;//先保存好尾节点指针
	Q->Rear = (Position)malloc(sizeof(struct QueueNode));//尾节点指着这块内存
	Q->Rear->Data = BT;//这块内存里面的数据指针指着这个二叉树节点的内存
	Q->Rear->Next = NULL;
	Temp->Next = Q->Rear;//把上一个节点和这一个节点连接起来
}

出队

BinTree DeleteQ(Queue Q)
{
	BinTree BT;
	if (Q->Front->Next == NULL)//如果是空的
		return NULL;//报错
	Q->Size--;//先把长度减一
	Position Temp = Q->Front->Next;//先保存好头节点的Next指针，Q->Front指着头节点
	if (Temp == Q->Rear)
		Q->Rear = Q->Front;//返回头节点
	Q->Front->Next = Temp->Next;//头节点的Next指针往下移，多出来一个节点就是要删除的节点
	BT = Temp->Data;
	free(Temp);//释放队列节点内存
	return BT;
}

下面就是完全二叉树的具体的创建过程，用户输入0时创建结束

具体过程

BinTree CreateBinTree()//创建一个完全二叉树，是全过程的精髓
{
	ElementType Data;
	BinTree BT, T;
	Queue Q = CreateQueue();//创建一个空队列
	scanf_s("%d", &Data);//临时存放数据
	if (Data != NoInfo)//等于0表示输入终结
	{
		BT = (BinTree)malloc(sizeof(struct TreeNode));//为二叉树节点申请一个内存,先插入二叉树
		BT->Data = Data;
		BT->Left = BT->Right = NULL;
		AddQ(Q, BT);//入队
	}
	else//等于0表示输入终结
		return NULL;
	while (Q->Size != 0)//如果队列不为空
	{
		T = DeleteQ(Q);//出队,已经筛选好了指针，可以直接用
		scanf_s("%d", &Data);
		if (Data == NoInfo)
		{
			T->Left = NULL;
			T->Right = NULL;
			return BT;
		}
		else//为新数据申请内存节点，把节点插入二叉树
		{
			T->Left = (BinTree)malloc(sizeof(struct TreeNode));
			T->Left->Data = Data;
			T->Left->Left = T->Left->Right = NULL;
			AddQ(Q, T->Left);
		}
		scanf_s("%d", &Data);
		if (Data == NoInfo)
		{
			T->Right = NULL;
			return BT;
		}
		else//为新数据申请内存节点，把节点插入二叉树
		{
			T->Right = (BinTree)malloc(sizeof(struct TreeNode));
			T->Right->Data = Data;
			T->Right->Left = T->Right->Right = NULL;
			AddQ(Q, T->Right);
		}
	}
	return BT;
}

再来个层序遍历遍历完全二叉树，层序遍历也用到了队列

void SequenceTraversal(BinTree BT)
{
	BinTree T = BT;
	Queue Q = CreateQueue();//先创建一个队列
	AddQ(Q, BT);//入队
	while (1)
	{
		T = DeleteQ(Q);//出队
		if (T == NULL)
			return;
		else
		{
			if (T->Left != NULL)
			{
				AddQ(Q, T->Left);
				if (T->Right != NULL)
					AddQ(Q, T->Right);
			}
			printf("%d ", T->Data);
		}
	}
}

得，完整代码在此

#include<stdio.h>
typedef int ElementType;//输入的数据的类型
#define NoInfo 0//如果输入是0，则输入结束
////////////////////////////////////////////////////////////////////
typedef struct TreeNode* BinTree; 
struct TreeNode//二叉树节点
{
	ElementType Data;
	BinTree Left;
	BinTree Right;
};
/////////////////////////////////////////////////////////////////////
typedef struct QueueNode*PtrToNode;//队列中的节点
struct QueueNode
{
	BinTree Data;//指着那块内存
	PtrToNode Next;
};
typedef PtrToNode Position;
typedef struct QNode* PtrToQNode;//队列的头尾数据和队列的长度
struct QNode
{
	Position Front, Rear;
	int Size;
};
typedef PtrToQNode Queue;
///////////////////////////////////////////////////////////////////
BinTree CreateBinTree();
Queue CreateQueue();
void AddQ(Queue Q, BinTree BT);
BinTree DeleteQ(Queue Q);
void SequenceTraversal(BinTree BT);
///////////////////////////////////////////////////////////////////
int main()
{
	BinTree T = CreateBinTree();//输入一个元素就回一次车，他就会层序给你排好，建立一个完全二叉树
	SequenceTraversal(T);
	return 0;
}
/********************************************************************************************************
创建思路：用户每输入一个非0（NoInfo）数据，我们都malloc一个QueueNode类型的节点来储存数据，并把存入队列中，
用QueueNode类型的节点来保存数据，并更改Q里面的数据，然后就是把这个数据插入到二叉树里面。再从队列中取出来一
个数据，将接下来输入的两个数据分别同样malloc一个QueueNode类型的节点来存放数据，并把它存入队列中，然后把这
两个数据插入取出的这个节点的左右孩子里面
*********************************************************************************************************/
BinTree CreateBinTree()//创建一个完全二叉树，是全过程的精髓
{
	ElementType Data;
	BinTree BT, T;
	Queue Q = CreateQueue();//创建一个空队列
	scanf_s("%d", &Data);//临时存放数据
	if (Data != NoInfo)//等于0表示输入终结
	{
		BT = (BinTree)malloc(sizeof(struct TreeNode));//为二叉树节点申请一个内存,先插入二叉树
		BT->Data = Data;
		BT->Left = BT->Right = NULL;
		AddQ(Q, BT);//入队
	}
	else//等于0表示输入终结
		return NULL;
	while (Q->Size != 0)//如果队列不为空
	{
		T = DeleteQ(Q);//出队,已经筛选好了指针，可以直接用
		scanf_s("%d", &Data);
		if (Data == NoInfo)
		{
			T->Left = NULL;
			T->Right = NULL;
			return BT;
		}
		else//为新数据申请内存节点，把节点插入二叉树
		{
			T->Left = (BinTree)malloc(sizeof(struct TreeNode));
			T->Left->Data = Data;
			T->Left->Left = T->Left->Right = NULL;
			AddQ(Q, T->Left);
		}
		scanf_s("%d", &Data);
		if (Data == NoInfo)
		{
			T->Right = NULL;
			return BT;
		}
		else//为新数据申请内存节点，把节点插入二叉树
		{
			T->Right = (BinTree)malloc(sizeof(struct TreeNode));
			T->Right->Data = Data;
			T->Right->Left = T->Right->Right = NULL;
			AddQ(Q, T->Right);
		}
	}
	return BT;
}
Queue CreateQueue()//创建一个空队列,里面没有除了头节点外的其他任何节点
{
	Queue Q = (Queue)malloc(sizeof(struct QNode));
	Q->Front = Q->Rear = (Position)malloc(sizeof(struct QueueNode));//刚开始指针都指着头节点，为这个头节点申请了一块内存
	Q->Size = 0;
	Q->Front->Next = Q->Front->Data = NULL;
	return Q;
}
void AddQ(Queue Q, BinTree BT)
{
	Q->Size++;
	Position Temp = Q->Rear;//先保存好尾节点指针
	Q->Rear = (Position)malloc(sizeof(struct QueueNode));//尾节点指着这块内存
	Q->Rear->Data = BT;//这块内存里面的数据指针指着这个二叉树节点的内存
	Q->Rear->Next = NULL;
	Temp->Next = Q->Rear;//把上一个节点和这一个节点连接起来
}
BinTree DeleteQ(Queue Q)
{
	BinTree BT;
	if (Q->Front->Next == NULL)//如果是空的
		return NULL;//报错
	Q->Size--;//先把长度减一
	Position Temp = Q->Front->Next;//先保存好头节点的Next指针，Q->Front指着头节点
	if (Temp == Q->Rear)
		Q->Rear = Q->Front;//返回头节点
	Q->Front->Next = Temp->Next;//头节点的Next指针往下移，多出来一个节点就是要删除的节点
	BT = Temp->Data;
	free(Temp);//释放队列节点内存
	return BT;
}
void SequenceTraversal(BinTree BT)
{
	BinTree T = BT;
	Queue Q = CreateQueue();//先创建一个队列
	AddQ(Q, BT);//入队
	while (1)
	{
		T = DeleteQ(Q);//出队
		if (T == NULL)
			return;
		else
		{
			if (T->Left != NULL)
			{
				AddQ(Q, T->Left);
				if (T->Right != NULL)
					AddQ(Q, T->Right);
			}
			printf("%d ", T->Data);
		}
	}
}

如何创建一颗完全二叉树(C语言)

先介绍以下本人自己的二叉树的大概结构

知识点：

二叉树

空的队列（头节点不储存数据）

非空队列（头节点不储存数据）

删除节点，即从队列中取出数据

思路

队列的操作

创建一个空队列

入队

出队

具体过程

再来个层序遍历遍历完全二叉树，层序遍历也用到了队列

得，完整代码在此

C语言实现线索二叉树的前中后创建和遍历详解

C语言二叉树统计二叉树中度为0,1和2的结点个数【树和二叉树】给定先序序列，按照该序列创建对应的二叉树，并输出该二叉树度为0,1和2的结点个数。输入：一行，二叉树按先序遍历序列，空指针用字符^占位

如何创建一颗完全二叉树(C语言)

C语言--二叉树创建与遍历

C语言--线索二叉树创建与遍历

如何创建一颗完全二叉树(C语言)

先介绍以下本人自己的二叉树的大概结构

知识点：

二叉树

空的队列（头节点不储存数据）

非空队列（头节点不储存数据）

删除节点，即从队列中取出数据

思路

队列的操作

创建一个空队列

入队

出队

具体过程

再来个层序遍历遍历完全二叉树，层序遍历也用到了队列

得，完整代码在此

C语言实现线索二叉树的前中后创建和遍历详解

C语言 二叉树 统计二叉树中度为0,1和2的结点个数【树和二叉树】给定先序序列，按照该序列创建对应的二叉树，并输出该二叉树度为0,1和2的结点个数。输入：一行，二叉树按先序遍历序列，空指针用字符^占位

如何创建一颗完全二叉树(C语言)

C语言--二叉树创建与遍历

C语言--线索二叉树创建与遍历

C语言二叉树统计二叉树中度为0,1和2的结点个数【树和二叉树】给定先序序列，按照该序列创建对应的二叉树，并输出该二叉树度为0,1和2的结点个数。输入：一行，二叉树按先序遍历序列，空指针用字符^占位