二叉树相关算法实现
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了二叉树相关算法实现,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含6674字,纯文字阅读大概需要10分钟。
内容图文
![二叉树相关算法实现](/upload/InfoBanner/zyjiaocheng/603/f1aa6ea530be4be88241be27d1fe78ed.jpg)
二叉树算法实现
一:二叉链表的建立和遍历
例,建立如图所示二叉链表:
# 定义结点类
class BNode:
def __init__(self,data=None,lchild=None,rchild=None):
self.data = data
self.lchild = lchild
self.rchild = rchild
# 先序遍历函数
def preorder(T):
if T == None:
return
print(T.data, end="")
preorder(T.lchild)
preorder(T.rchild)
# 中序遍历
def inorder(T):
if T == None:
return
inorder(T.lchild)
print(T.data, end="")
inorder(T.rchild)
# 后序遍历
def finalorder(T):
if T == None:
return
finalorder(T.lchild)
finalorder(T.rchild)
print(T.data, end="")
if __name__ == '__main__':
# 实例化结点
a = BNode("A")
b = BNode("B")
c = BNode("C")
d = BNode("D")
a.lchild = b
a.rchild = c
b.rchild = d
# 先序遍历二叉树
preorder(a)
print()
# 中序遍历二叉树
inorder(a)
print()
# 后序遍历二叉树
finalorder(a)
如果结点很多,我们可以通过循环或递归的方式来创建结点
# 定义结点类
class BNode:
def __init__(self,data=None,lchild=None,rchild=None):
self.data = data
self.lchild = lchild
self.rchild = rchild
# 先序遍历函数
def preorder(T):
if T == None:
return
print(T.data, end="")
preorder(T.lchild)
preorder(T.rchild)
# 中序遍历
def inorder(T):
if T == None:
return
inorder(T.lchild)
print(T.data, end="")
inorder(T.rchild)
# 后序遍历
def finalorder(T):
if T == None:
return
finalorder(T.lchild)
finalorder(T.rchild)
print(T.data, end="")
# 递归创建二叉树
def createBT():
ch = input("输入一个结点数据,*表示空")
if ch == "*":
return None
else:
T = BNode(ch)
T.lchild = createBT()
T.rchild = createBT()
return T
if __name__ == '__main__':
# 创建二叉树,如上图二叉树,输入顺序为:A B * D * * C * *
T = createBT()
# 先序遍历二叉树
preorder(T)
print()
# 中序遍历二叉树
inorder(T)
print()
# 后序遍历二叉树
finalorder(T)
统计叶子结点数
# 定义结点类
class BNode:
def __init__(self,data=None,lchild=None,rchild=None):
self.data = data
self.lchild = lchild
self.rchild = rchild
# 递归创建二叉树
def createBT():
ch = input("输入一个结点数据,*表示空")
if ch == "*":
return None
else:
T = BNode(ch)
T.lchild = createBT()
T.rchild = createBT()
return T
# 统计叶子结点数
def countleaf(T):
if T == None:
return None
else:
if T.lchild == None and T.rchild == None:
global n
n += 1
countleaf(T.lchild)
countleaf(T.rchild)
if __name__ == '__main__':
# 创建二叉树,如上图二叉树,输入顺序为:A B * D * * C * *
T = createBT()
# 定义计数器
n = 0
countleaf(T)
print(n)
查找元素
# 定义结点类
class BNode:
def __init__(self,data=None,lchild=None,rchild=None):
self.data = data
self.lchild = lchild
self.rchild = rchild
# 递归创建二叉树
def createBT():
ch = input("输入一个结点数据,*表示空")
if ch == "*":
return None
else:
T = BNode(ch)
T.lchild = createBT()
T.rchild = createBT()
return T
# 查找元素
def searchdata(T, ch):
if T == None:
return None
if T.data == ch:
return T
else:
p = searchdata(T.lchild, ch)
if p != None:
return p
p = searchdata(T.rchild, ch)
if p != None:
return p
if __name__ == '__main__':
# 创建二叉树
T = createBT()
# 查找元素
ch = input("请输入查找元素:")
ret = searchdata(T, ch)
if ret != None:
print("元素存在")
else:
print("元素不存在")
二:二叉树的类表存储
为什么可以使用列表来存放二叉树?
- 二叉树是递归定义的
- python列表也是递归定义的
步骤如下:
- 空树用None表示
- 非空树用包含三个元素的列表[data,lchild,rchild]表示
把一棵树映射到一种分层的list结构,每棵二叉树都有与之对应的列表
以如下二叉树为例:
它的list结构为:[“A”,[“B”,None,“D”,None,None]],[“C”,None,None]]
# 先序遍历
def preorder(T):
if T == None:
return
print(T[0])
preorder(T[1])
preorder(T[2])
# 中序遍历
def inorder(T):
if T == None:
return
inorder(T[1])
print(T[0])
inorder(T[2])
# 后序遍历
def finalorder(T):
if T == None:
return
finalorder(T[1])
finalorder(T[2])
print(T[0])
if __name__ == '__main__':
t = ["A",["B",None,["D",None,None]],["C",None,None]]
preorder(t)
inorder(t)
finalorder(t)
创建二叉列表,以上图为例:
class BinTreeLink:
def __init__(self, data, lchild=None, rchild=None):
self.btree = [data, lchild, rchild]
# 判断是否为空
def is_empty(self):
return self.btree[0] is None
# 建立左子树
def set_lchild(self, lchild):
if self.is_empty():
return
self.btree[1] = lchild.btree
# 建立右子树
def set_rchild(self, rchild):
if self.is_empty():
return
self.btree[2] = rchild.btree
if __name__ == '__main__':
a = BinTreeLink("A")
b = BinTreeLink("B")
c = BinTreeLink("C")
d = BinTreeLink("D")
a.set_lchild(b)
a.set_rchild(c)
b.set_rchild(d)
print(a.btree)
三:二叉树非递归中序遍历
? 要实现非递归中序遍历算法,二叉树的列表存储方式必须为为链表存储。首先要建立二叉链表,然后利用栈来进行中序遍历。
以下图为例:
# 定义栈
class sstack:
def __init__(self):
self.slist = []
# 判断栈是否为空
def is_empty(self):
if self.slist == []:
return 1
else:
return 0
# 压栈
def pushstack(self, item):
self.slist.append(item)
# 出栈
def popstack(self):
return self.slist.pop()
class BNode:
def __init__(self, data=None, lchild=None, rchild=None):
self.data = data
self.lchild = lchild
self.rchild = rchild
# 中序遍历
def inOrder(T):
p = T
s = sstack()
while p != None or s.is_empty() != 1:
while p != None:
s.pushstack(p)
p = p.lchild
if s.is_empty() != 1:
p = s.popstack()
print(p.data)
p = p.rchild
if __name__ == '__main__':
a = BNode("A")
b = BNode("B")
c = BNode("C")
d = BNode("D")
a.lchild = b
a.rchild = c
b.rchild = d
inOrder(a)
四:哈夫曼树的建立
构建如下哈夫曼树:
# 节点创建
class HuffmanNode:
def __init__(self, data):
self.data = data
self.lchild = None
self.rchild = None
self.parent = None
# 构建哈夫曼树
def creatHuffmanTree(hufnode):
nodelist = hufnode[:]
while len(nodelist) > 1:
nodelist.sort(key=lambda item:item.data)
left = nodelist.pop(0)
right = nodelist.pop(0)
father = HuffmanNode(left.data + right.data)
father.lchild = left
father.rchild = right
left.parent = father
right.parent = father
nodelist.append(father)
return nodelist[0]
# 先序遍历
def preorder(T):
if T == None:
return
print(T.data)
preorder(T.lchild)
preorder(T.rchild)
if __name__ == '__main__':
hufnode = []
while True:
a = int(input("请输入叶子节点的权值,输入-1结束"))
if a == -1:
break
hufnode.append(HuffmanNode(a))
bt = creatHuffmanTree(hufnode)
preorder(bt)
五:哈夫曼编码的实现
例:已知一段码文出现4个字符{T,;,A,C},出现的概率为{7,5,2,4},使用哈夫曼编码的方式对这4个字符进行编码。
过程:
? (1) 遍历nodelis,从第一个叶子结点开始回退
? (2) 遇到左分支设置为0,遇到右分支设置为1
? (3) 直到回退到根结点,再去找下一个叶子结点。
class HuffmanNode:
def __init__(self, data):
self.data = data
self.lchild = None
self.rchild = None
self.parent = None
def creatHuffmanTree(hufnode):
nodelist = hufnode[:]
while len(nodelist) > 1:
nodelist.sort(key=lambda item:item.data)
left = nodelist.pop(0)
right = nodelist.pop(0)
father = HuffmanNode(left.data + right.data)
father.lchild = left
father.rchild = right
left.parent = father
right.parent = father
nodelist.append(father)
return nodelist[0]
# 哈夫曼编码
def hufEncode(hufnode, root):
encode = [""] * len(hufnode)
for i in range(len(hufnode)):
node = hufnode[i]
while node != root:
if node.parent.lchild == node:
encode[i] = "0" + encode[i]
else:
encode[i] = "1" + encode[i]
node = node.parent
return encode
内容总结
以上是互联网集市为您收集整理的二叉树相关算法实现全部内容,希望文章能够帮你解决二叉树相关算法实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。