等级序树遍历 [英] Level-order tree traversal

问题描述

我想写这将需要一个IntTree作为参数，并返回一个队列的IntTree的层次顺序值的方法。为了澄清：一个IntTree是作为它的根整数值的树，有一个IntTree作为其左，右子树。 对一些方法的注意事项： 值（吨） - 在树的根部返回整数值 左（T） - 返回左IntTree子树// 右（吨） - 返回右子树

I am trying to write a method that will take an IntTree as a parameter and return a Queue with the values of the IntTree in level order. To clarify: an IntTree is a tree with an integer value as its root, and has an IntTree as its left and right subtrees. A note on some methods: value(t) - returns the integer value at the root of the tree left(t) - returns the left IntTree subtree // right(t) - returns the right sub-tree

这里的code我有这么远。我是相当新的编程，所以我很抱歉，如果它不是很优雅。

Here's the code I have so far. I'm rather new to programming, so I'm sorry if it's not very elegant.

public static QueueList levelOrder(IntTree t) {
//returns a QueueList with the values in level order

Object val;
QueueList q = new QueueList(); //temp queueList
QueueList theta = new QueueList();  //the QueueList which will eventually be printed


if (isEmpty(t)) {
  return theta;    //possible problem here
} else {

  IntTree tL = left(t);  //using for possible updating. probably won't work
  IntTree tR = right(t);

  q.enqueue(value(t)); //enqueue the root of the tree

  while (!q.isEmpty()) {
    val = q.dequeue();  //pop off the top element for printing
    theta.enqueue(val); // put the element in the queue to be printed
    if (tL != null) { 
      q.enqueue(value(tL));  //if the left isn't null, enqueue the lefts
      tL = left(tL); //this will only branch left

    }
    if (tR != null) {       //if the right isn't null, enqueue the rights
      q.enqueue(value(tR));
      tR = right(tR);  //this will only branch right
    }
  }
}
return theta; //returns a queue with values in order

}

我写的TL和TR变量，因为如果我写的东西，如如果（左（T）！= NULL），我将结束了无限递归，因为T是从来没有更新。与此code的问题是，'TL'将唯一分支机构左，TR只会分支的权利。所以以下后根一层，一些值将永远不会被存储。我希望这是明确的，任何帮助是极大的AP preciated。谢谢你。

I wrote the tL and tR variables because if I wrote something like "if (left(t) != null)", I would end up with infinite recursion, since 't' was never updated. The problem with this code is that 'tL' will only branch left and 'tR' will only branch right. So after one level below the root, some values will never be stored. I hope this was clear, and any help is greatly appreciated. Thank you.

推荐答案

无需实现边缘的值的队列中，实现为IntTrees（节点）的队列中。这将大大简化你的逻辑。

Instead of implementing the fringe as a queue of values, implement it as a queue of IntTrees (nodes). That will simplify your logic tremendously.

  while (!q.isEmpty()) {
    IntTree node = q.dequeue();  //pop off the top element
    theta.enqueue(value(node)); // put the element in the queue to be printed

    //enqueue the children
    IntTree left = left(node);
    if ( left != null ) {
        q.enqueue(left);
    }
    //...similar for right
  }

当你有这样的你没有保持¥和 TR 指针并行，这是我想象是一个有缺陷的做法，无论如何。

When you have this you don't have to maintain the tL and tR pointers in parallel, which I imagine is a flawed approach anyhow.

• 的广度优先遍历（维基百科）

这篇关于等级序树遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！