三种树遍历方式是中序遍历、前序遍历和后序遍历。
第四种不常用的遍历方式是层序遍历。在层序遍历中，“深度d”的所有节点都会在“深度d+1”的任何节点之前被处理。与其他遍历方式不同的是，层序遍历不是递归完成的，而是使用队列来代替递归中隐含的栈。
由于层序遍历需要按照节点深度的顺序进行处理，所以无法使用递归完成。递归时需要先访问子节点再回溯到父节点，因此无法保证按照深度顺序进行处理。
使用队列可以轻松地实现层序遍历。具体步骤如下：
定义一个空队列
将根节点入队
while 队列不为空 do
从队列中取出首元素
处理该节点
将其子节点依次入队
end while
在这个过程中，我们首先将根节点入队，然后进入循环。每次从队列中取出首元素，处理该节点（例如打印节点值），然后将其子节点依次入队。由于队列的先进先出特性，我们可以保证按照深度顺序进行处理。
谢谢！
层次遍历实际上是一种非递归的广度优先搜索 （BFS）。它使用队列而不是栈来保存下一个应该打开的顶点。原因是在这种遍历中，您要以FIFO顺序而不是通过递归获得的LIFO顺序打开节点。
正如我提到的，层次遍历实际上是BFS，其[BFS]伪代码[取自维基百科]如下：
1 procedure BFS(Graph,source):
2 create a queue Q
3 enqueue source onto Q
4 mark source
5 while Q is not empty:
6 dequeue an item from Q into v
7 for each edge e incident on v in Graph:
8 let w be the other end of e
9 if w is not marked:
10 mark w
11 enqueue w onto Q
在树中，不需要对顶点进行标记，因为您不能通过2条不同的路径到达同一个节点。
void levelorder(Node *n)
{ queue < Node * >q;
q.push(n);
while(!q.empty())
{
Node *node = q.front();
cout<<node->value;
q.pop();
if(node->left != NULL)
q.push(node->left);
if (node->right != NULL)
q.push(node->right);
}
}
对于你的第一点，我们可以使用以下Java代码以递归顺序进行层次遍历。我们没有使用任何树库函数，所有的树和树特定函数都是用户定义的。
class Node
{
int data;
Node left, right;
public Node(int item)
{
data = item;
left = right = null;
}
boolean isLeaf() { return left == null ? right == null : false; }
}
public class BinaryTree {
Node root;
Queue<Node> nodeQueue = new ConcurrentLinkedDeque<>();
public BinaryTree() {
root = null;
}
public static void main(String args[]) {
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.left = new Node(6);
tree.root.right.right = new Node(7);
tree.root.right.left.left = new Node(8);
tree.root.right.left.right = new Node(9);
tree.printLevelOrder();
}
/*Level order traversal*/
void printLevelOrder() {
int h = height(root);
int i;
for (i = 1; i <= h; i++)
printGivenLevel(root, i);
System.out.println("\n");
}
void printGivenLevel(Node root, int level) {
if (root == null)
return;
if (level == 1)
System.out.print(root.data + " ");
else if (level > 1) {
printGivenLevel(root.left, level - 1);
printGivenLevel(root.right, level - 1);
}
}
/*Height of Binary tree*/
int height(Node root) {
if (root == null)
return 0;
else {
int lHeight = height(root.left);
int rHeight = height(root.right);
if (lHeight > rHeight)
return (lHeight + 1);
else return (rHeight + 1);
}
}
}
针对您的第二点，如果您想使用非递归函数，则可以使用以下函数作为队列 -
public void levelOrder_traversal_nrec(Node node){
System.out.println("Level order traversal !!! ");
if(node == null){
System.out.println("Tree is empty");
return;
}
nodeQueue.add(node);
while (!nodeQueue.isEmpty()){
node = nodeQueue.remove();
System.out.printf("%s ",node.data);
if(node.left !=null)
nodeQueue.add(node.left);
if (node.right !=null)
nodeQueue.add(node.right);
}
System.out.println("\n");
}
我使用了一个映射表来解决这个问题，而不是使用队列。当进行后序遍历时，我会维护每个节点所在的深度，并将该深度作为映射表中的键来收集同一层级的值。
class Solution {
public:
map<int, vector<int> > levelValues;
void recursivePrint(TreeNode *root, int depth){
if(root == NULL)
return;
if(levelValues.count(root->val) == 0)
levelValues.insert(make_pair(depth, vector<int>()));
levelValues[depth].push_back(root->val);
recursivePrint(root->left, depth+1);
recursivePrint(root->right, depth+1);
}
vector<vector<int> > levelOrder(TreeNode *root) {
recursivePrint(root, 1);
vector<vector<int> > result;
for(map<int,vector<int> >::iterator it = levelValues.begin(); it!= levelValues.end(); ++it){
result.push_back(it->second);
}
return result;
}
};
您可以在此处尝试解决 - https://oj.leetcode.com/problems/binary-tree-level-order-traversal/
而且，正如您所看到的，我们也可以以相同的时间和空间复杂度递归地完成这个解决方案！
我认为从第二个问题开始会更容易。一旦你理解了第二个问题的答案，你就能更好地理解第一个问题的答案。
我认为理解层序遍历的工作原理最好的方法是逐步执行，所以让我们这样做。
我们有一棵树。
让我们先将第一个节点A放入队列中。
好的，系好安全带。设置已经完成，我们即将开始深入探讨。
第一步是将 A 从队列中取出以便进行处理。但等等！在这样做之前，让我们也将 A 的 子节点，B 和 C，也放入队列中。
A实际上在这个时候已经不在队列中了。我将其变灰以尝试传达这一点。如果我完全从图表中删除它，那么后面的故事中发生的事情就会更难以想象。A正在由服务台的服务员处理。在现实生活中，处理节点可以意味着很多事情。例如使用它来计算总和、发送短信、记录到控制台等等。根据我图表中的比喻，您可以告诉服务员您希望他们如何处理该节点。B。A相同的事情：1）将子节点添加到队列中，2）处理该节点。
D。 D 没有子节点，因此我们不会将任何内容放在队列的末尾。我们只处理D。
然后对于E、F和G也是同样的处理。
想象一下，如果我们使用栈而不是队列会发生什么。 让我们倒回到我们刚刚访问A的那个点。
C，而不是B。C的子节点，然后处理C。这次我们只是将它们添加到堆栈中，而不是队列中。
G是下一个。s = new Stack()这样的栈数据结构。然而，运行时使用了调用栈。这最终在概念上类似于我上面做的事情，因此不能给我们从层次遍历中得到A B C D E F G的顺序。如需完整信息，请查看上述链接。
public void levelOrderTreeTraversal(List<Node<T>> nodes){
if(nodes == null || nodes.isEmpty()){
return;
}
List<Node<T>> levelNodes = new ArrayList<>();
nodes.stream().forEach(node -> {
if(node != null) {
System.out.print(" " + node.value);
levelNodes.add(node.left);
levelNodes.add(node.right);
}
});
System.out.println("");
levelOrderTreeTraversal(levelNodes);
}
还可以查看http://www.geeksforgeeks.org/
在这里，您将找到几乎所有与数据结构相关的答案。
C++中的递归解决方案
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> levels;
void helper(TreeNode* node,int level)
{
if(levels.size() == level) levels.push_back({});
levels[level].push_back(node->val);
if(node->left)
helper(node->left,level+1);
if(node->right)
helper(node->right,level+1);
}
vector<vector<int>> levelOrder(TreeNode* root) {
if(!root) return levels;
helper(root,0);
return levels;
}
};
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> levelOrderTraversal = new ArrayList<List<Integer>>();
List<Integer> currentLevel = new ArrayList<Integer>();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
if(root != null)
{
queue.add(root);
queue.add(null);
}
while(!queue.isEmpty())
{
TreeNode queueRoot = queue.poll();
if(queueRoot != null)
{
currentLevel.add(queueRoot.val);
if(queueRoot.left != null)
{
queue.add(queueRoot.left);
}
if(queueRoot.right != null)
{
queue.add(queueRoot.right);
}
}
else
{
levelOrderTraversal.add(currentLevel);
if(!queue.isEmpty())
{
currentLevel = new ArrayList<Integer>();
queue.add(null);
}
}
}
return levelOrderTraversal;
}
}
使用队列实现的层序遍历
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def levelOrder(root: TreeNode) -> List[List[int]]:
res = [] # store the node value
queue = [root]
while queue:
node = queue.pop()
# visit the node
res.append(node.val)
if node.left:
queue.insert(0, node.left)
if node.right:
queue.insert(0, node.right)
return res
递归实现也是可能的。但是，它需要事先知道根节点的最大深度。
def levelOrder(root: TreeNode) -> List[int]:
res = []
max_depth = maxDepth(root)
for i in range(max_depth):
# level start from 0 to max_depth-1
visitLevel(root, i, action)
return res
def visitLevel(root:TreeNode, level:int, res: List):
if not root:
return
if level==0:
res.append(node.val)
else:
self.visitLevel(root.left, level-1, res)
self.visitLevel(root.right, level-1, res)
def maxDepth(root: TreeNode) -> int:
if not root:
return 0
if not root.left and not root.right:
return 1
return max([ maxDepth(root.left), maxDepth(root.right)]) + 1