再帰を使用せずにツリーのすべての葉のパスを印刷するにはどうすればよいですか。
二分木ではなく、木です
struct node {
int data
std::vector<node*> children;
}
ルートからリーフまでのすべてのパスを印刷します。つまり、以下はツリーです。
- - - - - - -根 ------ dmn --- xyzop
結果は次のようになります。
root-dx root-dy root-dz root-m ルート-いいえ root-np
非再帰的な方法を使用しようとしましたが、失敗しました。
public static void printAllPathToLeafNonRecursive(Node root) {
if (root == null) {
return;
}
Queue<Object> q = new LinkedList<Object>();
q.add(root);
q.add(root.data + "");
while(!q.isEmpty()){
Node head = (Node) q.poll();
String headPath = (String) q.poll();
if(head.isLeaf()){
System.out.println(headPath);
continue;
}
if(head.left!=null){
String leftStr = headPath + "->" + head.left.data;
q.add(head.left);
q.add(leftStr);
}
if(head.right!=null){
String rightStr = headPath + "->" + head.right.data;
q.add(head.right);
q.add(rightStr);
}
}
}
これは、スタックを使用した事前注文の反復トラバーサルのみに基づく Python ソリューションです。パスとパスサムの両方を出力します。
class Stack(object): # just for reference
def __init__(self):
self.a = []
def push(self, b):
self.a.append(b)
def peek(self):
return self.a[-1]
def pop(self):
return self.a.pop()
def isEmpty(self):
return len(self.a) == 0
def show(self):
return self.a
def paths(troot): # you should create your own Tree and supply the root
current = troot
s = Stack()
s.push(current)
s.push(str(current.key))
s.push(current.key)
while not s.isEmpty():
pathsum = s.pop()
path = s.pop()
current = s.pop()
if not current.left and not current.right:
print 'path: %s, pathsum: %d' % (path, pathsum)
if current.right:
rightstr = path + "->" + str(current.right.key)
rightpathsum = pathsum * 10 + current.right.key
s.push(current.right)
s.push(rightstr)
s.push(rightpathsum)
if current.left:
leftstr = path + "->" + str(current.left.key)
leftpathsum = pathsum * 10 + current.left.key
s.push(current.left)
s.push(leftstr)
s.push(leftpathsum)
たとえば、次のツリーの場合:
3
/ \
/ \
/ \
/ \
/ \
/ \
/ \
/ \
1 7
/ \ / \
/ \ / \
/ \ / \
/ \ / \
0 2 5 8
/ \ / \ / \ / \
/ \ / \ / \ / \
NUL NUL NUL NUL 4 6 NUL 9
出力は次のようになります。
>>> paths()
path: 3->1->0, pathsum: 310
path: 3->1->2, pathsum: 312
path: 3->7->5->4, pathsum: 3754
path: 3->7->5->6, pathsum: 3756
path: 3->7->8->9, pathsum: 3789
戦略は単純です。下に、右に、そして上に行きます。それぞれの時点で、次にどこに行くべきかがわかります。
ツリー内の現在の場所であるベクトルを保持します。ルートから開始します。そして、擬似コードで：
while True:
if not a leaf:
current_place.push_back(0) // move down one
else:
print current path.
while can't move right:
if at root:
exit()
current_place.pop_back() //move up one
current_place[-1] += 1
これらの操作には関数呼び出しが必要です。ただし、これらはループを伴う関数呼び出しであり、再帰ではないため、再帰的ではありません。
結局のところ、それはただのグラフです。グラフ トラバーサルにはさまざまな種類があります。スタックでdfsを使用し、前方エッジがないノードを印刷します。
private void rootToLeaf(BSTNode root){
Stack<Map<BSTNode,ArrayList<Integer>>> tmpStack = new Stack<Map<BSTNode,ArrayList<Integer>>>();
Map<BSTNode,ArrayList<Integer>> tmpMap = new HashMap<BSTNode,ArrayList<Integer>>();
//List<Integer> tmp_arraylist = new ArrayList<Integer>();
ArrayList<Integer> tmpList = new ArrayList<Integer>();
tmpList.add(root.data);
tmpMap.put(root, tmpList);
tmpStack.push(tmpMap);
while(!tmpStack.isEmpty()){
Map<BSTNode,ArrayList<Integer>> temp_map = tmpStack.pop();
for(BSTNode node : temp_map.keySet()){
if(node.getLeft()==null && node.getRight()==null){
for(int i: temp_map.get(node)){
System.out.print(i+" ");
}
System.out.println();
}
if(node.getRight()!=null){
ArrayList<Integer> tmp_List = new ArrayList<Integer>();
for(int i: temp_map.get(node)){
tmp_List.add(i);
}
tmp_List.add(node.getRight().getData());
Map<BSTNode,ArrayList<Integer>> tmphashMap = new HashMap<BSTNode,ArrayList<Integer>>();
tmphashMap.put(node.getRight(), tmp_List);
tmpStack.push(tmphashMap);
}
if(node.getLeft()!=null){
ArrayList<Integer> tmp_List = new ArrayList<Integer>();
for(int i: temp_map.get(node)){
tmp_List.add(i);
}
tmp_List.add(node.getLeft().getData());
Map<BSTNode,ArrayList<Integer>> tmphashMap = new HashMap<BSTNode,ArrayList<Integer>>();
tmphashMap.put(node.getLeft(), tmp_List);
tmpStack.push(tmphashMap);
}
}
}
}
public static void RoottoPathPrint(BinaryTreeNode root) {
Stack<Object> stack = new Stack<Object>();
if (root == null)
return;
stack.push(root.getData() + "");
stack.push(root);
while (!stack.isEmpty()) {
BinaryTreeNode temp = (BinaryTreeNode) stack.pop();
String path = (String) stack.pop();
if (temp.getRight() != null) {
stack.push(path + temp.getRight().getData());
stack.push(temp.getRight());
}
if (temp.getLeft() != null) {
stack.push(path + temp.getLeft().getData());
stack.push(temp.getLeft());
}
if (temp.getLeft() == null && temp.getRight() == null) {
System.out.println(path);
}
}
}
ツリーをたどる際に、パスとノードの両方を 1 つのスタックで追跡するという考え方です。オブジェクトスタックがそれを処理します。お役に立てば幸いです!!