溫馨提示×

溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》

Python定義二叉樹及4種遍歷方法實例詳解

發(fā)布時間：2020-09-06 21:03:20 來源：腳本之家 閱讀：145 作者：亨利何 欄目：開發(fā)技術(shù)

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

Python & BinaryTree

1. BinaryTree (二叉樹)

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

  • 二叉樹的每個結(jié)點至多只有二棵子樹(不存在度大于2的結(jié)點)，二叉樹的子樹有左右之分，次序不能顛倒。
  • 二叉樹的第i層至多有2^{i-1}個結(jié)點
  • 深度為k的二叉樹至多有2^k-1個結(jié)點；
  • 對任何一棵二叉樹T，如果其終端結(jié)點數(shù)為N0，度為2的結(jié)點數(shù)為N2，則N0=N2+1

2. 二叉樹

Python定義二叉樹及4種遍歷方法實例詳解

生成二叉樹
# 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

Python定義二叉樹及4種遍歷方法實例詳解

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

完整代碼段

# -*- 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)

更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python編碼操作技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門與進階經(jīng)典教程》

希望本文所述對大家Python程序設(shè)計有所幫助。

向AI問一下細節(jié)

免責聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手