假设二叉树中每个结点值为单个字符，采用二叉链存储结构存储（ BTree 类），设计一个算法，按从左到右的次序输出一棵二叉树bt中的所有叶子结点
刚好也在学习二叉树：
class BTree:
def __init__(self, data=None, lchild=None, rchild=None):
self.data = data
self.left = lchild
self.right = rchild
def __repr__(self):
if not (self.left or self.right): return f'{self.data}'
return f'[{self.left if self.left else "-"}<{self.data}>{self.right if self.right else "-"}]'
def preOrder(self):
'''前序遍历'''
if not self: return []
return [self.data]+BTree.preOrder(self.left)+BTree.preOrder(self.right)
def inOrder(self):
'''中序遍历'''
if not self: return []
return BTree.inOrder(self.left)+[self.data]+BTree.inOrder(self.right)
def postOrder(self):
'''后序遍历'''
if not self: return []
return BTree.postOrder(self.left)+BTree.postOrder(self.right)+[self.data]
def Leaves(self):
'''遍历出所有叶子'''
if not self:
return []
elif not self.left and not self.right:
return [self.data]
return BTree.Leaves(self.left)+BTree.Leaves(self.right)
def levelOrder(self):
'''层序遍历'''
que = __import__('queue').Queue()
que.put(self)
res = []
while not que.empty() :
n = que.get()
res.append(n.data)
if n.left is not None :
que.put(n.left)
if n.right is not None :
que.put(n.right)
return res
def Height(self):
if not self: return 0
lH = BTree.Height(self.left)
rH = BTree.Height(self.right)
return max(lH,rH)+1
exp = BTree('+')
exp.left = BTree('*')
exp.right = BTree('/')
exp.left.left = BTree(1)
exp.left.right = BTree(2)
exp.right.left = BTree(3)
exp.right.right = BTree('-')
exp.right.right.left = BTree(5)
exp.right.right.right = BTree(6)
print(exp)
print(exp.Leaves())
'''输出：
[[1<*>2]<+>[3</>[5<->6]]]
[1, 2, 3, 5, 6]
'''
中序遍历，先左叉，后右叉。要使用递归，试举例如下：
def findNode(tree):
if tree.hasLeftNode or tree.hasRightNode:
print(findNode(tree.hasLeftNode))
print(tree.value)
print(findNode(tree.hasRightNode))
else:
print(tree.value)