溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本文實例講述了Python定義二叉樹及4種遍歷方法。分享給大家供大家參考，具體如下：
二叉樹是有限個元素的集合，該集合或者為空、或者有一個稱為根節點（root）的元素及兩個互不相交的、分別被稱為左子樹和右子樹的二叉樹組成。
# init a tree
def 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-order
def PreorderTraversalBinaryTree(root):
if root:
print '%d | ' % root.data,
PreorderTraversalBinaryTree(root.leftChild)
PreorderTraversalBinaryTree(root.rightChild)
# in-order
def InorderTraversalBinaryTree(root):
if root:
InorderTraversalBinaryTree(root.leftChild)
print '%d | ' % root.data,
InorderTraversalBinaryTree(root.rightChild)
# post-order
def PostorderTraversalBinaryTree(root):
if root:
PostorderTraversalBinaryTree(root.leftChild)
PostorderTraversalBinaryTree(root.rightChild)
print '%d | ' % root.data,
# layer-order
def 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 math
class BTNode(object):
"""docstring for BTNode"""
def __init__(self, data):
self.data = data
self.leftChild = None
self.rightChild = None
# insert element
def 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 tree
def 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-order
def PreorderTraversalBinaryTree(root):
if root:
print '%d | ' % root.data,
PreorderTraversalBinaryTree(root.leftChild)
PreorderTraversalBinaryTree(root.rightChild)
# in-order
def InorderTraversalBinaryTree(root):
if root:
InorderTraversalBinaryTree(root.leftChild)
print '%d | ' % root.data,
InorderTraversalBinaryTree(root.rightChild)
# post-order
def PostorderTraversalBinaryTree(root):
if root:
PostorderTraversalBinaryTree(root.leftChild)
PostorderTraversalBinaryTree(root.rightChild)
print '%d | ' % root.data,
# layer-order
def 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)
更多關于Python相關內容感興趣的讀者可查看本站專題：《Python數據結構與算法教程》、《Python編碼操作技巧總結》、《Python函數使用技巧總結》、《Python字符串操作技巧匯總》及《Python入門與進階經典教程》
希望本文所述對大家Python程序設計有所幫助。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
