python二叉树常用算法总结
作者:我是一颗大西瓜 时间:2023-01-15 01:35:18
1.1 二叉树的初始化
#initial of BinaryTree
class BinaryTree:
def __init__(self,rootObj):
self.val = rootObj
self.left = None
self.right = None
def insertLeft(self,newNode):
if self.left == None:
self.left = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.left = self.left
self.left = t
def insertRight(self,newNode):
if self.right == None:
self.right = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.right = self.right
self.right = t
1.2 创建一个二叉树
#create a BinaryTree [18,7,11,3,4,5,6,#,#,#,#,1,3,2,4]
# 18
# 7 11
#3 4 5 6
# 1 3 2 4
root = BinaryTree(18)
root.left = BinaryTree(7)
root.right = BinaryTree(11)
root.left.left = BinaryTree(3)
root.left.right = BinaryTree(4)
root.right.left = BinaryTree(5)
root.right.right = BinaryTree(6)
root.right.left.left = BinaryTree(1)
root.right.left.right = BinaryTree(3)
root.right.right.left = BinaryTree(2)
root.right.right.right = BinaryTree(4)
1.3 前序遍历
#递归版本
def PreOrder(self, node):
if node:
print(node.val)
self.PreOrder(node.left)
self.PreOrder(node.right)
#循环版本
def PreOrderLoop(self, node):
if node == None:
return
stack =[]
print(node.val)
stack.append(node)
node = node.left
while stack!=[] or node:
while node:
print(node.val)
stack.append(node)
node = node.left
node = stack[-1].right
stack.pop()
#ouput: 18 7 3 4 11 5 1 3 6 2 4
1.4 中序遍历
#递归版本
def InOrder(self, node):
if node:
self.InOrder(node.left)
print(node.val)
self.InOrder(node.right)
#循环版本
def InOrderLoop(self, node):
if node == None:
return None
stack = []
stack.append(node)
node = node.left
while stack!=[] or node:
while node:
stack.append(node)
node = node.left
print(stack[-1].val)
node = stack[-1].right
stack.pop()
#output:3 7 4 18 1 5 3 11 2 6 4
1.5 后序遍历
#递归
def PostOrder(self, node):
if node:
self.PostOrder(node.left)
self.PostOrder(node.right)
print(node.val)
#非递归
def PostOrderLoop(self, node):
if node == None:
return
stack =[]
stack.append(node)
pre = None
while stack!=[]:
node = stack[-1]
if ((node.left==None and node.right==None) or
(pre and (pre == node.left or pre ==node.right))):
print(node.val)
pre = node
stack.pop()
else:
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
#output:3 4 7 1 3 5 2 4 6 11 18
1.6 层序遍历
def LevelOrder(self, node):
if node == None:
return
stack = []
stack.append(node)
while stack!=[]:
node = stack[0]
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
print(node.val)
stack.pop(0)
output: 18 7 11 3 4 5 6 1 3 2 4
1.7 计算节点数
#递归版本
def CountNode(self, root):
if root == None:
return 0
return self.CountNode(root.left) + self.CountNode(root.right) + 1
#非递归版本
def CountNodeNotRev(self, root):
if root == None:
return 0
stack = []
stack.append(root)
index = 0
while index<len(stack):
if stack[index].left:
stack.append(stack[index].left)
if stack[index].right:
stack.append(stack[index].right)
index += 1
print(len(stack))
output: 11
1.8 计算树的深度
def getTreeDepth(self, root):
if root == None:
return 0
left = self.getTreeDepth(root.left) + 1
right = self.getTreeDepth(root.right) + 1
return left if left>right else right
1.9 计算树的叶子树
def countLeaves(self, root):
if root == None:
return 0
if root.left==None and root.right==None:
return 1
return self.countLeaves(root.left)+self.countLeaves(root.right)
1.10 获取第K层节点数
def getKLevel(self, root, K):
if root == None: return 0
if K == 1: return 1
return self.getKLevel(root.left, K-1)+self.getKLevel(root.right, K-1)
1.11 判断两颗二叉树是否相同
def StrucCmp(self, root1, root2):
if root1 == None and root2 == None: return True
elif root1 ==None or root2 == None: return False
return self.StrucCmp(root1.left, root2.left) and self.StrucCmp(root1.right, root2.right)
1.12 二叉树的镜像
def Mirror(self, root):
if root == None: return
tmp = root.left
root.left = root.right
root.right = tmp
self.Mirror(root.left)
self.Mirror(root.right)
1.13 找最低公共祖先节点
def findLCA(self, root, node1, node2):
if root == None: return
if root == node1 or root == node2: return root
left = self.findLCA(root.left, node1, node2)
right = self.findLCA(root.right, node1, node2)
if left and right:
return root
return left if left else right
1.14 获取两个节点的距离
def getDist(self, root, node1, node2):
lca = self.findLCA(root, node1, node2) #找最低公共祖宗节点
level1 = self.FindLevel(lca, node1) #祖节点到两个节点的距离
level2 = self.FindLevel(lca, node2)
return level1+level2
def FindLevel(self, node, target):
if node == None: return -1
if node == target: return 0
level = self.FindLevel(node.left, target)
if level == -1: level = self.FindLevel(node.right, target)
if level != -1: return level + 1
return -1
1.15 找一个节点的所有祖宗节点
def findAllAncestor(self, root, target):
if root == None: return False
if root == target: return True
if self.findAllAncestor(root.left, target) or self.findAllAncestor(root.right, target):
print(root.val)
return True
return False
来源:https://bbs.huaweicloud.com/blogs/254847
标签:python,二叉树,算法
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
asp+xml自动将远程页面中的图片下载到本地
2007-08-23 13:34:00
以SQLite和PySqlite为例来学习Python DB API
2023-07-13 02:19:14
![](https://img.aspxhome.com/file/2023/2/60512_0s.png)
Python使用matplotlib绘制正弦和余弦曲线的方法示例
2023-10-03 13:44:57
![](https://img.aspxhome.com/file/2023/5/63235_0s.png)
使用 Python 实现简单的 switch/case 语句的方法
2021-02-02 09:10:16
使用Python opencv实现视频与图片的相互转换
2022-03-04 15:20:31
解析xml字符串的函数
2008-06-10 12:37:00
python提取word文件中的所有图片
2022-04-10 13:56:39
![](https://img.aspxhome.com/file/2023/5/107965_0s.gif)
MySQL execute、executeUpdate、executeQuery三者的区别
2024-01-23 15:32:11
Python对列表的操作知识点详解
2022-05-08 09:06:39
![](https://img.aspxhome.com/file/2023/9/82939_0s.png)
pyecharts调整图例与各板块的位置间距实例
2023-05-15 20:05:40
![](https://img.aspxhome.com/file/2023/2/76762_0s.jpg)
pandas筛选某列出现编码错误的解决方法
2021-10-18 02:48:05
PyQt5+Caffe+Opencv搭建人脸识别登录界面
2022-06-18 01:42:25
![](https://img.aspxhome.com/file/2023/5/103075_0s.jpg)
Python学习之不同数据类型间的转换总结
2021-10-04 06:06:57
如何在Python中隐藏和加密密码示例详解
2023-07-19 00:00:09
Python计算字符宽度的方法
2021-02-13 20:25:28
vue.js实现只弹一次弹框
2024-05-09 15:08:07
SQLServer 日期函数大全(小结)
2024-01-13 05:36:32
Python3实现建造者模式的示例代码
2021-05-11 13:30:16
![](https://img.aspxhome.com/file/2023/0/118040_0s.png)
Python 查找list中的某个元素的所有的下标方法
2022-10-15 21:48:16
Python实现将xml导入至excel
2023-10-01 06:17:45
![](https://img.aspxhome.com/file/2023/5/95605_0s.jpg)