python二叉树常用算法总结
目录
- 1.1 二叉树的初始化
- 1.2 创建一个二叉树
- 1.3 前序遍历
- 1.4 中序遍历
- 1.5 后序遍历
- 1.6 层序遍历
- 1.7 计算节点数
- 1.8 计算树的深度
- 1.9 计算树的叶子树
- 1.10 获取第K层节点数
- 1.11 判断两颗二叉树是否相同
- 1.12 二叉树的镜像
- 1.13 找最低公共祖先节点
- 1.14 获取两个节点的距离
- 1.15 找一个节点的所有祖宗节点
1.1 二叉树的初始化
#initial of BinaryTreeclass BinaryTree:def __init__(self,rootObj):self.val = rootObjself.left = Noneself.right = Nonedef insertLeft(self,newNode):if self.left == None:self.left = BinaryTree(newNode)else:t = BinaryTree(newNode)t.left = self.leftself.left = tdef insertRight(self,newNode):if self.right == None:self.right = BinaryTree(newNode)else:t = BinaryTree(newNode)t.right = self.rightself.right = t
1.2 创建一个二叉树
#create a BinaryTree [18,7,11,3,4,5,6,#,#,#,#,1,3,2,4]#18# 711#3 4 5 6#1 3 2 4root = 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:returnstack =[]print(node.val)stack.append(node)node = node.leftwhile stack!=[] or node:while node:print(node.val)stack.append(node)node = node.leftnode = stack[-1].rightstack.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 Nonestack = []stack.append(node)node = node.leftwhile stack!=[] or node:while node:stack.append(node)node = node.leftprint(stack[-1].val)node = stack[-1].rightstack.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:returnstack =[]stack.append(node)pre = Nonewhile 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 = nodestack.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:returnstack = []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 0return self.CountNode(root.left) + self.CountNode(root.right) + 1#非递归版本def CountNodeNotRev(self, root):if root == None:return 0stack = []stack.append(root)index = 0while index
1.8 计算树的深度def getTreeDepth(self, root):if root == None:return 0left = self.getTreeDepth(root.left) + 1right = self.getTreeDepth(root.right) + 1return left if left>right else right
1.9 计算树的叶子树def countLeaves(self, root):if root == None:return 0if root.left==None and root.right==None:return 1return self.countLeaves(root.left)+self.countLeaves(root.right)
1.10 获取第K层节点数def getKLevel(self, root, K):if root == None: return 0if K == 1: return 1return 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 Trueelif root1 ==None or root2 == None: return Falsereturn self.StrucCmp(root1.left, root2.left) and self.StrucCmp(root1.right, root2.right)
1.12 二叉树的镜像def Mirror(self, root):if root == None: returntmp = root.leftroot.left = root.rightroot.right = tmpself.Mirror(root.left)self.Mirror(root.right)
1.13 找最低公共祖先节点def findLCA(self, root, node1, node2):if root == None: returnif root == node1 or root == node2: return rootleft = self.findLCA(root.left, node1, node2)right = self.findLCA(root.right, node1, node2)if left and right:return rootreturn 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+level2def FindLevel(self, node, target):if node == None: return -1if node == target: return 0level = self.FindLevel(node.left, target)if level == -1: level = self.FindLevel(node.right, target)if level != -1: return level + 1return -1
1.15 找一个节点的所有祖宗节点def findAllAncestor(self, root, target):if root == None: return Falseif root == target: return Trueif self.findAllAncestor(root.left, target) or self.findAllAncestor(root.right, target):print(root.val)return Truereturn False
【python二叉树常用算法总结】到此这篇关于python
二叉树常用算法总结的文章就介绍到这了,更多相关python二叉树常用算法,内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家!
推荐阅读
- python学习之|python学习之 实现QQ自动发送消息
- 【生信技能树】R语言练习题|【生信技能树】R语言练习题 - 中级
- 逻辑回归的理解与python示例
- python自定义封装带颜色的logging模块
- 【Leetcode/Python】001-Two|【Leetcode/Python】001-Two Sum
- java中如何实现重建二叉树
- Python基础|Python基础 - 练习1
- Python爬虫|Python爬虫 --- 1.4 正则表达式(re库)
- Python(pathlib模块)
- 种树郭橐驼传(文言句式+古今异义+词类活用+通假字)