二叉树的层次遍历是指从二叉树的第一层(根节点)开始,从上至下逐层遍历,在同一层中,则按照从左到右的顺序对节点逐个访问。在逐层遍历过程中,按从顶层到底层的次序访问树中元素,在同一层中,从左到右进行访问。
其思想为:用一个队列保存被访问的当前节点的左右孩子以实现层序遍历。在进行层次遍历的时候,设置一个队列结构,遍历从二叉树的根节点开始,首先将根节点指针入队列,然后从队头取出一个元素,每取一个元素,执行下面两个操作:
1、访问该元素所指向的节点。
2、若该元素所指节点的左右孩子节点非空,则将该元素所指节点的左孩子指针和右孩子指针顺序入队。此过程不断进行,当队列为空时,二叉树的层次遍历结束。
扩展资料
由于遍历中所使用的数据结构是一个队列而不是栈,因此写一个按层遍历的递归程序很困难。如下程序用来对二叉树进行逐层遍历,它采用了队列数据结构。队列中的元素指向二叉树节点。当然,也可以采用公式化队列。
程序中,仅当树非空时,才进入w h i l e循环。首先访问根节点,然后把其子节点加到队列中。当队列添加操作失败时,由Add引发NoMem异常,由于没有捕获该异常,因此当异常发生时函数将退出。在把t的子节点加入队列后,要从队列中删除t元素。
参考资料来源:百度百科-逐层遍历
就是按层(深度)遍历整棵树。
如果层次遍历这棵树,得到的序列就是12345678,遍历时因为要一层一层的下来,所以一般用广度优先遍历。
遍历是对树的一种最基本的运算,所谓遍历二叉树,就是按一定的规则和顺序走遍二叉树的所有结点,使每一个结点都被访问一次,而且只被访问一次。由于二叉树是非线性结构,因此,树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。
设L、D、R分别表示遍历左子树、访问根结点和遍历右子树, 则对一棵二叉树的遍历有三种情况:DLR(称为先根次序遍历),LDR(称为中根次序遍历),LRD (称为后根次序遍历)。
扩展资料:
二叉树是一个连通的无环图,并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点之后,每个顶点定义了唯一的父结点,和最多2个子结点。然而,没有足够的信息来区分左结点和右结点。如果不考虑连通性,允许图中有多个连通分量。
给定N个节点,能构成h(N)种不同的二叉树。h(N)为卡特兰数的第N项。h(n)=C(2*n,n)/(n+1)。
设有i个枝点,I为所有枝点的道路长度总和,J为叶的道路长度总和J=I+2i。
参考资料来源:百度百科——二叉树
本回答被网友采纳