数据结构 第12讲 二叉树的层次遍历

数据结构第12讲二叉树的层次遍历

二叉树的遍历一般有先序遍历、中序遍历和后序遍历,这三种遍历比较简单。今天我们讲二叉树的另一种遍历方式,层次遍历。即按照层次进行遍历。如图1所示:

图1二叉树

对图1的二叉树,进行层次遍历:首先搜索第1层A,然后搜索第2层,从左向右B、C,再搜索第3层,从左向右D、E、F,再搜索第4层G,很简单吧,这就是层次遍历。

程序是怎么实现层次遍历呢?用队列噢,很多同学觉得数据结构没什么用,其实数据结构就像我们小学时学的九九乘法表,你有时根本感觉不到它的存在,但却无时不刻都在用!

首先创建一个队列Q:

        1.令树根入队,如图2所示。(注意:实际上是指向树根A的指针入队,这里为了图解方便,把数据入队了)

图2层次遍历队列1

注意:实际上是指向树根A的指针入队,这里为了图解方便,把数据入队了)

2. 队头元素出队,输出A,同时令A的孩子(从左向右顺序,如果是普通树,则包含所有孩子)入队。如图3、4所示。

图3层次遍历队列2

图4二叉树层次遍历过程1

           3. 队头元素出队,输出B,同时令B的孩子D、E入队。如图5、6所示。

图5层次遍历队列3

图6二叉树层次遍历过程2

4. 队头元素出队,输出C,同时令C的孩子F入队。如图7、8所示。

图7层次遍历队列4

图8二叉树层次遍历过程3

5. 队头元素出队,输出D,同时令D的孩子入队,D没有孩子,什么也不做。如图9、10所示。

图9层次遍历队列5

图10二叉树层次遍历过程4

6. 队头元素出队,输出E,同时令E的孩子入队,E没有孩子,什么也不做。如图11、12所示。

图11层次遍历队列6

图12二叉树层次遍历过程5

7.队头元素出队,输出F,同时令F的孩子G入队。如图13、14所示。

图13层次遍历队列7

图14二叉树层次遍历过程6

8. 队头元素出队,输出G,同时令G的孩子入队, G没有孩子,什么也不做。。如图15、16所示。

图15层次遍历队列8

图16二叉树层次遍历过程7

9. 队列为空,算法结束。

算法实现: 1.首先输入一个先序序列字符串,创建一棵二叉树。   在先序序列中,孩子为空时为"#"号。

  •    如图17所示:

图17二叉树

那么图17中二叉树的先序遍历结果为:ABD##E##CF#G###

调用先序创建二叉树程序,创建二叉树。

2.调用层次遍历函数,对该二叉树进行层次遍历。

运行结果:

按先序次序输入二叉树中结点的值(孩子为空时输入#),创建一棵二叉树

ABD##E##CF#G###

二叉树的层次遍历结果:

A B C D E F G

源码:

#include <iostream>
#include <queue>  //引入队列头文件
using namespace std;

typedef struct Bnode	/*定义二叉树存储结构*/
{ char data;
  struct Bnode *lchild,*rchild;
}Bnode,*Btree;

void Createtree(Btree &T)	/*创建二叉树函数*/
{
    //按先序次序输入二叉树中结点的值(一个字符),创建二叉链表表示的二叉树T
	char ch;
	cin >> ch;
	if(ch=='#')
        T=NULL;			//递归结束,建空树
	else{
		T=new Bnode;
		T->data=ch;					//生成根结点
		Createtree(T->lchild);	//递归创建左子树
		Createtree(T->rchild);	//递归创建右子树
	}
    return;
}

bool Leveltraverse(Btree T)
{
    Btree p;
    if(!T)
        return false;
    queue<Btree>Q; //创建一个普通队列(先进先出),里面存放指针类型
    Q.push(T); //根指针入队
    while(!Q.empty()) //如果队列不空
    {
        p=Q.front();//取出队头元素
        Q.pop(); //队头元素出队
        cout<<p->data<<"\t";
        if(p->lchild)
            Q.push(p->lchild); //左孩子指针入队
        if(p->rchild)
            Q.push(p->rchild); //右孩子指针入队
    }
    return true;
}

int main()
{
    Btree mytree;
    cout<<"按先序次序输入二叉树中结点的值(孩子为空时输入#),创建一棵二叉树"<<endl;
    Createtree(mytree);//创建二叉树
    cout<<endl;
    cout<<"二叉树的层次遍历结果:"<<endl;
    Leveltraverse(mytree);//层次遍历二叉树
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏一名叫大蕉的程序员

大数据计数原理1+0=1这你都不会算(四)No.52

这是本坑的第四篇,之前已经说了关于 HashSet 、BitMap 、Bloom Filter 布隆过滤器了,本篇主要讲B-树。要是还不知道前面讲了啥的,可以点...

2117
来自专栏大闲人柴毛毛

剑指offer代码分析——面试题13在O(1)内删除链表结点

本题详细解析都已在代码中注释了: /** * 给一个单链表,头指针为first,请用O(1)时间删除其中节点p * @author chibozhou *...

3765
来自专栏数据处理

236. Lowest Common Ancestor of a Binary Tree

1725
来自专栏计算机视觉与深度学习基础

Leetcode 34 Search for a Range

Given a sorted array of integers, find the starting and ending position of a gi...

2149
来自专栏尾尾部落

[剑指offer] 按之字形顺序打印二叉树

请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。

912
来自专栏数据结构与算法

Day2平衡树笔记

线段树不支持的操作:删除,插入 ---- 常见的平衡树 treap 慢||好写 sbt(大小平衡的树) 非常快 比较好写 ||功能不全 rbt 红黑树 特...

3266
来自专栏拂晓风起

java LinkedList ArrayList 随机访问效率 list.get(int index)

1085
来自专栏开发 & 算法杂谈

PAT Advanced 1043

A Binary Search Tree (BST) is recursively defined as a binary tree which has th...

903
来自专栏猿人谷

顺序线性表

线性表的顺序表示和实现 线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。 线性表的第一个数据元素a1的存储位置,通常称作线性表的起始位置...

2325
来自专栏WindCoder

数据统计第一弹-按时/天/周/月补全某一段时间的数据-Java核心逻辑

本代码均结合之前的发布的DateUtil使用,之后的mysql查询部分看心情发布,就这么任性~ ~

1321

扫码关注云+社区

领取腾讯云代金券