python算法二叉树总结整理

整理B站视频教程：https://www.bilibili.com/video/BV1TV41177uv?p=1

内容：

　　（1）N个结点不同二叉树的个数

　　（2）二叉树的创建

　　（3）遍历二叉树

　　（4）二叉树的深度

　　（5）拷贝二叉树

　　（6）二叉树实际应用--二叉搜索树

一、N个节点不同二叉树的个数

　　N个结点可以构成多少不同的二叉树？

　　分析：n个结点，其中一定有一个是根结点（root）；另外的n-1个结点在根结点的左子树或者右子树，然后左子树看作根结点，又有不同的左右个数分配……

假设n=4，那么除去根结点还有3个结点，可以是根结点左边0个结点、右边3个节点，或者根结点左边1个结点，或者左边两个结点，或者左边3个结点；而每一次左边有多个结点时,第三层结点分布又有不同的排列组合……

　　假设n个结点，左边有k个结点，则右边有n-1-k个结点。设左边k个结点的组合方式为cl,右边结点的组合方式为cr,所以共有的组合方式：cl*cr

　　python代码实现：

 1 # def count(n):
 2 #     # root :1
 3 #     # left :k   [0,n-1]
 4 #     #right :n-k-1
 5 #     if n == 0:
 6 #         return 1
 7 #     s = 0
 8 #     for k in range(n):
 9 #         s += count(k) * count(n-k-1)
10 #     return s
11 #=========================================加入缓存机制，可以超级快的提高计算速度，因为属于迭代算法，每一次计算都要去先算前面n的值，所以加入缓存可以将之前算的都存下来==================
12 def count(n):
13     # root :1
14     # left :k   [0,n-1]
15     #right :n-k-1
16     # if n == 0:
17     #     return 1    #直接将n=0,s=1这种情况加入字典
18     s = count.cache.get(n,0)
19     if s:
20         return s  #如果s不是0，直接返回
21     # s = 0 #s = count.cache.get(n,0)的意思就是，如果缓存cache中有n，那么就将n赋值给s,如果缓存cache中没有n，那么就将缓存的默认参数0赋值给s
22 #            所以，上面的代码就已经将s=0的可能考虑在内了
23     for k in range(n):
24         s += count(k) * count(n-k-1)
25         count.cache[n] = s #将新计算的n和对应的S加入缓存字典
26     return s
27 count.cache = {0:1}  #创建一个缓存，用于存储已经计算过的n，默认情况，n=0时，s=1
28 print(count(100))

二、创建二叉树

　　分析：创建二叉树，其实就是先创建结点，然后给各个结点建立父子或者兄弟关系；采用python中的类来创建结点，利用构造器来给这个类初始化

　　python代码实现：

 1 class TreeNode(object):
 2     def __init__(self,data,left = None, right = None):   #初始化结点，因为左右结点都可能为空，所以默认设置左右结点的值为空，如果没有传入左右结点就是空，有的话则是传入的结点
 3         self.data = data        #这个结点需要有数值
 4         self.left = left         #这个结点可能有左结点
 5         self.right = right        #这个结点可能有右结点
 6 
 7     def __str__(self):             #对结点数值输出做的改进，输出结点的时候，自动输出为结点的数值，也就是不用写C.right.data中的data
 8         return (str(self.data))
 9 #============================调用TreeNode类来创建结点
10 # A = TreeNode("A")
11 # B = TreeNode("B")
12 # C = TreeNode("C")
13 # D = TreeNode("D",left=A) #上面的A、B、C只是构造出来，并没有给他们赋予左右子结点，构造D的时候就直接在复制时将A作为D的左结点
14 # E = TreeNode('E')
15 # E.left = B #在构造E的时候并没有给E的左结点赋值，只是构造出来，但是可以通过后期给E.left赋值
16 A,B,C,D,E,F,G,H,I = [TreeNode(X) for X in 'ABCDEFGHI'] #利用列表迭代的方法创建独立结点
17 #=================================给各个结点之间创建联系=============================
18 A.left = B
19 A.right = C
20 B.right = D
21 C.left = E
22 C.right = F
23 E.left = G
24 F.left = H
25 F.right = I
26 # print(C.right.data) #输出测试，输出C的右结点的值，也就是F，但是可以做改进，不用写data
27 print(C.right)

