快捷導(dǎo)航

python二叉樹(shù)的實(shí)現(xiàn)實(shí)例

更新時(shí)間：2013年11月21日 14:11:04 作者：

這篇文章主要介紹了python二叉樹(shù)的實(shí)現(xiàn)實(shí)例，大家參考使用吧

樹(shù)的定義

樹(shù)是一種重要的非線性數(shù)據(jù)結(jié)構(gòu)，直觀地看，它是數(shù)據(jù)元素（在樹(shù)中稱為結(jié)點(diǎn)）按分支關(guān)系組織起來(lái)的結(jié)構(gòu)，很象自然界中的樹(shù)那樣。樹(shù)結(jié)構(gòu)在客觀世界中廣泛存在，如人類社會(huì)的族譜和各種社會(huì)組織機(jī)構(gòu)都可用樹(shù)形象表示。樹(shù)在計(jì)算機(jī)領(lǐng)域中也得到廣泛應(yīng)用，如在編譯源程序時(shí)，可用樹(shù)表示源程序的語(yǔ)法結(jié)構(gòu)。又如在數(shù)據(jù)庫(kù)系統(tǒng)中，樹(shù)型結(jié)構(gòu)也是信息的重要組織形式之一。一切具有層次關(guān)系的問(wèn)題都可用樹(shù)來(lái)描述。
樹(shù)結(jié)構(gòu)的特點(diǎn)是：它的每一個(gè)結(jié)點(diǎn)都可以有不止一個(gè)直接后繼，除根結(jié)點(diǎn)外的所有結(jié)點(diǎn)都有且只有一個(gè)直接前驅(qū)。
樹(shù)的遞歸定義如下：（1）至少有一個(gè)結(jié)點(diǎn)（稱為根）（2）其它是互不相交的子樹(shù)

二叉樹(shù)：　
二叉樹(shù)是由n（n≥0）個(gè)結(jié)點(diǎn)組成的有限集合、每個(gè)結(jié)點(diǎn)最多有兩個(gè)子樹(shù)的有序樹(shù)。它或者是空集，或者是由一個(gè)根和稱為左、右子樹(shù)的兩個(gè)不相交的二叉樹(shù)組成。

二叉樹(shù)特點(diǎn)：
（1）二叉樹(shù)是有序樹(shù)，即使只有一個(gè)子樹(shù)，也必須區(qū)分左、右子樹(shù)；
（2）二叉樹(shù)的每個(gè)結(jié)點(diǎn)的度不能大于2，只能取0、1、2三者之一；
（3）二叉樹(shù)中所有結(jié)點(diǎn)的形態(tài)有5種：空結(jié)點(diǎn)、無(wú)左右子樹(shù)的結(jié)點(diǎn)、只有左子樹(shù)的結(jié)點(diǎn)、只有右子樹(shù)的結(jié)點(diǎn)和具有左右子樹(shù)的結(jié)點(diǎn)。

二叉樹(shù)基本的數(shù)據(jù)結(jié)構(gòu)

復(fù)制代碼代碼如下:

#!/usr/bin/python
# -*- coding: utf-8 -*-

class TreeNode(object):
    def __init__(self,data,left,right):
        self.data = data
        self.left = left
        self.right = right

class BTree(object):
def __init__(self,root=0):
self.root = root

您可能感興趣的文章: