如何在不使用遞歸的情況下打印樹的每個葉子路徑。不用遞歸打印樹的每個葉子路徑
這是一個樹，NOT二叉樹
struct node {
int data
std::vector<node*> children;
}
打印所有的從根到葉的路徑，即，以下是樹
-------------root ------d m n ---x y z o p
結果應該是：
root-d-x root-d-y root-d-z root-m root-n-o root-n-p
我試圖用非遞歸的方式，但失敗了。
該策略很簡單。往下走吧，然後起來。在每一點你都知道下一步該去哪裏。
保留一個向量，它是您當前在樹中的位置。從根開始。然後僞代碼：
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，並打印沒有前向邊的節點。
完全沒有回答這個問題...... –
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
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);
}
}
}
的想法是跟蹤路徑和節點兩者的在我們遍歷樹的時候在一個堆棧中。對象堆棧負責照顧。 希望幫助！
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);
}
}
}
}
對於n叉樹 - DFS和BFS路徑爲基礎，總結
100
// \ \
1 2 3 4
///// / \
10 11 12 13 14 40 41
/\
400 401
public void traverseDFS(Node root) {
Stack<Node> s = new Stack<Node>();
Stack<String> sPath = new Stack<>();
Stack<Integer> sSum = new Stack<>();
s.push(root); sPath.push(root.Id + ""); sSum.push(root.Id);
while (!s.isEmpty()) {
// Pop out
Node head = s.pop(); String headPath = sPath.pop(); Integer headSum = sSum.pop();
if(head.children == null || head.children.isEmpty()){ //Leaf
System.out.println(headPath + "(" + headSum+")");
continue;
}
for(Node child : head.children) {
String path = headPath + "->" + child.Id;
Integer sum = headSum + child.Id;
// Push on stack
s.push(child); sPath.push(path); sSum.push(sum);
}
}
}
public static void traverseBFS(Node root) {
Queue<Node> q = new LinkedList<>();
Queue<String> qPath = new LinkedList<>();
Queue<Integer> qSum = new LinkedList<>();
q.add(root); qPath.add(root.Id + ""); qSum.add(root.Id);
while(!q.isEmpty()){
// Poll the q
Node head = q.poll(); String headPath = qPath.poll(); Integer headSum = qSum.poll();
if(head.children == null || head.children.isEmpty()){ //Leaf
System.out.println(headPath + "(" + headSum+")");
continue;
}
for(Node child : head.children) {
String path = headPath + "->" + child.Id;
Integer sum = headSum + child.Id;
// Add to the q
q.add(child); qPath.add(path); qSum.add(sum);
}
}
}
class Node {
int Id;
String Data;
Node Parent;
ArrayList<Node> children;
public Node(int id, String data) {
Id = id;
Data = data;
}
}
輸出
-----------Depth FS-------------
100->4->41(145)
100->4->40->401(545)
100->4->40->400(544)
100->3(103)
100->2(102)
100->1->14(115)
100->1->13(114)
100->1->12(113)
100->1->11(112)
100->1->10(111)
-----------BFS-------------
100->2(102)
100->3(103)
100->1->10(111)
100->1->11(112)
100->1->12(113)
100->1->13(114)
100->1->14(115)
100->4->41(145)
100->4->40->400(544)
100->4->40->401(545)
這是功課？ – benjer3
我相信你可以調整你的情況的非遞歸二叉樹遍歷。具有最小內存開銷的最簡單的實現將在'節點'中具有父節點指針。請參閱[nonRecursiveInOrderTraversal（）]（http://en.wikipedia.org/wiki/Tree_traversal）。 –