三、遍历二叉树

　　遍历二叉树也就是二叉树的每一个结点都要访问到，根据遍历的顺序，分为先序遍历、中序遍历、后序遍历和层序遍历；先序遍历：根左右；中序遍历：左根右；后续遍历：左右根；层序遍历：每一层自左向右。

（1）先序遍历

　　分析：遍历的过程先遍历传入的根结点root,然后递归的遍历根结点的左结点作为根结点的子树，然后递归的遍历根结点的右结点作为根结点的子树；整个递归的结束条件，应该是这个根结点不再有左右结点。

代码实现：

from TreeNode import TreeNode
def creatTree():
    A, B, C, D, E, F, G, H, I = [TreeNode(X) for X in 'ABCDEFGHI']  # 利用列表迭代的方法创建独立结点
        # =================================给各个结点之间创建联系=============================
    A.left = B
    A.right = C
    B.right = D
    C.left = E
    C.right = F
    E.left = G
    F.left = H
    F.right = I
    return A

def preOrder(node):
    if node is None:
        return
    print(node.data)
    preOrder(node.left)
    preOrder(node.right)

if __name__ == '__main__':
    root = creatTree()
    preOrder(root)

（2）中序遍历

　　分析：和先序遍历斯思想一样，但是不是先输出根结点，而是先递归的找到左结点

　　python代码实现：

 1 from TreeNode import TreeNode
 2 def creatTree():
 3     A, B, C, D, E, F, G, H, I = [TreeNode(X) for X in 'ABCDEFGHI']  # 利用列表迭代的方法创建独立结点
 4         # =================================给各个结点之间创建联系=============================
 5     A.left = B
 6     A.right = C
 7     B.right = D
 8     C.left = E
 9     C.right = F
10     E.left = G
11     F.left = H
12     F.right = I
13     return A
14 #===============先序遍历==========================================
15 # def preOrder(node):
16 #     if node is None:
17 #         return
18 #     print(node.data)
19 #     preOrder(node.left)
20 #     preOrder(node.right)
21 
22 #================中序遍历===========================================
23 def inOrder(node):
24     if node is None:
25         return
26     inOrder(node.left)
27     print(node.data)
28     inOrder(node.right)
29 
30 if __name__ == '__main__':
31     root = creatTree()
32     # preOrder(root)
33     inOrder(root)

（3）后序遍历

　　分析：思路和先序一样，但是是先递归找到树的左结点和右结点，然后是根

　　python代码实现：

 1 from TreeNode import TreeNode
 2 def creatTree():
 3     A, B, C, D, E, F, G, H, I = [TreeNode(X) for X in 'ABCDEFGHI']  # 利用列表迭代的方法创建独立结点
 4         # =================================给各个结点之间创建联系=============================
 5     A.left = B
 6     A.right = C
 7     B.right = D
 8     C.left = E
 9     C.right = F
10     E.left = G
11     F.left = H
12     F.right = I
13     return A
14 #===============先序遍历==========================================
15 # def preOrder(node):
16 #     if node is None:
17 #         return
18 #     print(node.data)
19 #     preOrder(node.left)
20 #     preOrder(node.right)
21 
22 #================中序遍历===========================================
23 # def inOrder(node):
24 #     if node is None:
25 #         return
26 #     inOrder(node.left)
27 #     print(node.data)
28 #     inOrder(node.right)
29 #================后序遍历===========================================
30 def postOrder(node):
31     if node is None:
32         return
33     postOrder(node.left)
34     postOrder(node.right)
35     print(node.data)
36 
37 if __name__ == '__main__':
38     root = creatTree()
39     # preOrder(root)
40     # inOrder(root)
41     postOrder(root)

（4）回溯迭代版本的先序

　　分析：前面的思路是迭代版本，还可以通过回溯的方法实现。回溯首先需要有一个栈，用来存储遍历的根结点，每次都去找左结点找根结点，一直到根为0，就应该弹出最后的根结点然后访问这个结点的右结点，将右结点作为新的根。回溯结束的条件应该是栈为空，也就是说，等到所有的都抛出去，也就是所有的右结点也都访问到了，此时结束。

