Python二叉樹定義與遍歷方法實例分析

發(fā)布時間：2020-09-27 21:25:18 來源：腳本之家閱讀：134 作者：止語--- 欄目：開發(fā)技術(shù)

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

二叉樹基本概述：

二叉樹是有限個元素的幾個，如果為空則為空二叉樹，或者有一個結(jié)點稱之為根節(jié)點，分列根節(jié)點兩側(cè)的為二叉樹的左右子節(jié)點，二叉樹有如下的性質(zhì)：

1. 二叉樹的每個結(jié)點不存在度大于2的結(jié)點
2. 二叉樹的第i層至多有2^{i-1}個結(jié)點
3. 深度為k的二叉樹至多有2^k - 1個結(jié)點
4. 二叉樹中，度為0的結(jié)點數(shù)N0比度為2的結(jié)點數(shù)N2大1，即存在N2 + 1 = N0

Python代碼：

#coding:utf-8
'BiTree'
class Node(object):
  'Node Defination'
  def __init__(self,item):
    self.item = item
    self.left = None
    self.right = None
class Tree(object):
  'Bitree Defination'
  def __init__(self):
    self.root = None
  def add(self,item):
    node = Node(item)
    if self.root is None:
      self.root = node
    else:
      q = [self.root]
      while True:
        pop_node = q.pop(0)
        if pop_node.left is None:
          pop_node.left = node
          return
        elif pop_node.right is None:
          pop_node.right = node
          return
        else:
          q.append(pop_node.left)
          q.append(pop_node.right)
  def traverse(self):#層次遍歷
    if self.root is None:
      return None
    q = [self.root]
    res = [self.root.item]
    while q != []:
      pop_node = q.pop(0)
      if pop_node.left is not None:
        q.append(pop_node.left)
        res.append(pop_node.left.item)
      if pop_node.right is not None:
        q.append(pop_node.right)
        res.append(pop_node.right.item)
    return res
  def preorder(self,root): #先序遍歷
    if root is None:
      return []
    result = [root.item]
    left_item = self.preorder(root.left)
    right_item = self.preorder(root.right)
    return result + left_item + right_item
  def inorder(self,root): #中序遍歷
    if root is None:
      return []
    result = [root.item]
    left_item = self.inorder(root.left)
    right_item = self.inorder(root.right)
    return left_item + result + right_item
  def postorder(self,root): #后序遍歷
    if root is None:
      return []
    result = [root.item]
    left_item = self.postorder(root.left)
    right_item = self.postorder(root.right)
    return left_item + right_item + result
if __name__=='__main__':
  t = Tree()
  for i in range(10):
    t.add(i)
  print "層序遍歷:",t.traverse()
  print "先序遍歷:",t.preorder(t.root)
  print "中序遍歷:",t.inorder(t.root)
  print "后序遍歷:",t.postorder(t.root)

輸出結(jié)果：

層序遍歷: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
先序遍歷: [0, 1, 3, 7, 8, 4, 9, 2, 5, 6]
中序遍歷: [7, 3, 8, 1, 9, 4, 0, 5, 2, 6]
后序遍歷: [7, 8, 3, 9, 4, 1, 5, 6, 2, 0]

這里對于

if __name__=='__main__':
“Make a script both importable and executable”

意思就是說讓你寫的腳本模塊既可以導(dǎo)入到別的模塊中用，另外該模塊自己也可執(zhí)行。

這里通過一個示例進(jìn)行解釋：

#test.py
def func():
 print "we are in %s"%__name__
if __name__ == '__main__':
 func()

輸出結(jié)果：

we are in __main__

說明if語句中的內(nèi)容被執(zhí)行了，調(diào)用了 func()函數(shù)，現(xiàn)在在另一個模塊中調(diào)用func函數(shù)

#testtest
from test import func
func()

輸出結(jié)果：

we are in moudle

也就是說 if 條件中的內(nèi)容沒有執(zhí)行。

總結(jié)：

如果直接執(zhí)行某個*.py文件，該文件中 if __name__ == '__main__'是True，相當(dāng)于調(diào)式本模塊的代碼；如果是從另一個模塊(testtest.py)通過import導(dǎo)入該文件的時候,這時__name__就是這個模塊的名字（test）而不是__main__,總之在調(diào)式代碼的時候加上 if __name__ == '__main__'中加入調(diào)試代碼，可以讓步模塊調(diào)用的時候不執(zhí)行調(diào)式代碼，如果想排查本模塊代碼的問題時，直接進(jìn)行調(diào)試執(zhí)行

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

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

向AI問一下細(xì)節(jié)

Python二叉樹定義與遍歷方法實例分析

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標(biāo)簽