數(shù)據(jù)結(jié)構(gòu)與算法（Python版） 源代碼 （周元哲 版）第7章 樹和二叉樹

目錄

第7章樹和二叉樹.............................................................2

哈夫曼編碼..............................................................2

7.8實例.....................................................................4

7.8.1打印二叉樹的深度..................................................4

7.8.2打印二叉樹的左右視圖..............................................6

7.8.3二叉樹左右交換....................................................9

第7章樹和二叉樹

哈夫曼編碼

#樹節(jié)點類構(gòu)建

classTreeNode(object):

def—init_(self,data):

self.val=datafO]#節(jié)點的值

self.priority=data[l]#節(jié)點的優(yōu)先度

self.leftChild=None#節(jié)點廣結(jié)點

self.rightChild=None#節(jié)點的右子結(jié)點

self.code="n,#節(jié)點值的編碼

#創(chuàng)建樹節(jié)點隊列函數(shù)

defcreatnodeQ(codes):

q=口

forcodeincodes:

q.append(TreeNode(code))

returnq

#為隊列添加節(jié)點元素，并保證優(yōu)先度從大到小排列

defaddQ(queue,nodeNew):

iflen(queue)==0:

returnfnodeNew]

foriinrange(len(queue)):

ifqueue[il.priority>=nodeNew.priority:

returnqueuel：ij+[nodeNewJ+queue[i:J

returnqueue+fnodeNew]

#節(jié)點隊列類定義

classnodeQeuen(object):

def_init_(self,code):

self.que=creatnodeQ(code)

self.size=len(self.que)

defaddNode(self,node):#添加節(jié)點困數(shù)

self.que=addQ(self.que,node)

self.size+=1

defpopNode(self):#彈11i節(jié)點函數(shù)

self.size-=1

returnself.que.pop(O)

#各個字符在字符串中出現(xiàn)的次數(shù)，即計算優(yōu)先度

deffreChar(string):

d={}

#定義一個字典，遍歷文本中的每一個字母，若字母不在字典里說明是第一次出現(xiàn)，則定義該字

母為鍵，另鍵值為1,若在字典里有，則只需將相應的鍵值加一。遍歷后就得到了每個字母出現(xiàn)的

次數(shù)。

forcinstring:

ifnotcind:

d[c]=1

else:

d[c]+=1

returnsorted(d.items(),key=lambdax:x[l])

#創(chuàng)建哈夫曼樹

defcreatHuffmanTree(nodeQ):

whilenodeQ.size!=1:

nodel=nodeQ.popNode()

node2=nodeQ.popNode()

r=TreeNode([None,nodel.priority+node2.priority])

r.leftChild=nodel

r.rightChild=node2

nodeQ.addNode(r)

returnnodeQ.popNode()

codeDicl={}#用于編碼

codeDic2={}#用于解碼

#由哈夫曼樹得到哈夫曼編碼表

defHuffmanCodeDic(head,x):

globalcodeDic,codeList

ifhead:

HuffmanCodeDic(head.leftChild,x+'O')

#二叉樹的中序遍歷，每遞歸到深一層的時候，就隹后面多加?個O(左子樹)或T(右子樹)。

head.code+=x

ifhead.val:

codeDic2[head.code]=head.val

codeDic1[head,val]=head.code

HuffmanCodeDic(head.rightChild,x+T)

#字符串編碼

defTransEncode(string):

globalcodeDic1

transcode=

forcinstring:

transcode+=codeDicl[c]

returntranscode

#字符串解碼

defTransDecode(StringCode):

globalcodeDic2

code”

ans=

forchinStringCode:

code+=ch

ifcodeincodeDic2:

ans+=codeDic2[code]

code”

returnans

#舉例

string="AAGGDCCCDDDGFBBBFFGGDDDDGGGEFFDDCCCCDDFGAAA”

t=nodeQeuen(freChar(string))

tree=creatHuffmanTree(t)

HuffmanCodeDic(tree,0)

print(codeDic1,codeDic2)

a=TransEncode(string)

print(a)

aa=TransDecode(a)

print(aa)

print(string==aa)

【程序運行結(jié)果】

{E：woo','B*：wor,*A'：'oor,G：‘or,D'：'io;F：C：{'oooo'：'E,wor：B,

wr：'A'jor：G,"o’：‘D'，」io‘：F/iir：rc)

0010010101101111111111010100111000010001000111011001011010101001010100001101

1010101nil1111111101011001001001001

AAGGDCCCDDDGFBBBFFGGDDDDGGGEFFDDCCCCDDFGAAA

True

7.8實例

7.8.1打印二叉樹的深度

【例7-1】給定一棵二叉樹，要求樹的深度。如圖7.24所示。

圖7.24二叉樹

【程序運行代碼】

classNode():

def—init_(self,value,lchild=None,rchild=None,):

self.value=value

self.lchild=lchild

self.rchild=rchild

def_repr_(self):

returnstr(self.value)

classTree():

def_init_(self,root=None):

self.root=root

self.node_list=[]

defadd_node(self,node):

self.node_list.append(node)

temp」ist=1]

temp_list.append(self.root)

ifself.root==None:

self.root=node

else:

whiletempjist:

cur_node=temp_list.pop(0)

ifnotcur_node.lchild:

cur_node.lchild=node

return

elifnotcur_node.rchild:

cur_node.rchild=node

return

else:

temp_list.append(cur_node.lchild)

temp_list.append(cur_node,rchild)

#二叉樹的最大深度

deffind_max_deep(self,root):

if(notroot.lchild)and(notroot.rchild):

return1

ifroot.lchild:

lenghtl=self.find_max_deep(root.lchild)

else:

lenghtl=0

ifroot.rchild:

lenght2=self.find_max_deep(root.rchild)

else:

lenght2=0

return1+max(lenght1,lenght2)

if_name_=='_main_

tree=Tree()

nodel=Node(l)

node2=Node(2)

node3=Node(3)

node4=Node(4)

node5=Node(5)

tree.add_node(node1)

tree.add_node(node2)

tree.add_node(node3)

tree.add_node(node4)

tree.add_node(node5)

max_deep=tree.find_max_deep(tree.root)

print('max_deep:',max_deep)

【程序運行結(jié)果】

max_deep:3

7.8.2打印二叉樹的左右視圖

【例7-1】給定一棵二叉樹，要求輸出左右視圖，如圖7.25所示。

3

/\

920

/\

157

圖7.25二叉樹

程序運行結(jié)果為：左視圖：［3,9,15］左視圖：［3,20,7］

【程序運行代碼】

classNode():

def_ink_(self,value,lchild=None,rchild=None,):

self.value=value

self.lchild=lchild

self.rchild=rchild

def_repr_(self)：

returnstr(self.value)

classTree():

def_init_(self,root=None):

self.root=root

self.node_list=[]

defadd_node(seif,node):

self.node_list.append(node)

temp」ist=[]

temp_list.append(self.root)

ifself.root==None:

self.root=node

else:

whiletemp_list:

cur_node=temp_list.pop(0)

ifnotcur_node.lchild:

cur_node.lchild=node

return

elifnotcur_node.rchild:

cur_node.rchild=node

return

else:

temp_list.append(cur_node.lchild)

temp_list.append(cur_node.rchild)

#找到距離根節(jié)點指定距離的所有節(jié)點

deffind_target_length(self,root,n,target_list=[]):

ifn==0:

target_list.append(root)

#print(self.target_list)

#returntarget_list

ifroot.lchild:

self.find_target_length(root.lchild,n-l,target_list)

ifroot.rchild:

self.find_target_length(root.rchild,n-l,target_list)

returntarget」ist

#二叉樹的最大深度

deffind_max_deep(self,root):

if(notroot.lchild)and(notroot.rchild):

return1

ifroot.lchild:

lenghtl=self.find_max_deep(root.lchild)

else:

lenghtl=O

ifroot.rchild:

lenght2=self.find_max_deep(root.rchild)

else:

lenght2=0

return1+max(lenght1,lenght2)

#二叉樹的左視圖

deffind_view(self,root):

deep」ist=[]

out_put_list=[]

max_deep=self.find_max_deep(root)

cur_deep=0

whilecur_deep<max_deep:

cur_deep_list=self.find_target_length(root,cur_deep)

#print(cur_deep_list)

deep_list.append(cur_deep_list.copy())

cur_deep_list.clear()

cur_deep+=l

print("節(jié)點層次輸出:n,deep_Hst)

foritemindeep_list:

#求左視圖

out_put_list.append(item[OJ)

#求右視圖

#out_put_list.append(item[-1])

returnout_put」ist

if—name—=='—main—

tree=Tree()

nodel=Node(3)

node2=Node(9)

node3=Node(20)

node4=Node(15)

node5=Node(7)

tree.add_node(nodeI)

tree.add_node(node2)

tree.add_node(node3)

tree.add_node(node4)

tree.add_node(node5)

print("左視圖：u,tree.find_view(tree.root))

【程序運行結(jié)果】

節(jié)點層次輸出：[[3],[9,20],[15,7]]

左視圖：[3,9,