首页 / 算法 / 23 二叉树层序创建,遍历,二叉树队列
23 二叉树层序创建,遍历,二叉树队列
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了23 二叉树层序创建,遍历,二叉树队列,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3795字,纯文字阅读大概需要6分钟。
内容图文
![23 二叉树层序创建,遍历,二叉树队列](/upload/InfoBanner/zyjiaocheng/1099/6e11869e21f34a089da526e3f1be19f0.jpg)
// #include "Header.h" #include <stdio.h> #include <stdbool.h> #include <stdlib.h> //exit 函数需要 #include <malloc.h> #define MAXSIZE 20 //队列长度#define NOINFO -1 //输入-1 结点为空//定义二叉树 typedef struct node { int data; struct node* L; struct node* R; }Tnode, * BTree; //定义队列结点 typedef struct QNode { BTree data; struct QNode* next; }Qnode, * PQnode; //定义队列 typedef struct Qnode { PQnode front;//队头指针 PQnode rear;//队尾指针int size; }LinkQuene, * Q; //链表队列函数原型void Initqueue(Q queue); bool enqueue(Q queue, BTree BT); //入队 BTree dequeue(Q queue); //出队bool(QueueEmpty(queue)); //bool is_full(Q queue); //void show_queue(Q queue); //二叉树操作函数原型 BTree CreatBintree(void); void LevTraverse(BTree BT); void PreTraverse(BTree BT); //先序遍历,先根void InTraverse(BTree BT); //中序遍历,中根void PostTraverse(BTree BT); //后序遍历 main() { BTree BT; BT = CreatBintree(); LevTraverse(BT); PreTraverse(BT); //先序遍历 InTraverse( BT); //中序遍历 PostTraverse( BT); //后序遍历 LevTraverse( BT); } BTree CreatBintree(void) { intin; //二叉树结点,以int 为例 BTree BT; //二叉树结点,指针变量 BTree T; // 出队的结点,指针 LinkQuene Cr_queue; //定义队列结构变量 LinkQuene* Q = &Cr_queue; //取地址,用指针后面用Q传递方便 Initqueue(Q); //初始化队列 scanf_s("%d", &in); if (in != NOINFO) { //树根结点初始化 BT = (BTree)malloc(sizeof(Tnode)); //动态分配二叉树结点内存,返回指针类型,赋值给BT BT->data = in; BT->L = BT->R = NULL; //先把左右指针置空 enqueue(Q, BT); ////根结点放入队列 } elsereturn NULL; //如果第一个输入数据为 -1 ,二叉树为空, // 遍历时的很多地方判断条件就是根据这个空指针,创建树时,需输入多个-1while (!QueueEmpty(Q)) { //循环出队,出完了条件就非 T = dequeue(Q); scanf_s("%d", &in); if (in == NOINFO) T->L = NULL; //如果输入-1 ,左儿子没有,下面的if就不会申请内存else { T->L = (BTree)malloc(sizeof(struct node)); T->L->data = in; T->L->L = T->L->R = NULL; enqueue(Q, T->L); } scanf_s("%d", &in); if (in == NOINFO) T->R = NULL; //如果输入-1 ,右儿子没有else { T->R = (BTree)malloc(sizeof(struct node)); T->R->data = in; T->R->L = T->R->R = NULL; enqueue(Q, T->R); } } return BT; } void LevTraverse(BTree BT) { BTree T; LinkQuene Lev_queue; //定义队列 LinkQuene* Q = &Lev_queue; if (!BT) printf("BTree is empty!"); if (BT) { Initqueue(Q); //队列初始化 enqueue(Q, BT); //入队while (!QueueEmpty(Q)) { T = dequeue(Q); //出队 printf("%d ", T->data); if (T->L) enqueue(Q, T->L); //如果有左儿子,左儿子入队if (T->R) enqueue(Q, T->R); } } } void PreTraverse(BTree BT) { if (BT) printf("BTree is empty!"); else { if (BT) { printf("%d", BT->data); //先输出,然后不断向左递归 PreTraverse(BT->L); PreTraverse(BT->R); } } } void PostTraverse(BTree BT) { if (BT) printf("BTree is empty!"); else { if (BT) { PreTraverse(BT->L); PreTraverse(BT->R); printf("%d", BT->data); } } } void InTraverse(BTree BT) { if (BT) printf("BTree is empty!"); else { if (BT) { PreTraverse(BT->L); printf("%d", BT->data); PreTraverse(BT->R); } } } void Initqueue(Q queue) { queue->front = NULL; queue->rear = NULL; queue->size = 0; } bool enqueue(Q queue, const BTree BT) { PQnode node; //创建队列结点 node = (PQnode)malloc(sizeof(LinkQuene)); //申请队列结点内存if (node == NULL) exit(-1); node->data = BT; //二叉树结点 放入队列结点,都不是指针 node->next = NULL; if (QueueEmpty(queue)) //初始状态 { queue->front = node; queue->rear = node; } else { queue->rear->next = node; //后面结点的连上 queue->rear = node; //rear 指向新结点 } ++queue->size; //可以设置队列长度return1; } BTree dequeue(Q queue) { //出队,返回出点的树结点 BTree BT; PQnode tmp; if (QueueEmpty(queue)) { return0; } tmp = queue->front; // TEMP 指针指向队头 BT = queue->front->data; //队头数据给BT queue->front = queue->front->next; //front指针后移free(tmp); //释放内存 --queue->size; return BT; } bool(QueueEmpty(Q queue)) { if (queue->size == 0) return1; elsereturn0; } //下面的函数就不写了 //bool is_full(Q queue) { //} //void show_queue(Q queue) { //}
原文:https://www.cnblogs.com/abel2020/p/13058137.html
内容总结
以上是互联网集市为您收集整理的23 二叉树层序创建,遍历,二叉树队列全部内容,希望文章能够帮你解决23 二叉树层序创建,遍历,二叉树队列所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。