【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing @163.com】
在二叉树的遍历当中,有一种遍历方法是不常见的,那就是广度遍历。和其他三种遍历方法不同,二叉树的广度遍历需要额外的数据结构来帮助一下?什么数据结构呢?那就是队列。因为队列具有先进先出的特点,这个特点要求我们在遍历新的一层数据之前,必须对上一次的数据全部遍历结束。暂时还没有掌握队列知识的朋友可以看一看我的这一篇博客—队列。
a)下面是新添加的队列数据结构,其中数据部分换成了树节点指针的指针:
typedef struct _QUEUE
{
int head;
int tail;
int length;
TREE_NODE** pHead;
}QUEUE;
注:head表示开始,tail表示结束,length表示pHead的长度,pHead表示指针的起始地址
b)创建队列,因为涉及到length的长度问题,所以需要计算二叉树中节点的总数
QUEUE* create_queue_for_tree(const TREE_NODE* pTreeNode)
{
QUEUE* pQueue;
int count;
if(NULL == pTreeNode)
return NULL;
count = count_all_node_number(pTreeNode);
pQueue = (QUEUE*)malloc(sizeof(QUEUE));
assert(NULL != pQueue);
memset(pQueue, 0, sizeof(QUEUE));
pQueue->pHead = (TREE_NODE**)malloc(sizeof(TREE_NODE*)* count);
assert(NULL != pQueue->pHead);
memset(pQueue->pHead, 0, sizeof(TREE_NODE*) * count);
pQueue->head = pQueue->tail = 0;
pQueue->length = count;
return pQueue;
}
c)实现队列的数据加入和数据弹出操作
void insert_node_into_queue(QUEUE* pQueue, TREE_NODE* pNode)
{
if(NULL == pQueue || NULL == pQueue->pHead ||NULL == pNode)
return;
pQueue->pHead[pQueue->tail ++] = pNode;
return;
}
TREE_NODE* get_node_from_queue(QUEUE* pQueue)
{
if(NULL == pQueue || NULL == pQueue->pHead)
return NULL;
if(pQueue->head == pQueue->tail)
return NULL;
return pQueue->pHead[pQueue->head++];
}
注:这里定义的队列不是循环队列,所以数据的压入和弹出比较简单,直接对head和tail处理即可
d)遍历节点,按层得到数据,最后再pQueue->pHead中得到的指针数据就是按层输出的结果
QUEUE* traverse_node_by_layer(TREE_NODE* pNode)
{
QUEUE* pQueue;
if(NULL ==pNode)
return NULL;
pQueue = create_queue_for_tree(pNode);
assert(NULL != pQueue);
/* 首个节点加入队列 */
insert_node_into_queue(pQueue, pNode);
pNode = get_node_from_queue(pQueue);
while(pNode){
if(pNode->left)
insert_node_into_queue(pQueue, pNode->left);
if(pNode->right)
insert_node_into_queue(pQueue, pNode->right);
pNode = get_node_from_queue(pQueue);
}
return pQueue;
}
扩充部分:
上面的办法已经可以实现队列的按层输出,那么如果想在节点结构中直接实现数据的按层访问怎么办?其实两步走就可以:1)在已有的TREE_NODE添加prev和next;(2)按照刚才得到的pQueue->pHead结果,依次对prev和next进行赋值即可。不知道朋友们明白了没?
分享到:
相关推荐
二叉树广度和深度优先遍历,通过递归算法实现二叉树的建立,利用递归算法实现深度优先遍历,使用队列实现广度优先遍历
前序遍历 中序遍历 后序遍历 深度遍历 广度遍历 插入排序 选择排序 冒泡排序 快速排序 堆排序 希尔排序 合并排序 快速3排序
二叉树的深度优先搜索与广度优先搜索的非递归方法实现
二叉树 非递归实现 数据结构 c++ 广度遍历,非递归实现广度遍历生成二叉树。 数据结构与算法上机作业。
二叉树前序,中序,后序的递归与非递归算法。
给定一个二叉树的数据结构,通过JavaScript实现二叉树的广度遍历和深度遍历。
算法-数据结构和算法-17-二叉树的广度优先遍历和二叉树节点插入操作.rar
主要介绍了Java实现二叉树的深度优先遍历和广度优先遍历算法,结合实例形式详细分析了二叉树的定义、深度优先遍历与广度优先遍历算法原理与相关操作实现技巧,需要的朋友可以参考下
js代码-(算法)(二叉树)广度遍历
算法-二叉树的深度优先和广度优先遍历(包含源程序).rar
深度优先遍历算法之二叉树一、什么是深度优先遍历二、二叉树1. 二叉树简介2.二叉树类型3.二叉树相关术语4. 二叉树的节点代码5. 二叉树遍历顺序6.深度优先遍历和广度优先遍历三、面试题+励志 这不就是二叉树吗?嗯,...
一个很全面的二叉树遍历算法,其中包括递归,非递归,广度遍历,输入,输出。
二叉树的遍历:二叉树的各种遍历 图的遍历:图的深度遍历,广度遍历 一元多项式的相关设计: 停车场的课程设计(堆栈和队列的使用,停车出车) 迷宫的递归算法(需要修改)
React App会显示遍历,例如二叉树的有序,前序,后序和广度优先遍历。 建立在ReactJs之上 设置步骤: git clone cd BinaryTree遍历 npm安装 npm开始 浏览到htpp:// localhost:3000 登陆页面 包含一棵静态树。 ...
在Python中遍历二叉树可以使用不同的遍历算法,包括深度优先搜索(DFS)和广度优先搜索(BFS)
常用的数据结构的算法,包括二叉树的三种递归和非递归算法,染色问题,八皇后问题,深度广度遍历,约瑟夫环,数值转换,树的高度和叶子节点数,最小生成树 ,两点之间的所有路径
主要介绍了Java中二叉树的建立和各种遍历实例代码,涉及树节点的定义,后序遍历,层序遍历,深度优先和广度优先等相关内容,具有一定借鉴价值,需要的朋友可以参考下
这篇文章主要在JS中实现二叉树的遍历。 一个二叉树的例子 var tree = { value: 1, left: { value: 2, left: { value: 4 } }, right: { value: 3, left: { value: 5, left: { value: 7 }, right: { ...
本文实例讲述了C++非递归队列实现二叉树的广度优先遍历。分享给大家供大家参考。具体如下: 广度优先非递归二叉树遍历(或者说层次遍历): void widthFirstTraverse(TNode* root) { queue<TNode> q; // 队列 q....