服务器之家

服务器之家 > 正文

python二叉树常用算法总结

时间：2022-01-12 00:31     来源/作者：我是一颗大西瓜

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 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 创建一个二叉树

?
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 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 前序遍历

?
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+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 找一个节点的所有祖宗节点

?
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

标签：
Python 算法 二叉树 

相关文章

热门资讯

蜘蛛侠3英雄无归3正片免费播放 蜘蛛侠3在线观看免费高清完整
蜘蛛侠3英雄无归3正片免费播放 蜘蛛侠3在线观看免费高清完整 2021-08-24
yue是什么意思 网络流行语yue了是什么梗
yue是什么意思 网络流行语yue了是什么梗 2020-10-11
背刺什么意思 网络词语背刺是什么梗
背刺什么意思 网络词语背刺是什么梗 2020-05-22
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
2021年耽改剧名单 2021要播出的59部耽改剧列表
2021年耽改剧名单 2021要播出的59部耽改剧列表 2021-03-05
返回顶部