　　python代码实现：

 1 from TreeNode import TreeNode
 2 
 3 
 4 def creatOrder():
 5     A,B,C,D,E,F,G,H,I = [TreeNode(X) for X in 'ABCDEFGHI']
 6     A.left = B
 7     A.right = C
 8     B.right = D
 9     C.left = E
10     C.right = F
11     E.left = G
12     F.left = H
13     F.right = I
14     return A
15 def preOrder(node):
16     s = []
17     while True:
18         while node:
19             print(node)
20             s.append(node)
21             node = node.left
22         if not s:
23             break
24         node = s.pop().right
25 if __name__ == "__main__":
26     root = creatOrder()
27     preOrder(root)

（5）层序遍历

　　分析：层序遍历是指按着一层一层去遍历结点，可以采用队列的方式进行，每次遍历根据出队的结点顺序。先是父结点入队，然后父结点出队的时候子节点入队，保证父结点始终在子节点前面，而且子节点入队的时候也是左边的子节点先入队，保证出队先左节点后右结点。等到队列为空的时候，也就是所有结点都遍历到了。

　　python代码实现：

 1 from collections import deque
 2 
 3 from TreeNode import TreeNode
 4 
 5 
 6 def creatTree():
 7     A,B,C,D,E,F,G,H,I = [TreeNode(X) for X in 'ABCDEFGHI']
 8     A.left = B
 9     A.right = C
10     B.right = D
11     C.left = E
12     C.right = F
13     E.left = G
14     F.left = H
15     F.right = I
16     return A
17 def levelOrder(node):
18     q = deque([node])
19     while q:
20         node = q.popleft() #父结点先出队
21         print(node)
22         if node.left:
23             q.append(node.left) #如果有左结点，左结点入队
24         if node.right:
25             q.append(node.right)
26 
27 if __name__ == '__main__':
28     root = creatTree()
29     levelOrder(root)

四、树的深度

（1）递归方法计算

　　分析：计算树的深度，就是子节点中深度的最大值加1，求每个子节点的深度的时候，又递归的分为子节点深度最大值加1.

　　python代码实现：

 1 from TreeNode import TreeNode
 2 
 3 
 4 def creatTree():
 5     A,B,C,D,E,F,G,H,I = [TreeNode(X) for X in 'ABCDEFGHI']
 6     A.left = B
 7     A.right = C
 8     B.right = D
 9     C.left = E
10     C.right = F
11     E.left = G
12     F.left = H
13     F.right = I
14     return A
15 def deep(node):
16     if node is None:
17         return 0
18     dl = deep(node.left)
19     dr = deep(node.right)
20     dp = max(dl,dr) + 1
21     return dp
22 if __name__ == '__main__':
23     root = creatTree()
24     print(deep(root))

（2）迭代方法计算

　　分析：思考层序遍历的方法思路，在进行层序遍历的时候，最后一个出队的结点也就在最深一层，所有只要知道最后一个出队的结点的深度也就知道整个树的深度。所以在向队中存储结点的时候，需要把这个结点的深度也存进去，那就可以用一个元祖包含结点值和结点深度。

　　python代码实现：

 1 from collections import deque
 2 
 3 from TreeNode import TreeNode
 4 
 5 
 6 def creatTree():
 7     A,B,C,D,E,F,G,H,I = [TreeNode(X) for X in 'ABCDEFGHI']
 8     A.left = B
 9     A.right = C
10     B.right = D
11     C.left = E
12     C.right = F
13     E.left = G
14     F.left = H
15     F.right = I
16     return A
17 def deep(node):
18     if node is None:
19         return 0
20     dl = deep(node.left)
21     dr = deep(node.right)
22     dp = max(dl,dr) + 1
23     return dp
24 #================================================以迭代的方式计算深度============================================
25 def deep2(node):
26     q = deque([(node,1)]) #以元祖的形式来表示结点的值和深度
27     while q:
28         (node,d) = q.popleft()
29         if node.left:
30             q.append((node.left,d+1)) #前面抛出过程中，抛出的d是父结点的深度，给子节点赋值深度的时候就需要在父结点深度的基础上加1
31         if node.right:
32             q.append((node.right,d+1))
33     return d
34 if __name__ == '__main__':
35     root = creatTree()
36     print(deep2(root))

