2023年6月22日发(作者：)

python算法⼆叉树总结整理内容：　　（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 s11 #=========================================加⼊缓存机制，可以超级快的提⾼计算速度，因为属于迭代算法，每⼀次计算都要去先算前⾯n的值，所以加⼊缓存可以将之前算的都存下来==================12 def count(n):13 # root :114 # left :k [0,n-1]15 #right :n-k-116 # if n == 0:17 # return 1 #直接将n=0,s=1这种情况加⼊字典18 s = (n,0)19 if s:20 return s #如果s不是0，直接返回21 # s = 0 #s = (n,0)的意思就是，如果缓存cache中有n，那么就将n赋值给s,如果缓存cache中没有n，那么就将缓存的默认参数0赋值给s22 # 所以，上⾯的代码就已经将s=0的可能考虑在内了23 for k in range(n):24 s += count(k) * count(n-k-1)25 [n] = s #将新计算的n和对应的S加⼊缓存字典26 return s27 = {0:1} #创建⼀个缓存，⽤于存储已经计算过的n，默认情况，n=0时，s=128 print(count(100))

⼆、创建⼆叉树　　分析：创建⼆叉树，其实就是先创建结点，然后给各个结点建⽴⽗⼦或者兄弟关系；采⽤python中的类来创建结点，利⽤构造器来给这个类初始化　　python代码实现：

1 class TreeNode(object): 2 def __init__(self,data,left = None, right = None): #初始化结点，因为左右结点都可能为空，所以默认设置左右结点的值为空，如果没有传⼊左右结点就是空，有的话则是传⼊的结点 3 = data #这个结点需要有数值 4 = left #这个结点可能有左结点 5 = right #这个结点可能有右结点 6

7 def __str__(self): #对结点数值输出做的改进，输出结点的时候，⾃动输出为结点的数值，也就是不⽤写中的data 8 return (str()) 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 # = B #在构造E的时候并没有给E的左结点赋值，只是构造出来，但是可以通过后期给赋值16 A,B,C,D,E,F,G,H,I = [TreeNode(X) for X in 'ABCDEFGHI'] #利⽤列表迭代的⽅法创建独⽴结点17 #=================================给各个结点之间创建联系=============================18 = B19 = C20 = D21 = E22 = F23 = G24 = H25 = I26 # print() #输出测试，输出C的右结点的值，也就是F，但是可以做改进，不⽤写data27 print()三、遍历⼆叉树　　遍历⼆叉树也就是⼆叉树的每⼀个结点都要访问到，根据遍历的顺序，分为先序遍历、中序遍历、后序遍历和层序遍历；先序遍历：根左右；中序遍历：左根右；后续遍历：左右根；层序遍历：每⼀层⾃左向右。（1）先序遍历　　分析：遍历的过程先遍历传⼊的根结点root,然后递归的遍历根结点的左结点作为根结点的⼦树，然后递归的遍历根结点的右结点作为根结点的⼦树；整个递归的结束条件，应该是这个根结点不再有左右结点。代码实现：from TreeNode import TreeNodedef creatTree(): A, B, C, D, E, F, G, H, I = [TreeNode(X) for X in 'ABCDEFGHI'] # 利⽤列表迭代的⽅法创建独⽴结点 # =================================给各个结点之间创建联系============================= = B = C = D = E = F = G = H = I return Adef preOrder(node): if node is None: return print() preOrder() preOrder()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 = B 6 = C 7 = D 8 = E 9 = F10 = G11 = H12 = I13 return A14 #===============先序遍历==========================================15 # def preOrder(node):16 # if node is None:17 # return18 # print()19 # preOrder()20 # preOrder()21

22 #================中序遍历===========================================23 def inOrder(node):24 if node is None:25 return26 inOrder()27 print()28 inOrder()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 = B 6 = C 7 = D 8 = E 9 = F10 = G11 = H12 = I13 return A14 #===============先序遍历==========================================15 # def preOrder(node):16 # if node is None:17 # return18 # print()19 # preOrder()20 # preOrder()21

22 #================中序遍历===========================================23 # def inOrder(node):24 # if node is None:25 # return26 # inOrder()27 # print()28 # inOrder()29 #================后序遍历===========================================30 def postOrder(node):31 if node is None:32 return33 postOrder()34 postOrder()35 print()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 = B 7 = C 8 = D 9 = E10 = F11 = G12 = H13 = I14 return A15 def preOrder(node):16 s = []17 while True:18 while node:19 print(node)20 (node)21 node = 22 if not s:23 break24 node = ().right25 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 = B 9 = C10 = D11 = E12 = F13 = G14 = H15 = I16 return A17 def levelOrder(node):18 q = deque([node])19 while q:20 node = t() #⽗结点先出队21 print(node)22 if :23 () #如果有左结点，左结点⼊队24 if :25 ()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 = B 7 = C 8 = D 9 = E10 = F11 = G12 = H13 = I14 return A15 def deep(node):16 if node is None:17 return 018 dl = deep()19 dr = deep()20 dp = max(dl,dr) + 121 return dp22 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 = B 9 = C10 = D11 = E12 = F13 = G14 = H15 = I16 return A17 def deep(node):18 if node is None:19 return 020 dl = deep()21 dr = deep()22 dp = max(dl,dr) + 123 return dp24 #================================================以迭代的⽅式计算深度============================================25 def deep2(node):26 q = deque([(node,1)]) #以元祖的形式来表⽰结点的值和深度27 while q:28 (node,d) = t()29 if :30 ((,d+1)) #前⾯抛出过程中，抛出的d是⽗结点的深度，给⼦节点赋值深度的时候就需要在⽗结点深度的基础上加131 if :32 ((,d+1))33 return d34 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 = B 7 = C 8 = D 9 = E10 = F11 = G12 = H13 = I14 return A15 def treeCopy(node):16 if node is None:17 return None18 cl = treeCopy()19 cr = treeCopy()20 node = TreeNode(,cl,cr)21 return node22 def levelOrder(node):23 q = deque([node])24 while q:25 node = t() #⽗结点先出队26 print(node)27 if :28 () #如果有左结点，左结点⼊队29 if :30 ()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 = None 6 #======================搜索算法===================== 7 def search(self,k): 8 node = 9 while node != None and k != :10 if k < :11 node = 12 else:13 node = 14 return node15 #=====================改进的搜索算法,不⽌找到这个数所在的结点，也找到该结点的⼦结点==================16 def _search(self,k):17 parent = None18 node = 19 while node and k != :20 parent = node21 if k < :22 node = 23 else:24 node = 25 return node ,parent26 #=====================插⼊算法，调⽤了改进的搜索算法=================================================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 = node # 考虑极端情况，假设是⼀个空树，每⼀项都是空，那么查找的时候查找的⽗结点⾃然也是空，这时直接将要插⼊的数作为这个树的根结点即可35 # 在调⽤搜索函数查找的过程中，虽然没有找到和K匹配的结点，但是⽗结点就已经是和这个k值最接近的结点，只需要根据k值和⽗结点的⼤⼩就⾏⽐较，确定将新结点作为⽗结点的左结点还是右结点即可36 elif k < :37 = node38 else:39 = node40

41 if __name__ == '__main__':42 # root = creatTree()43 bst = BinarySearchTree() #只是创建了⼀个⼆叉树类44 (10)45 (5)46 (15)47 levelOrder()