まず、この質問はこれの複製ではなく、それに基づいています。
その質問の木を例にとると、
1
/ \
2 3
/ / \
4 5 6
そのように印刷するには、プログラムをどのように変更しますか。
1
2 3
4 5 6
一般というより
1
2
3
4
5
6
私は基本的にそれを行うための最も効率的な方法についての直感を探しています.結果をリストに追加してからループする方法があります. より効率的な方法は、ポップされたときに各レベルの最後の要素を格納し、後で新しい行を出力することです。
アイデア？
一度に 1 つのレベルを構築するだけです。
class Node(object):
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def traverse(rootnode):
thislevel = [rootnode]
while thislevel:
nextlevel = list()
for n in thislevel:
print n.value,
if n.left: nextlevel.append(n.left)
if n.right: nextlevel.append(n.right)
print
thislevel = nextlevel
t = Node(1, Node(2, Node(4, Node(7))), Node(3, Node(5), Node(6)))
traverse(t)
編集：最大消費される「補助」メモリを少し節約したい場合（このような「補助」メモリにこのレベルと次のレベルをすべて同時に持つことはありません）、もちろんcollection.deque代わりに使用できますlist、および現在のpopleft単純にループするのではなく、( 経由で) レベルを上げます。一度に 1 つのレベルを作成する (前のレベルを消費する、または反復する) という考え方は変わりません。レベルを区別する必要がある場合は、単一の大きな deque と補助情報 (深さ、または特定のレベルに残っているノードの数など)。
ただし、追加されるだけの (「消費」されるのではなく、ループされる) リストは、deque よりもかなり効率的です (C++ ソリューションを使用している場合は、まったく同様に、単にpush_backforを使用する std::vectorそれを構築し、それを使用するためのループは、std::deque よりも効率的です)。すべての生成が最初に行われ、次にすべての反復 (または消費)が行われるため、メモリが厳密に制約されている場合の興味深い代替手段は、とにかくリストを使用して各レベルを表し、それを (呼び出しで).reverse消費を開始する前に使用することです - 私は.pop測定によってチェックする大きなツリーは周りにありませんが、このアプローチは、deque(リスト [[or std::vector]] の基礎となる実装が実際にpop[[or pop_back]] を数回呼び出した後にメモリをリサイクルすると仮定すると、もちろん deque についても同じ仮定が適用されます;-)。
私には幅優先トラバーサルのように聞こえます。
幅優先トラバーサルはqueueで実装されます。ここでは、改行を出力する必要があることを示す特別なトークンをキューに挿入するだけです。トークンが見つかるたびに、改行を出力し、トークンをキューに再挿入します (最後に -- これがキューの定義です)。
ルートとそれに続く特別な改行トークンを含むキューでアルゴリズムを開始します。
これは幅優先検索であるため、キューを使用して再帰的に単純かつコンパクトな方法でこれを行うことができます...
# built-in data structure we can use as a queue
from collections import deque
def print_level_order(head, queue = deque()):
if head is None:
return
print head.data
[queue.append(node) for node in [head.left, head.right] if node]
if queue:
print_level_order(queue.popleft(), queue)
私のソリューションは Alex Martelli のソリューションと似ていますが、データ構造の走査とデータ構造の処理を分離しています。コードの中身を iterLayers に入れて、printByLayer を短く簡潔にします。
from collections import deque
class Node:
def __init__(self, val, lc=None, rc=None):
self.val = val
self.lc = lc
self.rc = rc
def iterLayers(self):
q = deque()
q.append(self)
def layerIterator(layerSize):
for i in xrange(layerSize):
n = q.popleft()
if n.lc: q.append(n.lc)
if n.rc: q.append(n.rc)
yield n.val
while (q):
yield layerIterator(len(q))
def printByLayer(self):
for layer in self.iterLayers():
print ' '.join([str(v) for v in layer])
root = Node(1, Node(2, Node(4, Node(7))), Node(3, Node(5), Node(6)))
root.printByLayer()
実行すると次のように出力されます。
1
2 3
4 5 6
7
センティナルをキューに入れておき、現在のレベルのすべてのノードがいつ処理されるかを確認してください。
public void printLevel(Node n) {
Queue<Integer> q = new ArrayBlockingQueue<Integer>();
Node sentinal = new Node(-1);
q.put(n);
q.put(sentinal);
while(q.size() > 0) {
n = q.poll();
System.out.println(n.value + " ");
if (n == sentinal && q.size() > 0) {
q.put(sentinal); //push at the end again for next level
System.out.println();
}
if (q.left != null) q.put(n.left);
if (q.right != null) q.put(n.right);
}
}
class TNode:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
class BST:
def __init__(self, root):
self._root = root
def bfs(self):
list = [self._root]
while len(list) > 0:
print [e.data for e in list]
list = [e.left for e in list if e.left] + \
[e.right for e in list if e.right]
bst = BST(TNode(1, TNode(2, TNode(4), TNode(5)), TNode(3, TNode(6), TNode(7))))
bst.bfs()
ここで、私のコードはツリーをレベルごとに上下逆に出力します
int counter=0;// to count the toatl no. of elments in the tree
void tree::print_treeupsidedown_levelbylevel(int *array)
{
int j=2;
int next=j;
int temp=0;
while(j<2*counter)
{
if(array[j]==0)
break;
while(array[j]!=-1)
{
j++;
}
for(int i=next,k=j-1 ;i<k; i++,k--)
{
temp=array[i];
array[i]=array[k];
array[k]=temp;
}
next=j+1;
j++;
}
for(int i=2*counter-1;i>=0;i--)
{
if(array[i]>0)
printf("%d ",array[i]);
if(array[i]==-1)
printf("\n");
}
}
void tree::BFS()
{
queue<node *>p;
node *leaf=root;
int array[2*counter];
for(int i=0;i<2*counter;i++)
array[i]=0;
int count=0;
node *newline=new node; //this node helps to print a tree level by level
newline->val=0;
newline->left=NULL;
newline->right=NULL;
newline->parent=NULL;
p.push(leaf);
p.push(newline);
while(!p.empty())
{
leaf=p.front();
if(leaf==newline)
{
printf("\n");
p.pop();
if(!p.empty())
p.push(newline);
array[count++]=-1;
}
else
{
cout<<leaf->val<<" ";
array[count++]=leaf->val;
if(leaf->left!=NULL)
{
p.push(leaf->left);
}
if(leaf->right!=NULL)
{
p.push(leaf->right);
}
p.pop();
}
}
delete newline;
print_treeupsidedown_levelbylevel(array);
}
ここで私のコードでは、関数 BFS はレベルごとにツリーを出力し、ツリーを逆さまに出力するために int 配列にデータを入力します。(ツリーを逆さまに印刷する際に少しスワップが使用されることに注意してください。これは、目標を達成するのに役立ちます)。スワップが実行されない場合、次のようなツリーの場合
8
/ \
1 12
\ /
5 9
/ \
4 7
/
6
o/p は
6
7 4
9 5
12 1
8
しかし、o/p は
6
4 7
5 9
1 12
8
これが、その配列でパーツの交換が必要だった理由です。
Bread First Search に基づく単純なバージョン。このコードはグラフ全般に適用でき、二分木にも使用できます。
def printBfsLevels(graph,start):
queue=[start]
path=[]
currLevel=1
levelMembers=1
height=[(0,start)]
childCount=0
print queue
while queue:
visNode=queue.pop(0)
if visNode not in path:
if levelMembers==0:
levelMembers=childCount
childCount=0
currLevel=currLevel+1
queue=queue+graph.get(visNode,[])
if levelMembers > 0:
levelMembers=levelMembers-1
for node in graph.get(visNode,[]):
childCount=childCount+1
height.append((currLevel,node))
path=path+[visNode]
prevLevel=None
for v,k in sorted(height):
if prevLevel!=v:
if prevLevel!=None:
print "\n"
prevLevel=v
print k,
return height
g={1: [2, 3,6], 2: [4, 5], 3: [6, 7],4:[8,9,13]}
printBfsLevels(g,1)
>>>
[1]
1
2 3 6
4 5 6 7
8 9 13
>>>
二分木に固有の再帰に基づく別のバージョン
class BinTree:
"Node in a binary tree"
def __init__(self,val,leftChild=None,rightChild=None,root=None):
self.val=val
self.leftChild=leftChild
self.rightChild=rightChild
self.root=root
if not leftChild and not rightChild:
self.isExternal=True
def getChildren(self,node):
children=[]
if node.isExternal:
return []
if node.leftChild:
children.append(node.leftChild)
if node.rightChild:
children.append(node.rightChild)
return children
@staticmethod
def createTree(tupleList):
"Creates a Binary tree Object from a given Tuple List"
Nodes={}
root=None
for item in treeRep:
if not root:
root=BinTree(item[0])
root.isExternal=False
Nodes[item[0]]=root
root.root=root
root.leftChild=BinTree(item[1],root=root)
Nodes[item[1]]=root.leftChild
root.rightChild=BinTree(item[2],root=root)
Nodes[item[2]]=root.rightChild
else:
CurrentParent=Nodes[item[0]]
CurrentParent.isExternal=False
CurrentParent.leftChild=BinTree(item[1],root=root)
Nodes[item[1]]=CurrentParent.leftChild
CurrentParent.rightChild=BinTree(item[2],root=root)
Nodes[item[2]]=CurrentParent.rightChild
root.nodeDict=Nodes
return root
def printBfsLevels(self,levels=None):
if levels==None:
levels=[self]
nextLevel=[]
for node in levels:
print node.val,
for node in levels:
nextLevel.extend(node.getChildren(node))
print '\n'
if nextLevel:
node.printBfsLevels(nextLevel)
## 1
## 2 3
## 4 5 6 7
## 8
treeRep = [(1,2,3),(2,4,5),(3,6,7),(4,8,None)]
tree= BinTree.createTree(treeRep)
tree.printBfsLevels()
>>>
1
2 3
4 5 6 7
8 None
次のコードは、バイナリ ツリーの各レベルを新しい行に出力します。
public void printbylevel(node root){
int counter = 0, level = 0;
Queue<node> qu = new LinkedList<node>();
qu.add(root);
level = 1;
if(root.child1 != null)counter++;
if(root.child2 != null)counter++;
while(!qu.isEmpty()){
node temp = qu.remove();
level--;
System.out.print(temp.val);
if(level == 0 ){
System.out.println();
level = counter;
counter = 0;
}
if(temp.child1 != null){
qu.add(temp.child1);
counter++;
}
if(temp.child2 != null){
qu.add(temp.child2);
counter++;
}
}
}
追加のストレージを必要としないバージョン:
std::deque<Node> bfs;
bfs.push_back(start);
int nodesInThisLayer = 1;
int nodesInNextLayer = 0;
while (!bfs.empty()) {
Node front = bfs.front();
bfs.pop_front();
for (/*iterate over front's children*/) {
++nodesInNextLayer;
nodes.push_back(child);
}
std::cout << node.value;
if (0 == --nodesInThisLayer) {
std::cout << std::endl;
nodesInThisLayer = nodesInNextLayer;
nodesInNextLayer = 0;
} else {
std::cout << " ";
}
}
PS C++ コードで申し訳ありません。私はまだ Python に精通していません。