我們學習樹的時候，一些地方用到了遞歸，但是可能沒意識到這里面都是分治的思想

=============================================================================

結合這幾個例子，體會一下樹形結構

樹本來就是一個天然的遞歸結構，每一個遞歸都對應著一個遞歸樹

就二叉樹而言，每一個二叉樹對應著一個左子樹，一個右子樹

都不用我們思考怎么劃分子問題，現在兩個子問題就已經劃分好了

那么每一棵樹對應三部分：當前結點，左子樹，右子樹

那么我們處理原問題，只需要對應處理這三部分就可以了

遞歸實現的出口是什么，出口就是葉子結點的左右子樹，也就是空樹，出口就是空樹return

=============================================================================

# -*- coding: utf-8 -*-# 構造一棵樹 # 首先需要定義結點 class BinTNode:def __init__(self,data=None,left =None,right =None):self.data =dataself.left =leftself.right =right # ============================================================================= # 結合這幾個例子，體會一下樹形結構 # 樹本來就是一個天然的遞歸結構，每一個遞歸都對應著一個遞歸樹 # 就二叉樹而言，每一個二叉樹對應著一個左子樹，一個右子樹 # 都不用我們思考怎么劃分子問題，現在兩個子問題就已經劃分好了 # 那么每一棵樹對應三部分：當前結點，左子樹，右子樹 # 那么我們處理原問題，只需要對應處理這三部分就可以了 # 遞歸實現的出口是什么，出口就是葉子結點的左右子樹，也就是空樹，出口就是空樹return # =============================================================================# 我們統計樹的結點，當前結點1個+左子樹的結點和+右子樹的結點和 def count_TreeNodes(root):if not root:return 0else:return 1 + count_TreeNodes(root.left) + count_TreeNodes(root.right)# 我們統計樹的權值和，當前結點權值+左子樹的權值和+右子樹的權值和 def sum_TreeValues(root):if not root:return 0else:return root.data + sum_TreeValues(root.left) + sum_TreeValues(root.right) # 同樣的道理，獲取樹的高度 def height_Tree(root):if not root:return 0else:return 1 + max(height_Tree(root.left),height_Tree(root.right)) # 合并子樹 # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = Noneclass Solution(object):def mergeTrees(self, t1, t2):""":type t1: TreeNode:type t2: TreeNode:rtype: TreeNode""" if t1 and t2:t1.val += t2.valt1.left = self.mergeTrees(t1.left, t2.left)t1.right = self.mergeTrees(t1.right, t2.right) else:t1 = t1 or t2 return t1

我們討論樹的遍歷，對于一棵樹：

先根遍歷：遍歷當前結點–>遍歷左子樹–>遍歷右子樹

中根遍歷：遍歷左子樹–>遍歷當前結點–>遍歷右子樹

后跟遍歷：遍歷左子樹–>遍歷右子樹–>遍歷當前結點

這是從整個問題來考慮

還有一個思考為什么這3種遍歷成了深度優先搜索了？

只要是遞歸必然是深度優先，因為只要是遞歸就必須一直探到底部，然后逐步返回

整個看起來，先處理左邊，再處理右邊，很像寬度優先是吧，其實所有的遞歸都是深度優先

處理時應該從整體分解子問題的角度來分析

# 我們討論樹的遍歷，對于一棵樹： # 先根遍歷：遍歷當前結點-->遍歷左子樹-->遍歷右子樹 # 中根遍歷：遍歷左子樹-->遍歷當前結點-->遍歷右子樹 # 后跟遍歷：遍歷左子樹-->遍歷右子樹-->遍歷當前結點 # 這是從整個問題來考慮 # 還有一個思考為什么這3種遍歷成了深度優先搜索了？ # 只要是遞歸必然是深度優先，因為只要是遞歸就必須一直探到底部，然后逐步返回 # 整個看起來，先處理左邊，再處理右邊，很像寬度優先是吧，其實所有的遞歸都是深度優先 # 處理時應該從整體分解子問題的角度來分析 def preorder(root):if not root:returnelse:print(root.data,end=' ')preorder(root.left)preorder(root.right)def inorder(root):if not root:returnelse:inorder(root.left)print(root.data,end=' ')inorder(root.right)def postorder(root):if not root:returnelse:postorder(root.left)postorder(root.right)print(root.data,end=' ')

運行結果：

root = BinTNode(1,BinTNode(2,BinTNode(4),BinTNode(5)),BinTNode(3,BinTNode(6),BinTNode(7))) print(count_TreeNodes(root)) print(sum_TreeValues(root)) print('preorder:',end='') preorder(root) print(end='\n') print('inorder:',end='') inorder(root) print(end='\n') print('postorder:',end='') postorder(root) print(end='\n') print('Height:',end='') print(height_Tree(root)) print(end='\n')runfile('D:/share/test/TreeRecursion.py', wdir='D:/share/test') 7 28 preorder:1 2 4 5 3 6 7 inorder:4 2 5 1 6 3 7 postorder:4 5 2 6 7 3 1 Height:3 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的树形结构：二叉树，分治，合并子树，递归的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。