这是一道面试题
我想一个解决办法。它使用队列。
public Void BFS()
{
Queue q = new Queue();
q.Enqueue(root);
Console.WriteLine(root.Value);
while (q.count > 0)
{
Node n = q.DeQueue();
if (n.left !=null)
{
Console.Writeln(n.left);
q.EnQueue(n.left);
}
if (n.right !=null)
{
Console.Writeln(n.right);
q.EnQueue(n.right);
}
}
}
有什么比这更好的解决方案，不使用队列吗？
逐级遍历称为广度优先遍历。使用队列是执行此操作的正确方法。如果您想进行深度优先遍历，您将使用堆栈。
你拥有它的方式虽然不是很标准。应该是这样的。
public Void BFS()
{
Queue q = new Queue();
q.Enqueue(root);//You don't need to write the root here, it will be written in the loop
while (q.count > 0)
{
Node n = q.DeQueue();
Console.Writeln(n.Value); //Only write the value when you dequeue it
if (n.left !=null)
{
q.EnQueue(n.left);//enqueue the left child
}
if (n.right !=null)
{
q.EnQueue(n.right);//enque the right child
}
}
}
编辑
这是工作中的算法。假设你有一棵像这样的树：
1
/ \
2 3
/ / \
4 5 6
首先，根 (1) 将被排队。然后进入循环。队列 (1) 中的第一项被出列并打印。1 的孩子从左到右排队，队列现在包含 {2, 3} 回到循环开始 队列 (2) 中的第一项出列并打印 2 的孩子从左到右排队，队列现在包含 {3, 4} 回到循环开始...
队列将在每个循环中包含这些值
1：{1}
2: {2, 3}
3: {3, 4}
4: {4, 5, 6}
5: {5, 6}
6：{6}
7: {}//空，循环终止
输出：
1
2
3
4
5
6
由于问题需要逐级打印树，因此应该有一种方法可以确定何时在控制台上打印换行符。这是我的代码，它尝试通过将 NewLine 节点附加到队列来做同样的事情，
void PrintByLevel(Node *root)
{
Queue q;
Node *newline = new Node("\n");
Node *v;
q->enque(root);
q->enque(newline);
while(!q->empty()) {
v = q->deque();
if(v == newline) {
printf("\n");
if(!q->empty())
q->enque(newline);
}
else {
printf("%s", v->val);
if(v->Left)
q-enque(v->left);
if(v->right)
q->enque(v->right);
}
}
delete newline;
}
让我们看看一些 Scala 解决方案。首先，我将定义一个非常基本的二叉树：
case class Tree[+T](value: T, left: Option[Tree[T]], right: Option[Tree[T]])
我们将使用以下树：
1
/ \
2 3
/ / \
4 5 6
您像这样定义树：
val myTree = Tree(1,
Some(Tree(2,
Some(Tree(4, None, None)),
None
)
),
Some(Tree(3,
Some(Tree(5, None, None)),
Some(Tree(6, None, None))
)
)
)
我们将定义一个breadthFirst 函数，该函数将遍历树，将所需函数应用于每个元素。有了这个，我们将定义一个打印函数并像这样使用它：
def printTree(tree: Tree[Any]) =
breadthFirst(tree, (t: Tree[Any]) => println(t.value))
printTree(myTree)
现在，Scala 解决方案，递归，列出但没有队列：
def breadthFirst[T](t: Tree[T], f: Tree[T] => Unit): Unit = {
def traverse(trees: List[Tree[T]]): Unit = trees match {
case Nil => // do nothing
case _ =>
val children = for{tree <- trees
Some(child) <- List(tree.left, tree.right)}
yield child
trees map f
traverse(children)
}
traverse(List(t))
}
接下来，Scala解决方案，队列，无递归：
def breadthFirst[T](t: Tree[T], f: Tree[T] => Unit): Unit = {
import scala.collection.mutable.Queue
val queue = new Queue[Option[Tree[T]]]
import queue._
enqueue(Some(t))
while(!isEmpty)
dequeue match {
case Some(tree) =>
f(tree)
enqueue(tree.left)
enqueue(tree.right)
case None =>
}
}
该递归解决方案功能齐全，但我对它可以进一步简化感到不安。
队列版本不起作用，但非常有效。在 Scala 中关于导入对象的这一点并不常见，但在这里得到了很好的利用。
C++：
struct node{
string key;
struct node *left, *right;
};
void printBFS(struct node *root){
std::queue<struct node *> q;
q.push(root);
while(q.size() > 0){
int levelNodes = q.size();
while(levelNodes > 0){
struct node *p = q.front();
q.pop();
cout << " " << p->key ;
if(p->left != NULL) q.push(p->left);
if(p->right != NULL) q.push(p->right);
levelNodes--;
}
cout << endl;
}
}
输入 ：
平衡树创建自：
string a[] = {"a","b","c","d","e","f","g","h","i","j","k","l","m","n"};
输出：
g
c k
a e i m
b d f h j l n
PS：我知道OP说，没有队列。我的回答只是显示是否有人正在寻找使用队列的 C++ 解决方案。
public class LevelOrderTraversalQueue {
Queue<Nodes> qe = new LinkedList<Nodes>();
public void printLevelOrder(Nodes root)
{
if(root == null) return;
qe.add(root);
int count = qe.size();
while(count!=0)
{
System.out.print(qe.peek().getValue());
System.out.print(" ");
if(qe.peek().getLeft()!=null) qe.add(qe.peek().getLeft());
if(qe.peek().getRight()!=null) qe.add(qe.peek().getRight());
qe.remove(); count = count -1;
if(count == 0 )
{
System.out.println(" ");
count = qe.size();
}
}
}
}
为了按级别打印，您可以将级别信息与节点一起存储为元组以添加到队列中。然后，您可以在更改级别时打印一个新行。这是执行此操作的 Python 代码。
from collections import deque
class BTreeNode:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
def printLevel(self):
""" Breadth-first traversal, print out the data by level """
level = 0
lastPrintedLevel = 0
visit = deque([])
visit.append((self, level))
while len(visit) != 0:
item = visit.popleft()
if item[1] != lastPrintedLevel: #New line for a new level
lastPrintedLevel +=1
print
print item[0].data,
if item[0].left != None:
visit.append((item[0].left, item[1] + 1))
if item[0].right != None:
visit.append((item[0].right, item[1] + 1))
试试这个（完整代码）：
class HisTree
{
public static class HisNode
{
private int data;
private HisNode left;
private HisNode right;
public HisNode() {}
public HisNode(int _data , HisNode _left , HisNode _right)
{
data = _data;
right = _right;
left = _left;
}
public HisNode(int _data)
{
data = _data;
}
}
public static int height(HisNode root)
{
if (root == null)
{
return 0;
}
else
{
return 1 + Math.max(height(root.left), height(root.right));
}
}
public static void main(String[] args)
{
// 1
// / \
// / \
// 2 3
// / \ / \
// 4 5 6 7
// /
// 21
HisNode root1 = new HisNode(3 , new HisNode(6) , new HisNode(7));
HisNode root3 = new HisNode(4 , new HisNode(21) , null);
HisNode root2 = new HisNode(2 , root3 , new HisNode(5));
HisNode root = new HisNode(1 , root2 , root1);
printByLevels(root);
}
private static void printByLevels(HisNode root) {
List<HisNode> nodes = Arrays.asList(root);
printByLevels(nodes);
}
private static void printByLevels(List<HisNode> nodes)
{
if (nodes == null || (nodes != null && nodes.size() <= 0))
{
return;
}
List <HisNode> nodeList = new LinkedList<HisNode>();
for (HisNode node : nodes)
{
if (node != null)
{
System.out.print(node.data);
System.out.print(" , ");
nodeList.add(node.left);
nodeList.add(node.right);
}
}
System.out.println();
if (nodeList != null && !CheckIfNull(nodeList))
{
printByLevels(nodeList);
}
else
{
return;
}
}
private static boolean CheckIfNull(List<HisNode> list)
{
for(HisNode elem : list)
{
if (elem != null)
{
return false;
}
}
return true;
}
}
我认为您期望的是打印每个级别的节点，或者用空格或逗号分隔，并且级别用新行分隔。这就是我编写算法的方式。我们知道，当我们在图或树上进行广度优先搜索并将节点插入队列时，队列中的所有节点都将与前一个级别相同或新级别，即父级别+ 1，仅此而已。
因此，当您处于某个级别时，请继续打印节点值，并且一旦您发现节点的级别增加 1，则在开始打印该级别的所有节点之前插入新行。
这是我的代码，它不使用太多内存，所有事情都只需要队列。
假设树从根开始。
queue = [(root, 0)] # Store the node along with its level.
prev = 0
while queue:
node, level = queue.pop(0)
if level == prev:
print(node.val, end = "")
else:
print()
print(node.val, end = "")
if node.left:
queue.append((node.left, level + 1))
if node.right:
queue.append((node.right, level + 1))
prev = level
最后，您需要的只是所有处理的队列。
我调整了答案，使其显示空节点并按高度打印。实际上对于测试红黑树的平衡相当不错。还
可以将颜色添加到打印行中以检查黑色高度。
Queue<node> q = new Queue<node>();
int[] arr = new int[]{1,2,4,8,16,32,64,128,256};
int i =0;
int b = 0;
int keeper = 0;
public void BFS()
{
q.Enqueue(root);
while (q.Count > 0)
{
node n = q.Dequeue();
if (i == arr[b])
{
System.Diagnostics.Debug.Write("\r\n"+"("+n.id+")");
b++;
i =0 ;
}
else {
System.Diagnostics.Debug.Write("(" + n.id + ")");
}
i++;
if (n.id != -1)
{
if (n.left != null)
{
q.Enqueue(n.left);
}
else
{
node c = new node();
c.id = -1;
c.color = 'b';
q.Enqueue(c);
}
if (n.right != null)
{
q.Enqueue(n.right);
}
else
{
node c = new node();
c.id = -1;
c.color = 'b';
q.Enqueue(c);
}
}
}
i = 0;
b = 0;
System.Diagnostics.Debug.Write("\r\n");
}
当然你不需要使用队列。这是在python中。
# Function to print level order traversal of tree
def printLevelOrder(root):
h = height(root)
for i in range(1, h+1):
printGivenLevel(root, i)
# Print nodes at a given level
def printGivenLevel(root , level):
if root is None:
return
if level == 1:
print "%d" %(root.data),
elif level > 1 :
printGivenLevel(root.left , level-1)
printGivenLevel(root.right , level-1)
""" Compute the height of a tree--the number of nodes
along the longest path from the root node down to
the farthest leaf node
"""
def height(node):
if node is None:
return 0
else :
# Compute the height of each subtree
lheight = height(node.left)
rheight = height(node.right)
return max(lheight, reight)
试试下面的代码。
public void printLevelOrder(TreeNode root) {
if (root == null) {
return;
}
Queue<TreeNode> nodesToVisit = new LinkedList<>();
nodesToVisit.add(root);
int count = nodesToVisit.size();
while (count != 0) {
TreeNode node = nodesToVisit.remove();
System.out.print(" " + node.data);
if (node.left != null) {
nodesToVisit.add(node.left);
}
if (node.right != null) {
nodesToVisit.add(node.right);
}
count--;
if (count == 0) {
System.out.println("");
count = nodesToVisit.size();
}
}
}
这是我的答案。
//for level order traversal
func forEachLevelOrder(_ visit : (TreeNode) -> Void) {
visit(self)
var queue = Queue<TreeNode>()
children.forEach {
queue.Enqueue($0)
}
while let node = queue.Dequeue() {
visit(node)
node.children.forEach { queue.Enqueue($0)}
}
}
这里的 children 是一个数组，用于存储节点的子节点。