From 85cf121bd14b0e0564ea1bee5dafce175a1bbf2e Mon Sep 17 00:00:00 2001 From: Cédric Bonhomme Date: Tue, 19 Mar 2013 13:03:04 +0100 Subject: In and Post order depth traversal. --- source/binarytree.py | 40 ++++++++++++++++++++++++++++++---------- 1 file changed, 30 insertions(+), 10 deletions(-) (limited to 'source/binarytree.py') diff --git a/source/binarytree.py b/source/binarytree.py index 8a793540..e12c5b6d 100644 --- a/source/binarytree.py +++ b/source/binarytree.py @@ -105,27 +105,47 @@ class CBOrdTree(object): else: return self.size(root.left) + 1 + self.size(root.right) - def printTree(self, root): + def pre_order_traversal(self, root, result=[]): """ - Prints the tree path. + Depth-first. Pre-order traversal. """ if root == None: pass else: - self.printTree(root.left) - print(root.data, end=' ') - self.printTree(root.right) + result.append(root.data) + self.in_order_traversal(root.left, result) + self.in_order_traversal(root.right, result) + return result - def printRevTree(self, root): + def in_order_traversal(self, root, result=[]): """ - Prints the tree path in reverse order. + Depth-first. In-order traversal. """ if root == None: pass else: - self.printRevTree(root.right) - print(root.data, end=' ') - self.printRevTree(root.left) + self.in_order_traversal(root.left, result) + result.append(root.data) + self.in_order_traversal(root.right, result) + return result + + def post_order_traversal(self, root, result=[]): + """ + Depth-first. Post-order traversal. + """ + if root == None: + pass + else: + self.in_order_traversal(root.left, result) + self.in_order_traversal(root.right, result) + result.append(root.data) + return result + + def __str__(self): + """ + Pretty display. + """ + return ", ".join([article["article_title"] for article in self.in_order_traversal(self.root)]) if __name__ == "__main__": # Point of entry in execution mode. -- cgit