本文實例講述了Python定義二叉樹及4種遍歷方法。分享給大家供大家參考，具體如下：

Python & BinaryTree

1. BinaryTree (二叉樹)

二叉樹是有限個元素的集合，該集合或者為空、或者有一個稱為根節點（root）的元素及兩個互不相交的、分別被稱為左子樹和右子樹的二叉樹組成。

2. 二叉樹

生成二叉樹

# init a treedef InitBinaryTree(dataSource, length):  root = BTNode(dataSource[0])  for x in xrange(1,length):    node = BTNode(dataSource[x])    InsertElementBinaryTree(root, node)  return root  print 'Done...'

前序遍歷

# pre-orderdef PreorderTraversalBinaryTree(root):  if root:    print '%d | ' % root.data,    PreorderTraversalBinaryTree(root.leftChild)    PreorderTraversalBinaryTree(root.rightChild)

中序遍歷

# in-orderdef InorderTraversalBinaryTree(root):  if root:    InorderTraversalBinaryTree(root.leftChild)    print '%d | ' % root.data,    InorderTraversalBinaryTree(root.rightChild)

后序遍歷

# post-orderdef PostorderTraversalBinaryTree(root):  if root:    PostorderTraversalBinaryTree(root.leftChild)    PostorderTraversalBinaryTree(root.rightChild)    print '%d | ' % root.data,

按層遍歷

# layer-orderdef TraversalByLayer(root, length):  stack = []  stack.append(root)  for x in xrange(length):    node = stack[x]    print '%d | ' % node.data,    if node.leftChild:      stack.append(node.leftChild)    if node.rightChild:      stack.append(node.rightChild)

Result

二叉樹的思想重在“遞歸”， 并不是非要用遞歸處理，而是去理解二叉樹遞歸的思想

完整代碼段

# -*- coding:utf-8 -*-#################### implement Binary Tree using python### Hongwing### 2016-9-4#################import mathclass BTNode(object):  """docstring for BTNode"""  def __init__(self, data):    self.data = data    self.leftChild = None    self.rightChild = None# insert elementdef InsertElementBinaryTree(root, node):  if root:    if node.data < root.data:      if root.leftChild:        InsertElementBinaryTree(root.leftChild, node)      else:        root.leftChild = node    else:      if root.rightChild:        InsertElementBinaryTree(root.rightChild, node)      else:        root.rightChild = node  else:    return 0# init a treedef InitBinaryTree(dataSource, length):  root = BTNode(dataSource[0])  for x in xrange(1,length):    node = BTNode(dataSource[x])    InsertElementBinaryTree(root, node)  return root  print 'Done...'# pre-orderdef PreorderTraversalBinaryTree(root):  if root:    print '%d | ' % root.data,    PreorderTraversalBinaryTree(root.leftChild)    PreorderTraversalBinaryTree(root.rightChild)# in-orderdef InorderTraversalBinaryTree(root):  if root:    InorderTraversalBinaryTree(root.leftChild)    print '%d | ' % root.data,    InorderTraversalBinaryTree(root.rightChild)# post-orderdef PostorderTraversalBinaryTree(root):  if root:    PostorderTraversalBinaryTree(root.leftChild)    PostorderTraversalBinaryTree(root.rightChild)    print '%d | ' % root.data,# layer-orderdef TraversalByLayer(root, length):  stack = []  stack.append(root)  for x in xrange(length):    node = stack[x]    print '%d | ' % node.data,    if node.leftChild:      stack.append(node.leftChild)    if node.rightChild:      stack.append(node.rightChild)if __name__ == '__main__':  dataSource = [3, 4, 2, 6, 7, 1, 8, 5]  length = len(dataSource)  BTree = InitBinaryTree(dataSource, length)  print '****NLR:'  PreorderTraversalBinaryTree(BTree)  print '/n****LNR'  InorderTraversalBinaryTree(BTree)  print '/n****LRN'  PostorderTraversalBinaryTree(BTree)  print '/n****LayerTraversal'  TraversalByLayer(BTree, length)