二叉树遍历python

1. python中yield和return究竟有什么区别，怎么用

常看到别人使用或讨论yield语法,能搜到的中文解释却不多,今天决心搞定yield,把暂时的理解贴到这里.

搞定yield之前: 叠代器(iterator)

发现yield: 生成器(constructor)

使用yield: 递归调用

1. iterator

叠代器最简单例子应该是数组下标了，且看下面的c++代码：

int array[10];

for ( int i = 0; i < 10; i++ )

printf("%d ", array[i]);

叠代器工作在一个容器里(array[10])，它按一定顺序(i++)从容器里取出值(array[i])并进行操作(printf("%d ", array[i])。

上面的代码翻译成python：

array = [i for i in range(10)]

for i in array:

print i,

for i in array干了什么(别乱想)？首先，array作为一个list是个容器，其次list这个内建类型有默认的next行为，python发现这些之后采 取的秘密的没被各位看到的动作是：拿出array这丫容器的叠代器，从里面next一下把值给i供for循环主体处置，for把这个值print了。

现在的问题是数据可以做容器叠代，代码可以吗？

怎么不行，碗碟可以用来放菜，wk们不就联想出用nt盛吗，当然我们的yield不会那么yellow + bt

2. constructor

怎么把函数变成constructor？ 在函数体里有yield就行了！

def gen():
print 'enter'
yield 1
print 'next'
yield 2
print 'next again'

for i in gen():
print i

各位！python看到gen函数里出现yield，知道可以用next了，问题是怎么对代码这个容器玩next？

从容器里拿到iterator的时候它还什么也不是，处在容器入口处，对于数组来说就是下标为-1的地方，对于函数来说就是函数入口嘛事没干，但是万事俱备就欠next。

开始for i in g，next让itreator爬行到yield语句存在的地方并返回值,

再次next就再爬到下一个yield语句存在的地方并返回值,依次这样直到函数返回(容器尽头)。
您一定看出来上面代码的输出是：

enter
1
next
2
next again

如果没看出来请不要往下看了免得反被yield搞定。

3. 使用yield

yield的代码叠代能力不但能打断函数执行还能记下断点处的数据，下次next书接上回，这正是递归函数需要的。

例如中序遍历二叉树：

(应该是David Mertz写的)

def inorder(t):
if t:
for x in inorder(t.left):
yield x
yield t.label
for x in inorder(t.right):
yield x

for n in inorder(tree)

print n

当然yield这种代码next的能力还可以用在其它方面，发现拍案的在贴咯。

2. 树.层序遍历的三种实现算法

树层序遍历的三种实现算法如下：

1. 队列法：

   • 核心思路：利用队列先进先出的特性，逐层遍历二叉树。首先将根节点入队，然后进入一个循环，每次循环处理当前队列中的所有节点，并将它们的子节点入队。循环直到队列为空。
   • 实现细节：在每次循环开始时，记录队列的大小，然后依次处理这些节点。处理节点时，将其值添加到当前层的结果列表中，并将其左右子节点入队。

2. 递归与栈的结合：

   • 核心思路：通过递归和栈的结合来实现层序遍历。使用一个自定义的节点类，将根节点及其层数压入栈中。然后进入一个循环，每次循环从栈中弹出一个节点，将其值添加到对应层的结果列表中，并将其左右子节点压入栈中。
   • 实现细节：在每次弹出节点时，检查结果列表的大小是否等于当前节点的层数，如果是，则在结果列表中添加一个新的空列表作为当前层的结果容器。然后将节点的值添加到当前层的结果列表中。

3. Python版实现：

   • 核心思路：与递归与栈的结合方法类似，但使用Python的列表来模拟栈，并简化了一些操作。同样使用一个自定义的节点类来存储节点值和层数信息。
   • 实现细节：初始化一个栈，将根节点及其层数压入栈中。然后进入一个循环，每次循环从栈中弹出一个节点，将其值添加到对应层的结果列表中。然后将节点的左右子节点压入栈中。

这三种方法各有优缺点，队列法直观易懂，递归与栈的结合方法在处理复杂情况时可能更加灵活，而Python版实现则利用了Python的语言特性使代码更加简洁。在实际应用中，可以根据具体需求和场景选择合适的方法。

3. python二叉树输出结果为什么是这样

1. 二叉树

二叉树(binary tree)中的每个节点都不能有多于两个的儿子。

图 ((7+3)*(5-2))的表达式树表示

2.1 根据中缀表达式构造表达式树：

遍历表达式：

1.建立一个空树

2.遇到'('，为当前的Node添加一个left child，并将left child当做当前Node。

3.遇到数字，赋值给当前的Node，并返回parent作为当前Node。

4.遇到('+-*/')，赋值给当前Node，并添加一个Node作为right child，将right child当做当前的Node。

5.遇到')',返回当前Node的parent。

defbuildexpressionTree(exp):tree=BinaryTree('')stack=[]stack.append(tree)currentTree=treeforiinexp:ifi=='(':currentTree.insertLeft('')stack.append(currentTree)currentTree=currentTree.leftChildelifinotin'+-*/()':currentTree.key=int(i)parent=stack.pop()currentTree=parentelifiin'+-*/':currentTree.key=icurrentTree.insertRight('')stack.append(currentTree)currentTree=currentTree.rightChildelifi==')':currentTree=stack.pop()else:raiseValueErrorreturntree

上述算法对中缀表达式的写法要求比较繁琐，小括号应用太多，例如要写成(a+(b*c))的形式。

用后缀表达式构建表达式树会方便一点:如果符号是操作数，建立一个单节点并将一个指向它的指针推入栈中。如果符号是一个操作符，从栈中弹出指向两棵树T1和T2的指针并形成一棵新的树，树的根为此操作符，左右儿子分别指向T2和T1.

123456789101112131415defbuild_tree_with_post(exp):stack=[]oper='+-*/'foriinexp:ifinotinoper:tree=BinaryTree(int(i))stack.append(tree)else:righttree=stack.pop()lefttree=stack.pop()tree=BinaryTree(i)tree.leftChild=lefttreetree.rightChild=righttreestack.append(tree)returnstack.pop()

3.树的遍历

3.1 先序遍历(preorder travelsal)

先打印出根，然后递归的打印出左子树、右子树，对应先缀表达式

12345678defpreorder(tree,nodelist=None):ifnodelistisNone:nodelist=[]iftree:nodelist.append(tree.key)preorder(tree.leftChild,nodelist)preorder(tree.rightChild,nodelist)returnnodelist

3.2 中序遍历(inorder travelsal)

先递归的打印左子树，然后打印根，最后递归的打印右子树，对应中缀表达式

12345definorder(tree):iftree:inorder(tree.leftChild)printtree.keyinorder(tree.rightChild)

3.3 后序遍历(postorder travelsal)

递归的打印出左子树、右子树，然后打印根，对应后缀表达式

1234567defpostorder(tree):iftree:forkeyinpostorder(tree.leftChild):yieldkeyforkeyinpostorder(tree.rightChild):yieldkeyyieldtree.key

3.4 表达式树的求值

1234567891011defpostordereval(tree):operators={'+':operator.add,'-':operator.sub,'*':operator.mul,'/':operator.truediv}leftvalue=Nonerightvalue=Noneiftree:leftvalue=postordereval(tree.leftChild)rightvalue=postordereval(tree.rightChild)ifleftvalueandrightvalue:returnoperators[tree.key](leftvalue,rightvalue)else:returntree.key

4. Python算法系列—深度优先遍历算法

一、什么是深度优先遍历
深度优先遍历算法是经典的图论算法。从某个节点v出发开始进行搜索。不断搜索直到该节点所有的边都被遍历完，当节点v所有的边都被遍历完以后，深度优先遍历算法则需要回溯到v以前驱节点来继续搜索这个节点。
注意：深度优先遍历问题一定要按照规则尝试所有的可能才行。

二、二叉树

2.二叉树类型
二叉树类型：空二叉树、满二叉树、完全二叉树、完美二叉树、平衡二叉树。

空二叉树：有零个节点
完美二叉树：每一层节点都是满的二叉树（如1中举例的图）
满二叉树：每一个节点都有零个或者两个子节点
完全二叉树：出最后一层外，每一层节点都是满的，并且最后一层节点全部从左排列
平衡二叉树：每个节点的两个子树的深度相差不超过1.

注：国内对完美二叉树和满二叉树定义相同
3.二叉树相关术语
术语 解释
度 节点的度为节点的子树个数
叶子节点 度为零的节点
分支节点 度不为零的节点
孩子节点 节点下的两个子节点
双亲节点 节点上一层的源节点
兄弟节点 拥有同一双亲节点的节点
根 二叉树的源头节点
深度 二叉树中节点的层的数量

DLR（先序）：
LDR（中序）：
LRD(后序）：
注意：L代表左子树R代表右子树；D代表根

6.深度优先遍历和广度优先遍历
深度优先遍历：前序、中序和后序都是深度优先遍历
从根节点出发直奔最远节点，
广度优先遍历：首先访问举例根节点最近的节点，按层次递进，以广度优先遍历上图的顺序为：1-2-3-4-5-6-7
三、面试题+励志
企鹅运维面试题：
1.二叉树遍历顺序：看上文
2.用你熟悉的语言说说怎么创建二叉树？ python看上文