标准二叉树的创建

最新推荐文章于 2024-05-21 16:08:56 发布

陈恒_nick

最新推荐文章于 2024-05-21 16:08:56 发布

阅读量1w

点赞数 1

分类专栏：数据结构及算法（C语言描述）文章标签：数据结构二叉树的创建队列

本文链接：https://blog.csdn.net/nick_chain/article/details/87985800

版权

数据结构及算法（C语言描述）专栏收录该内容

4 篇文章

订阅专栏

本文介绍了一种使用队列创建二叉树的方法，详细展示了队列操作与二叉树节点之间的交互，包括队列的创建、入队、出队等关键步骤，以及二叉树的初始化和遍历过程。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
typedef char ElementType;


typedef struct TNode{
	ElementType Data;
	struct TNode* Rchild;
	struct TNode* Lchild;
}BinTree;

typedef struct Node{
	BinTree* Data[MAXSIZE];
	int front;
	int rear;
}Queue;

//队列的创建
Queue* CreateQ(Queue* Q){

	Q = (Queue*)malloc(sizeof(Queue));
	if(!Q){
		printf("no enough memory\n");
		exit(-1);
	}
	else{
		Q->front = Q->rear = 0;
		return Q;
	}
}

//入队
void Add(Queue* Q,BinTree* T){
	if((Q->rear+1)%MAXSIZE == Q->front){
		printf("Queue was full\n");
		return;
	}
	else{
		Q->rear = (Q->rear+1)%MAXSIZE;
		Q->Data[Q->rear] = T;
	}
}

//出队
BinTree* DeleteQ(Queue* Q){
	BinTree* BT;
	if(Q->rear == Q->front){
		printf("Queue was empty\n");
		exit(-1);
	}
	else{
		Q->front = (Q->front+1)%MAXSIZE;
		BT = Q->Data[Q->front];
	}
	return BT;
}

//二叉树的初始化
BinTree* InitTree(BinTree* Tree){

		Tree = (BinTree*)malloc(sizeof(BinTree));
		if(!Tree){
			printf("no enough memory\n");
			exit(-1);
		}
		else{
			Tree->Rchild = NULL;
			Tree->Lchild = NULL;
			return Tree;
		}
}

//判断队列是否为空
int IsEmpty(Queue* Q){
	if(Q->front == Q->rear){
		return 0;
	}
	else{
		return 1;
	}
}

//二叉树的初始化
BinTree* CreateTree(){
	BinTree *BT,*T;
	Queue* Q;
	ElementType data;

	Q = CreateQ(Q);
	scanf("%c",&data);
	if(data){
		BT = (BinTree*)malloc(sizeof(BinTree));
		if(!BT){
			printf("no enough memory\n");
			exit(-1);
		}
			BT->Data = data;
			Add(Q,BT);
	}
		else{
			return NULL;
		}
		while(IsEmpty(Q)){
			T = DeleteQ(Q);
			scanf("%c",&data);
			if(data == '0'){
				T->Lchild = NULL;
			}
			else{
				T->Lchild = (BinTree*)malloc(sizeof(BinTree));
				T->Lchild->Data = data;
				Add(Q,T->Lchild);
			}
			scanf("%c",&data);
			if(data == '0'){
				T->Rchild = NULL;
			}
			else{
				T->Rchild = (BinTree*)malloc(sizeof(BinTree));
				T->Rchild->Data = data;
				Add(Q,T->Rchild);
			}
		}
		return BT;
}


//前序遍历二叉树
void PreOrder(BinTree* BT){

	if(BT){
		printf("%c ",BT->Data);
		PreOrder(BT->Lchild);
		PreOrder(BT->Rchild);
	}
}


//中序遍历二叉树
void InOrder(BinTree* BT){

	if(BT){
		PreOrder(BT->Lchild);
		printf("%c ",BT->Data);
		PreOrder(BT->Rchild);
	}
}

//主函数
int main(int argc,char* argv[]){

	ElementType data;
	BinTree* Tree;

	Tree = CreateTree();
	PreOrder(Tree);
	printf("\n");
	InOrder(Tree);
	
		return 0;
}

大家都知道很多关于二叉树操作的知识，包括遍历，查找，增删等等。

那如何建立二叉树关心的较少，文中通过队列的形式来创建一个二叉树。

代码的主要结构来源于，浙江大学陈越老师的《数据结构》

若有侵权，立即删除。