1.1 二叉树的初始化
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
#initial of BinaryTreeclass 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 创建一个二叉树
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
#create a BinaryTree [18,7,11,3,4,5,6,#,#,#,#,1,3,2,4]# 18# 7 11#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 前序遍历
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
#递归版本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 中序遍历
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#递归版本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 后序遍历
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
#递归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 层序遍历
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
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 计算节点数
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
#递归版本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 计算树的深度
|
1
2
3
4
5
6
|
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 计算树的叶子树
|
1
2
3
4
5
6
|
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层节点数
|
1
2
3
4
|
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 判断两颗二叉树是否相同
|
1
2
3
4
|
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 二叉树的镜像
|
1
2
3
4
5
6
7
|
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 找最低公共祖先节点
|
1
2
3
4
5
6
7
8
|
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 获取两个节点的距离
|
1
2
3
4
5
6
7
8
9
10
11
12
|
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 -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 找一个节点的所有祖宗节点
|
1
2
3
4
5
6
7
|
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 |
到此这篇关于python二叉树常用算法总结的文章就介绍到这了,更多相关python二叉树常用算法，内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！
原文链接：https://bbs.huaweicloud.com/blogs/254847
