樹(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ù)的遞歸定義如下：
- 至少有一個(gè)結(jié)點(diǎn)（稱為根）
- 其它是互不相交的子樹(shù)
二叉樹(shù)
二叉樹(shù)是由n（n≥0）個(gè)結(jié)點(diǎn)組成的有限集合秒紧、每個(gè)結(jié)點(diǎn)最多有兩個(gè)子樹(shù)的有序樹(shù)绢陌。它或者是空集，或者是由一個(gè)根和稱為左熔恢、右子樹(shù)的兩個(gè)不相交的二叉樹(shù)組成脐湾。
特點(diǎn)：
- 二叉樹(shù)是有序樹(shù)，即使只有一個(gè)子樹(shù)叙淌，也必須區(qū)分左秤掌、右子樹(shù)；
- 二叉樹(shù)的每個(gè)結(jié)點(diǎn)的度不能大于2鹰霍，只能取0闻鉴、1、2三者之一茂洒；
- 二叉樹(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)渠羞。
源代碼：
#-*- encoding:utf-8 -*-
'''
樹(shù)的構(gòu)建：
5
6 7
8 9
'''
class Tree():
'樹(shù)的實(shí)現(xiàn)'
def __init__(self,ltree = 0,rtree = 0,data = 0):
self.ltree = ltree
self.rtree = rtree
self.data = data
class BTree():
'二叉樹(shù)的實(shí)現(xiàn)'
def __init__(self,base = 0):
self.base = base
def _Empty(self):
'是否為空樹(shù)'
if self.base == 0:
return True
else:
return False
def qout(self,tree_base):
'前序遍歷:根-左-右'
if tree_base == 0:
return
print tree_base.data
self.qout(tree_base.ltree)
self.qout(tree_base.rtree)
def mout(self,tree_base):
'中序遍歷:左-根-右'
if tree_base == 0:
return
self.mout(tree_base.ltree)
print tree_base.data
self.mout(tree_base.rtree)
def hout(self,tree_base):
'后序遍歷:左-右-根'
if tree_base == 0:
return
self.hout(tree_base.ltree)
self.hout(tree_base.rtree)
print tree_base.data
#test
tree1 = Tree(data=8)
tree2 = Tree(data=9)
tree3 = Tree(tree1,data=6)
tree4 = Tree(tree2,0,data=7)
base = Tree(tree3,tree4,5)
btree = BTree(base)
print '前序遍歷結(jié)果:'
btree.qout(btree.base)
print '中序遍歷結(jié)果:'
btree.mout(btree.base)
print '后序遍歷結(jié)果:'
btree.hout(btree.base)