二叉树的层次遍历算法
层次遍历从方法上不具有递归的形式，所以一般不用递归实现。当然了，非要写成递归肯定也是可以的，大致方法如下。 void LevelOrder(BTree T, int cnt) { BTree level = malloc(sizeof(struct BTNode)*cnt); if(level==NULL) return; int i=0,rear=0; if(cnt==0) return; for(i=0; i<cnt; i++){ printf("%c ",T[i].data); if(T[i].lchild) level[rear++]=*T[i].lchild; if(T[i].rchild) level[rear++]=*T[i].rchild; } printf("
"); LevelOrder(level, rear); free(level); } 补充一下，在main里面调用的时候就得用LevelOrder(T,1)了。
#include
#include
typedef char datatype;
typedef struct node
{datatype data;
struct node *lchild,*rchild;
}bitree;
bitree *Q[100];
bitree *creat()
{
bitree *root,*s;
int front,rear;
root=NULL;
char ch;
front=1;rear=0;
ch=getchar();
while(ch!='0')
{
s=NULL;
if(ch!='@')
{s=(bitree *)malloc(sizeof(bitree));
s->data=ch;
s->lchild=NULL;
s->rchild=NULL;
}
rear++;
Q[rear]=s;
if(rear==1)
root=s;
else
{
if(s&&Q[front])
if(rear%2==0)
Q[front]->lchild=s;
else
Q[front]->rchild=s;
if(rear%2==1)
front++;
}
ch=getchar();
}
return root;
}
void cengci(bitree *t)
{
bitree *Queue[100],*p;
int front=0,rear=0;
if(t)
{
p=t;
Queue[rear]=p;
rear=(rear+1)%20;
while(front!=rear)
{
p=Queue[front];
printf("%c",p->data);
front=(front+1)%100;
if(p->lchild)
{
Queue[rear]=p->lchild;
rear=(rear+1)%100;
}
if(p->rchild)
{
Queue[rear]=p->rchild;
rear=(rear+1)%20;
}
}
}
}
void main()
{struct node *tree;
tree=(bitree *)malloc(sizeof(bitree));
tree=creat();
cengci(tree);
}
二叉树的层次遍历算法有如下三种方法：
给定一棵二叉树，要求进行分层遍历，每层的节点值单独打印一行，下图给出事例结构：
对此二叉树遍历的结果应该是：
1，
2 ， 3
4， 5， 6
7， 8
第一种方法，就是利用递归的方法，按层进行打印，我们把根节点当做第0层，之后层次依次增加，如果我们想打印第二层怎么办呢，利用递归的代码如下：
[cpp] view plaincopy
int print_at_level(Tree T, int level) {
if (!T || level < 0)
return 0;
if (0 == level) {
cout << T->data << " ";
return 1;
}
return print_at_level(T->lchild, level - 1) + print_at_level(T->rchild, level - 1);
如果我们成功的打印了给定的层次，那么就返回非0的正值，如果失败返回0。有了这个思路，我们就可以应用一个循环，来打印这颗树的所有层的节点，但是有个问题就是我们不知道这棵二叉树的深度，怎么来控制循环使其结束呢，仔细看一下print_at_level，如果指定的Tree是空的，那么就直接返回0，当返回0的时候，我们就结束循环，说明没有节点可以打印了。
[cpp] view plaincopy
void print_by_level_1(Tree T) {
int i = 0;
for (i = 0; ; i++) {
if (!print_at_level(T, i))
break;
}
cout << endl;
}
以上的方法可以很清楚的看出，存在重复访问的情况，就是第0层访问的次数最多，第1层次之。所以这个递归的方法不是很有效的方法。
第二种方法：我们可以设置两个队列，想象一下队列的特点，就是先进先出，首先把第0层保存在一个队列中，然后按节点访问，并把已经访问节点的左右孩子节点放在第二个队列中，当第一个队列中的所有节点都访问完成之后，交换两个节点。这样重复下去，知道所有层的节点都被访问，这样做的代价就是空间复杂度有点高。
[cpp] view plaincopy
void print_by_level_2(Tree T) {
deque<tree_node_t*> q_first, q_second;
q_first.push_back(T);
while(!q_first.empty()) {
while (!q_first.empty()) {
tree_node_t *temp = q_first.front();
q_first.pop_front();
cout << temp->data << " ";
if (temp->lchild)
q_second.push_back(temp->lchild);
if (temp->rchild)
q_second.push_back(temp->rchild);
}
cout << endl;
q_first.swap(q_second);
}
}
第三种方法就是设置双指针，一个指向访问当层开始的节点，一个指向访问当层结束节点的下一个位置：
这是第一层访问的情况，当访问第0层之后的结构如下，把第0层的所有子节点加入之后：
访问完第1层之后：
之后大家就可以自己画图了，下面给出程序代码：
[cpp] view plaincopy
void print_by_level_3(Tree T) {
vector<tree_node_t*> vec;
vec.push_back(T);
int cur = 0;
int end = 1;
while (cur < vec.size()) {
end = vec.size();
while (cur < end) {
cout << vec[cur]->data << " ";
if (vec[cur]->lchild)
vec.push_back(vec[cur]->lchild);
if (vec[cur]->rchild)
vec.push_back(vec[cur]->rchild);
cur++;
}
cout << endl;
}
}
最后给出完成代码的测试用例：124##57##8##3#6##
[cpp] view plaincopy
#include<iostream>
#include<vector>
#include<deque>
using namespace std;
typedef struct tree_node_s {
char data;
struct tree_node_s *lchild;
struct tree_node_s *rchild;
}tree_node_t, *Tree;
void create_tree(Tree *T) {
char c = getchar();
if (c == '#') {
*T = NULL;
} else {
*T = (tree_node_t*)malloc(sizeof(tree_node_t));
(*T)->data = c;
create_tree(&(*T)->lchild);
create_tree(&(*T)->rchild);
}
}
void print_tree(Tree T) {
if (T) {
cout << T->data << " ";
print_tree(T->lchild);
print_tree(T->rchild);
}
}
int print_at_level(Tree T, int level) {
if (!T || level < 0)
return 0;
if (0 == level) {
cout << T->data << " ";
return 1;
}
return print_at_level(T->lchild, level - 1) + print_at_level(T->rchild, level - 1);
}
void print_by_level_1(Tree T) {
int i = 0;
for (i = 0; ; i++) {
if (!print_at_level(T, i))
break;
}
cout << endl;
}
void print_by_level_2(Tree T) {
deque<tree_node_t*> q_first, q_second;
q_first.push_back(T);
while(!q_first.empty()) {
while (!q_first.empty()) {
tree_node_t *temp = q_first.front();
q_first.pop_front();
cout << temp->data << " ";
if (temp->lchild)
q_second.push_back(temp->lchild);
if (temp->rchild)
q_second.push_back(temp->rchild);
}
cout << endl;
q_first.swap(q_second);
}
}
void print_by_level_3(Tree T) {
vector<tree_node_t*> vec;
vec.push_back(T);
int cur = 0;
int end = 1;
while (cur < vec.size()) {
end = vec.size();
while (cur < end) {
cout << vec[cur]->data << " ";
if (vec[cur]->lchild)
vec.push_back(vec[cur]->lchild);
if (vec[cur]->rchild)
vec.push_back(vec[cur]->rchild);
cur++;
}
cout << endl;
}
}
int main(int argc, char *argv[]) {
Tree T = NULL;
create_tree(&T);
print_tree(T);
cout << endl;
print_by_level_3(T);
cin.get();
cin.get();
return 0;
}
创建一个队列q;
将根放入队列;
while(队列非空)
{
从队列取出一个元素并访问;
如果该元素有右子树就将它放入队列;
如果该元素有左子树就将它放入队列;
}
二叉树序列中的“层序序列”是什么?
首先 中序遍历(即“中序序列” 应该叫遍历正规点吧) 就是LDR(左根右 以下简称“LDR”)层序遍历上面解释了 就是按层次来遍历的 然后 先看 层序遍历“bafegcd” 由此可知 B在最前面 即B是整个二叉树的根结点 咱可以把 中序遍历“abcdefg"根据LDR分为三份： A (左) B(根) CDEFG(右)因...
二叉树中序遍历为bafdgce 层次遍历为abcdefg 则后续遍历为? 怎么个确 ...
后续遍历为 ：bfgdeca 层序遍历二叉树（同一层从左到右访问）中序遍历也叫做中根遍历，可记做左根右。中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结点，最后遍历右子树。根据层次遍历 首先确定根节点 a，左孩子：b，右孩子 c；然后...
二叉树的深度遍历和广度遍历
解决方案 从根节点开始，沿着树的宽度遍历树的节点，直到所有节点都被遍历完为止。因为是按照一层一层遍历的，所以我们考虑引入 队列 这个数据结构帮助我们实现广度优先搜索算法。给出一棵二叉树，返回其节点值 从底向上 的层次序遍历 解决方法：和上面的实现方式类似，只是最后需要把容器翻转过来。
数据结构二叉树遍历方式学生收藏
后序遍历就像是剪葡萄,我们要把一串葡萄剪成一颗一颗的。围着树的外围绕一圈,如果发现一剪刀就能剪下的葡萄(必须是一颗葡萄)(也就是葡萄要一个一个掉下来,不能一口气掉超过1个),就把它剪下来,组成的就是后序遍历了。 巧记:左右根 后序遍历结果:HIDJEBKFGCA 层次遍历 层次遍历很好理解,就是从根节点开始,一...
树和二叉树
遍历二叉树 ：是指按 某种次序访问 二叉树上的所有结点，使每个结点被 访问一次 且仅被访问一次。先序遍历，DLR ：根 -> 左子树 -> 右子树 中序遍历，LDR ：左子树 -> 根 -> 右子树 后序遍历，LRD ：左子树 -> 右子树 -> 根 二叉树的层次遍历 ：从二叉树的 根结点 的这一...
...它的中序遍历序列是BGDHAEICF,请给出其层次遍历序列.
根据先序遍历和中序遍历，我们可以将这颗二叉树画出来，如下图。所以，根据图片，得出层次遍历序列为：ABCDEFGHI。
在二叉树结点的先序序列、中序序列和后序序列中,所有叶子结点的先后顺序...
二叉树的其他遍历方式：1、层次遍历：层次遍历是一种按照树的层次从上到下、从左到右进行遍历的方式。这种遍历方式通常使用队列来实现。首先将根结点入队，然后按照队列的先进先出原则，逐层遍历树的结点。每遍历一层，从队列中出队一个结点，访问它，并将其左右子节点入队。直到队列为空，表示所有结点...
已知二叉树的前序和中序后序 怎么用c求它的层次遍历
依据划分出的两个序列，在前序序列中找到这两个序列（按照中序中序列的元素个数即可划分）对划分后的先序序列继续1,2，3两步（要平行进行不能处理完一个序列再处理另一个序列）直到遍历全部元素，此时得到的序列即为层次遍历序列。例如：先序ABDECFG，中序DBEAFCG 按照算法：输出先序第一个元素A 依...
已知一棵二叉树的先序遍历序列为ABDGHCEIF,它的中序遍历序列是BGDHAEI...
根据先序遍历和中序遍历，我们可以将这颗二叉树画出来，如下图。所以，根据图片，得出层次遍历序列为：ABCDEFGHI。
二叉树的遍历
对任意给定的二叉树(顶点数自定)建立它的二叉链表存储结构,并利用栈的五种基本运算(置空栈、进栈、出栈、取栈顶元素、判栈空)实现二叉树的先序、中序、后序三种遍历,输出三种遍... 对任意给定的二叉树(顶点数自定)建立它的二叉链表存储结构,并利用栈的五种基本运算(置空栈、进栈、出栈、取栈顶元素、判...
嵇差复方： #include typedef char datatype; typedef struct node {datatype data; struct node *lchild,*rchild; }bitree; bitree *Q[100]; bitree *creat() { bitree *root,*s; int front,rear; root=NULL; char ch; front=1;rear=0; ch=getchar(); while(ch!='0') { s=NULL; if(ch!='@') {s=(...
上思县13522934832： 二叉树的层次遍历 - ？
嵇差复方： 设计一个算法层序遍历二叉树(同一层从左到右访问).思想:用一个队列保存被访问的当前节点的左右孩子以实现层序遍历. void HierarchyBiTree(BiTree Root){ LinkQueue *Q; // 保存当前节点的左右孩子的队列 InitQueue(Q); // 初始化队列 ...
上思县13522934832： 二叉树的分层遍历的算法流程是什么? - ？
嵇差复方： 1. 首先将根结点入队列2. 若队列不为空则进行出队操作,否则遍历结束3. 将出队的对头结点的左结点和右结点入队列4. 按照需要输出对头结点的数据5. 返回到2继续执行 流程图就不画了,我这边不方便画图,有上面的步骤实际上流程图已经很清晰了,大致如下: [开始] [根节点入队] -----------------> --是-->[结束]| 否 | [出队] | [出队结点的左右子结点入队] | [处理或输出出队结点的数据] -----------------------|
上思县13522934832： 什么是二叉树的层次遍历 - ？
嵇差复方： 从第一行到第N行.依次遍历 比如:12 34 5 6 7 遍历结果是:1234567
上思县13522934832： 求一个按层次遍历二叉树的算法思路 - ？
嵇差复方： 广度优先遍历: 队列是先进先出的概念 所以使用于保存节点 2插树的话 1个节点有个2个子节点 你先将根节点入队,然后访问根节点数据(此时让根节点出队),然后将根节点2个子节点或一个子节点入队,同时访问2个子节点然后再让2个子节点的节点入队一次这样直到遇到null结束
上思县13522934832： 二叉树的层次遍历以及用层次遍历算法显示所有叶子节点 - ？
嵇差复方： #include using namespace std; struct segtree{int a,b;} tree[10001]; void buildtree(int l,int r,int root = 0) //建树 { tree[root].a=l; tree[root].b=r; if (l==r) return; int mid=(l+r)>>1; rootvoid dfs(int level,int root = 0){ for (int i=1;istruct {int root,level;} st[100001]; ...
上思县13522934832： 已知二叉树的前序和中序后序 怎么用c求它的层次遍历 - ？
嵇差复方： 可以不用建立二叉树. 使用两个队列A,B,A用来存放当前要遍历的层,B队列用来存放A队列那层的下一层(当然在实际编程中可以通过分割元素将AB放在一个队列中). 算法:1. 将前序遍历的第一个节点(根节点)加入队列A. 2. 如果队列A...
上思县13522934832： 二叉树 按层遍历 递归的算法 - ？
嵇差复方： 层次遍历从方法上不具有递归的形式,所以一般不用递归实现.当然了,非要写成递归肯定也是可以的,大致方法如下.void LevelOrder(BTree T, int cnt) { BTree level = malloc(sizeof(struct BTNode)*cnt); if(level==NULL) return; int i=0,rear=0; if(...
