您的位置 首页 java

二叉树的层序遍历及应用

二叉树 的遍历实质问题就是,将二维结构线性化。

深度优先遍历对应的是前序、中序、后续遍历;广度优先对应的是层序遍历。

今天深入学习一下层序遍历,层序遍历也是面试中出现频率较多的一个知识点。

如下二叉树,它的层序遍历结果为:1 – 2 – 5 – 3 – 4 – 6

二叉树

我们用队列对它进行层序遍历:

用队列进行层序遍历过程

得出层序遍历的基本过程如下:

  1. 把根节点放入队列中
  2. 从队列中取出一个元素
  3. 访问该元素所有节点
  4. 若该元素左右节点非空,则将其左右节点顺序入队列

用C++和 Python 实现层序遍历的基本过程:

C++:

void leverOrder(pTree node &Tree)

{

queue<pTreeNode> q;

if(Tree != NULL)

{

q. push (Tree);//root 进队列

}

while(q.empty() == false )

{

q.pop();//已经遍历郭的队列元素出队列

cout << q.front()->data<<“->”;//输出遍历结果

if(q.front()->leftPtr != NULL)

{//如果有左孩子,左孩子入队列

q.push(q.front()->leftPtr);

}

if(q.front()->rightPtr != NULL)

{//如果有右孩子,右孩子入队列

q.push(q.front()->rightPtr);

}

}

}

Python:

from collections import deque

#导入双向队列

class BTree( object ):

#定义二叉树

def __init__(self):

self._root = None

self._size = 0

def leverOrder(self):

#创建一个队列

q = deque()

#root加入队列

q.append(self._root)

btree = []

#队列不空

while q:

#队列头出队列

node = q.popleft()

#输出列表,追加

btree.append(node.data)

#如果有左孩子,左孩子入队列

if node.lft:

q.append(node.lft)

#如果有右孩子,右孩子入队列

if node.rgt:

q.append(node.rgt)

return btree

层序遍历的应用:

  1. 可以用来求二叉树的高度和宽度
  2. 判断二叉树是否为完全二叉树

层序遍历应用场景丰富,很受面试官青睐。

文章来源:智云一二三科技

文章标题:二叉树的层序遍历及应用

文章地址:https://www.zhihuclub.com/197798.shtml

关于作者: 智云科技

热门文章

发表回复

您的电子邮箱地址不会被公开。

网站地图