資源簡介

樹與二叉樹
1.線性結構和非線性結構
線性結構的所有元素都是線性排列的，結構中必然存在唯一的“起點”和“終點”元素。且除首尾元素外，都有且只有一個“前驅”和“后驅”節(jié)點。
非線性結構則完全相反，結構中可能存在多個“起點”和“終點”元素。所有節(jié)點都可能存在0個或多個“前驅”和“后繼”節(jié)點。
2.樹形結構
樹可以描述為由n（n>=0）個節(jié)點構成的一個有限集合，以及在該集合上定義的一種節(jié)點關系。
樹形結構是一種特殊的非線性結構，其特點是：只有一個沒有“前驅”，只有“后繼”的根節(jié)點。有多個只有“前驅”沒有“后繼”的葉子節(jié)點，其余節(jié)點均只有一個“前驅”和多個“后繼”。
3.描述樹形結構的詞
1）度（Degree）：
一個節(jié)點擁有的子樹（后繼節(jié)點）的個數(shù)稱之為該節(jié)點的度,一棵樹中最大的度稱之為樹的度。
2)節(jié)點（Node）：
沒有前驅的節(jié)點稱為根節(jié)點或開始節(jié)點；沒有后驅的節(jié)點稱為葉子節(jié)點或終端節(jié)點。
樹中度不為0的節(jié)點稱為分支節(jié)點，除根節(jié)點之外的分支節(jié)點稱為內(nèi)部節(jié)點。
節(jié)點間的前驅和后驅關系也稱之為父子關系。
3)層數(shù)（Level）:
節(jié)點的層數(shù)從根節(jié)點開始計算，根節(jié)點的層數(shù)為1。樹中節(jié)點最大層數(shù)稱為樹的高度或深度（Depth）
4.二叉樹
二叉樹是樹形結構的一種特殊情況，其最大度為2。
1)完全二叉樹和滿二叉樹
滿二叉樹：所有節(jié)點度為2或0；所有葉子節(jié)點在同一層
完全二叉樹：最多只有最下兩層度小于0；最下一層的葉子節(jié)點都在最左邊。
2)二叉樹的性質(zhì)
二叉樹第k層上最多有2k-1個節(jié)點（K>=1）；
深度為k的二叉樹最多有2k-1個節(jié)點（k>=1）；
度為2的節(jié)點個數(shù)（n0）和度為0的節(jié)點個數(shù)（n2）滿足n0=n2+1的關系；
3)二叉樹的遍歷：前序遍歷（根左右），中序遍歷（左根右），后序遍歷（左右根）
#二叉樹的實現(xiàn)方式
<---這是用來舉例的二叉樹
#1.數(shù)組實現(xiàn)
#用數(shù)組實現(xiàn)二叉樹，從根節(jié)點開始，從上而下，從左到右存儲
#非完全二叉樹需先補全為為完全二叉樹后存儲
#而又基于數(shù)組定義(元素數(shù)據(jù)類型相同)，空節(jié)點用''空字符填充
tree_s = ['A','B','C','','D','','E']
#2.鏈表實現(xiàn)
#用鏈表實現(xiàn)二叉樹，頭指針指向根節(jié)點
#節(jié)點格式：[左子樹指針，值域，右子樹指針]
tree_item_head = 0
tree_item = [[1,'A',2],[-1,'B',3],[-1,'C',4],[-1,'D',-1],[-1,'E',-1]]
#3.列表實現(xiàn)
#用列表實現(xiàn)二叉樹格式[節(jié)點名稱，左子樹，右子樹]
tree_list = ['A',['B',None,['D',None,None]],['C',None,['E',None,None]]]
#4.類實現(xiàn)
class node:
def __init__(self,value,left=None,right=None):
self.value = value
self.left = left
self.right = right
class tree:
def __init__(self):
self.root = None

def bulid(self,data):#假裝這里有個建立二叉樹的方法
def preTraverse(self,p): #前序遍歷
if p is None:
return
print(p.value,end=',')
self.preTraverse(p.left)
self.preTraverse(p.right)
def midTraverse(self,p): #中序遍歷
if p is None:
return
self.midTraverse(p.left)
print(p.value,end=',')
self.midTraverse(p.right)
def afterTraverse(self,p): #后序遍歷
if p is None:
return
self.afterTraverse(p.left)
self.afterTraverse(p.right)
print(p.value,end=',')
import random
t = tree()
list1 = [];n=0
while n<10:
r = random.randint(0,99)
if r not in list1:
list1.append(r)
t.build(r) #提綱上沒有，我自己瞎寫了一個
n+=1
print(r,end=',')
t.preTraverse(t.root)
t.midTraverse(t.root)
t.afterTraverse(t.root)
#基于數(shù)組存儲二叉樹的遍歷
tree_s = ['A','B','C','','D','','E']
#前提：父節(jié)點f和子節(jié)點c的索引關系：c=2*f+1
#1.前序遍歷
def preTraverse(tree_s,p):
f=p;c=f*2+1
print(tree_s[f],end=',') #輸出父節(jié)點
if c preTraverse(tree_s,c)
if c+1 preTraverse(tree_s,c+1)
preTraverse(tree_s,0)
def midTraverse(tree_s,p):
f=p;c=f*2+1
if c midTraverse(tree_s,c)
print(tree_s[f],end=',') #輸出父節(jié)點
if c+1 midTraverse(tree_s,c+1)
midTraverse(tree_s,0)
def afterTraverse(tree_s,p): #后序遍歷
f=p;c=f*2+1
if c afterTraverse(tree_s,c)
if c+1 afterTraverse(tree_s,c+1)
print(tree_s[f],end=',') #輸出父節(jié)點
afterTraverse(tree_s,0)

展開更多......

收起↑