python二叉树遍历,二叉树遍历方法

二叉树遍历（Binary Tree Traversal）

二叉树的递归遍历比较简单，这里说一下非递归遍历，以中序遍历为例子。

非递归遍历主要用到栈来协助进行。对于一个二叉树，首先根节点入栈，如果有左儿子，则继续入栈，重复直到最左边的儿子，这时候此节点值为要遍历的第一个值，他父亲是在栈顶。所以我们做一次出栈操作   f = stack.pop()，并将　　f.val　　值存为第二个点，接下来要遍历　　f.right，完成后栈的最后元素是  f  的父亲，继续做出栈操作。重复下去可以完成遍历。

def inorderTraversal(self, root): res = [] stack = [] while root!=None or stack!=[]: while root!=None: stack.append(root) root = root.left if stack!=[]: k = stack.pop() res.append(k.val) root = k.right return res

 

posted on 2017-01-01 18:34  特工的特 阅读( ...) 评论( ...) 编辑 收藏

转载于:https://www.cnblogs.com/tegongdete/p/6241312.html