数据结构与算法（Python版） 源代码 （周元哲 版）第7章 树和二叉树

目录

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

哈夫曼编码..............................................................2

7.8实例.....................................................................4

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

7.8.2打印二叉树的左右视图..............................................6

7.8.3二叉树左右交换....................................................9

第7章树和二叉树

哈夫曼编码

#树节点类构建

classTreeNode(object):

def—init_(self,data):

self.val=datafO]#节点的值

self.priority=data[l]#节点的优先度

self.leftChild=None#节点广结点

self.rightChild=None#节点的右子结点

self.code="n,#节点值的编码

#创建树节点队列函数

defcreatnodeQ(codes):

q=口

forcodeincodes:

q.append(TreeNode(code))

returnq

#为队列添加节点元素，并保证优先度从大到小排列

defaddQ(queue,nodeNew):

iflen(queue)==0:

returnfnodeNew]

foriinrange(len(queue)):

ifqueue[il.priority>=nodeNew.priority:

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

returnqueue+fnodeNew]

#节点队列类定义

classnodeQeuen(object):

def_init_(self,code):

self.que=creatnodeQ(code)

self.size=len(self.que)

defaddNode(self,node):#添加节点困数

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

self.size+=1

defpopNode(self):#弹11i节点函数

self.size-=1

returnself.que.pop(O)

#各个字符在字符串中出现的次数，即计算优先度

deffreChar(string):

d={}

#定义一个字典，遍历文本中的每一个字母，若字母不在字典里说明是第一次出现，则定义该字

母为键，另键值为1,若在字典里有，则只需将相应的键值加一。遍历后就得到了每个字母出现的

次数。

forcinstring:

ifnotcind:

d[c]=1

else:

d[c]+=1

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

#创建哈夫曼树

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)

【程序运行结果】

{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)

【程序运行结果】

max_deep:3

7.8.2打印二叉树的左右视图

【例7-1】给定一棵二叉树，要求输出左右视图，如图7.25所示。

3

/\

920

/\

157

图7.25二叉树

程序运行结果为：左视图：［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)

#找到距离根节点指定距离的所有节点

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("节点层次输出: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))

【程序运行结果】

节点层次输出：[[3],[9,20],[15,7]]

左视图：[3,9,