五、树的拷贝

　　分析：采用递归的思想，先拷贝左子树和右子树，然后创建根结点，在创建根结点时将拷贝到的左右子树赋值给创建的结点

　　python代码实现：

 1 from collections import deque
 2 
 3 from TreeNode import TreeNode
 4 def creatTree():
 5     A,B,C,D,E,F,G,H,I = [TreeNode(X) for X in 'ABCDEFGHI']
 6     A.left = B
 7     A.right = C
 8     B.right = D
 9     C.left = E
10     C.right = F
11     E.left = G
12     F.left = H
13     F.right = I
14     return A
15 def treeCopy(node):
16     if node is None:
17         return None
18     cl = treeCopy(node.left)
19     cr = treeCopy(node.right)
20     node = TreeNode(node.data,cl,cr)
21     return node
22 def levelOrder(node):
23     q = deque([node])
24     while q:
25         node = q.popleft() #父结点先出队
26         print(node)
27         if node.left:
28             q.append(node.left) #如果有左结点，左结点入队
29         if node.right:
30             q.append(node.right)
31 if __name__ == "__main__":
32     root = creatTree()
33     new_Tree = treeCopy(root)
34     levelOrder(new_Tree)

六、树的实际应用-二叉搜索树

　　包括二叉树的搜索（search）和插入（insert）

　　分析：二叉树的搜索，类似与二分法的搜索，每次将要搜索的值与父结点比较，在父结点不为空以及父结点的值和要搜索的值不相等的情况下，比较父结点的值和要搜索的值大小关系，小于父结点，则将左结点取作父结点，否则将右结点取作父结点。对搜索进行改进可以有利于插入算法，改进就是在原来返回结点基础上返回该结点的父结点。

　　　　二叉树的插入，调用改进的搜索算法，先利用搜索算法检索二叉树中是否有这个值，如果有，那么不必插入，直接返回，停止操作；如果没有，那么就创建一个数值等于要插入数的结点，然后，如果这是一个空树，直接将该结点作为二叉树的根结点，如果不是空树，根据改进的搜索算法是返回值中的parent值，搜索返回值中node = None,但是parent返回的是最接近K值的一个结点，所以只需要比较K值和父结点数值的大小：K<父结点数值，将新结点插入到父结点左侧，否则插入到父结点右侧

　　python代码实现：

 1 from TreeNode import TreeNode
 2 from levelOrder import levelOrder,creatTree
 3 class BinarySearchTree():
 4     def __init__(self):
 5         self.root = None
 6 #======================搜索算法=====================
 7     def search(self,k):
 8         node = self.root
 9         while node != None and k != node.data:
10             if k < node.data:
11                 node = node.left
12             else:
13                 node = node.right
14         return node
15 #=====================改进的搜索算法,不止找到这个数所在的结点，也找到该结点的子结点==================
16     def _search(self,k):
17         parent = None
18         node = self.root
19         while node and k != node.data:
20             parent = node
21             if k < node.data:
22                 node = node.left
23             else:
24                 node = node.right
25         return node ,parent
26 #=====================插入算法，调用了改进的搜索算法=================================================
27     def insert(self,k):
28         node,parent = self._search(k)
29         if node:
30             return  #如果node有值，也就意味着在原本的树的结构中含有要插入的这个值，直接返回，不必进行插入操作了
31 
32         node = TreeNode(k) #创建一个新的结点，这个结点的数值为k，这个结点的左右结点都为空
33         if parent is None:
34             self.root = node  # 考虑极端情况，假设是一个空树，每一项都是空，那么查找的时候查找的父结点自然也是空，这时直接将要插入的数作为这个树的根结点即可
35         # 在调用搜索函数查找的过程中，虽然没有找到和K匹配的结点，但是父结点就已经是和这个k值最接近的结点，只需要根据k值和父结点的大小就行比较，确定将新结点作为父结点的左结点还是右结点即可
36         elif k < parent.data:
37             parent.left = node
38         else:
39             parent.right = node
40 
41 if __name__ == '__main__':
42     # root = creatTree()
43     bst = BinarySearchTree() #只是创建了一个二叉树类
44     bst.insert(10)
45     bst.insert(5)
46     bst.insert(15)
47     levelOrder(bst.root)