樹Tree

• 數據結構中具有層次關系的非線性結構.
• 生活中常見各種樹結構的應用
  • 家譜樹
    
  • Windows文件系統
    

樹的定義

• 樹為n個結點的有限集合T.

  • n=0，沒有結點，稱為空樹.
  • n>0，必有一根.
    • 根root結點，沒有前驅結點.
    • 其余n-1個結點可以劃分成m棵根的子樹.

• 特點

  • 如下圖，A為根結點，B、C、D為根結點的子樹.
  • 子樹又有多棵子樹組成.
  • 每棵子樹除根節點外，其余每個結點有且僅有一個直接前驅，但可以有0個或多個直接后繼.
  • 形成樹的遞歸特性.
    

樹的基本概念

• 結點：包含一個數據元素及若干指向其他結點的分支信息.
• 結點分類：根結點、葉子結點、非葉子結點、孩子結點、雙親結點、兄弟結點以及堂兄弟結點.
• 結點的度：一個結點的子樹個數.
• 樹的度：樹中所有結點的度的最大值.
• 葉子結點：度為0的結點.
• 分支結點：度不為0的結點.
• 結點的層次：從根結點開始定義，根結點的層次為1，根的直接后繼的層次為2，以此類推.
• 結點的層序編號：將樹中的結點按從上到下、同層按從左到右的次序排成一個線性序列，依次給他們編以連續的自然數.
• 森林：m棵互不相交的樹的集合.
• 孩子結點：相鄰的兩層之間用直線連接的層數更下面的結點.
• 雙親結點：相鄰的兩層之間用直線連接的層數更上面的結點.
• 兄弟結點：同一層的結點之間為兄弟結點.
• 堂兄弟結點：同一層的雙親不同的結點.
• 祖先結點：當前結點中所有上面層級與之鏈接的一脈結點.
• 子孫結點：當前結點中所有下面層級且與之鏈接的一脈結點.
• 前輩結點：當前結點以上層級的所有結點.
• 后輩結點：當前結點以下層級的所有結點.
• 有序樹：如果在樹的每一組兄弟結點之間定義一個從左到右的次序，則得到一顆有序樹.
  

樹的存儲結構

雙親表示法

• 定義：用一組連續的存儲單元存儲樹的每個結點，每個結點設置指針域parent指向雙親.
• 根結點指針域設置為-1.
• 按層序將每個結點編號.
• 按結點的層序編號，依次在列表中對應單元存儲一個結點(data, parent).
  • data：存儲樹結點中的數據元素.
  • parent：存儲該結點的雙親結點的列表下標值.
• 存儲代碼定義

class Node(object):def __init__(self, data, parent):self.data = dataself.parent = parent

• 樹的示意圖
  
• 雙親表示存儲圖
  

孩子表示法

• 定義：把每個結點的孩子結點排列起來，以單鏈表為存儲結構.
• 存儲結構將所有結點按層序編號順序存儲在列表中，用單鏈表的存儲結構表示該結點的孩子結點.
• 樹的示意圖
  
• 存儲結構表
  

孩子兄弟表示法

• 定義：樹的左孩子右兄弟表示法指的是左邊的孩子結點接管右邊的孩子結點，鏈表中每個結點的兩個鏈域分別指向該結點的左孩子和右兄弟.
• 采用孩子兄弟表示法進行轉換的流程示意圖：
  

二叉樹

• 作為一類非常重要的特殊的樹狀結構.
• 特點每個結點至多有2個孩子結點，并且有左右之分.
• 左邊的孩子成為左孩子結點，位于右邊的孩子結點稱為右孩子結點.

二叉樹與度不超過２的普通樹的不同之處

• 在普通樹中，若結點只有一個孩子結點，無左右之分.
• 二叉樹為有序數，左子樹和右子樹的次序不能顛倒，即使樹中某個結點只有一棵子樹，也要區別是左子樹還是右子樹.
• 在有序樹中，雖然一個結點的孩子結點之間是有左右次序之分的，但是若該結點只有一個孩子結點，則無須區分其左右次序.
• 在二叉樹中，即使是一個孩子結點也要做出左右孩子結點.

二叉樹的基本形態

• 1.空二叉樹
• 2.僅有根結點的二叉樹
• 3.僅有一棵左子樹的二叉樹
• 4.僅有一棵右子樹的二叉樹
• 5.有兩棵子樹的二叉樹

二叉樹的分類

• 滿二叉樹：一棵高度為k且有2^k-1個結點的二叉樹

  • 葉子結點只能出現在最后一層，
  • 非葉子結點都在左右子樹，
  • 在同樣高度的二叉樹中，滿二叉樹的結點數最多，葉子數最多.
    

• 完全二叉樹：若滿二叉樹最后一層的結點，從右向左連續缺若干結點，就是完全二叉樹

  • 葉子結點只能出現在最下兩層，
  • 最下層的葉子結點一定集中在左邊連續位置，
  • 如果結點的度為1，那么該結點只有左孩子結點，不存在只有右孩子結點的情況，
  • 有同樣結點數的二叉樹，完全二叉樹的高度最小.
    

• 聯系與區別

  • 若某個結點沒有左孩子的結點，那么它一定沒有右孩子結點
  • 滿二叉樹除葉子結點外，其中每個結點都有兩個孩子結點，每層的結點數都達到最大
  • 滿二叉樹一定也是完全二叉樹，但完全二叉樹不一定為滿二叉樹.

二叉樹的性質

• 1.若二叉樹的層次從1開始計數，則在二叉樹的第i層最多有2^(i-1)個結點.
• 2.高度為k的二叉樹最多有(2^k)-1個結點.
• 3.高度為k的二叉樹最少有k個結點.
• 4.具有n個結點的二叉樹的高度最多為n.
• 5.具有n個結點的二叉樹的高度最少為$${\log }_{2}n+1$$
• 6.對于任何一棵二叉樹，如果其葉子結點有a個，度為2的結點有b個，則有a=b+1.
• 7.n個結點可以組成$$\frac{1}{n+1}?\frac{(2n)!}{n!?n!}$$種不同構的二叉樹.
• 8.具有n個結點的完全二叉樹的高度為$${\log }_{2}n+1$$
• 9.如果完全二叉樹各層次結點從1開始編號，即1,2，3，…,n，那么則可得以下關系：
  • 僅當i=1時，結點i為根結點；
  • 當i>1時，結點i的雙親結點編號為i/2(取整)；
  • 結點i的左孩子結點編號為2i；
  • 結點i的右孩子結點編號為2i+1；
  • 若2i>n，則結點i無左孩子結點；
  • 若2i+1>n，則結點i無右孩子結點.
    

二叉樹的順序存儲

• 順序存儲實現

  • 層序編號 = 列表下標值+1
    

• 順序存儲的初始化

    def __init__(self, array):self.array = array  # 順序存儲的數組（完全二叉樹形式）

• 前序遍歷

    def preOrder(self):"""前序遍歷：根 -> 左 -> 右"""result = []def _preorder(index):if index >= len(self.array) or self.array[index] is None:returnresult.append(self.array[index])_preorder(2 * index + 1)  # 左子節點_preorder(2 * index + 2)   # 右子節點_preorder(0)  # 從根節點開始return result

• 中序遍歷

    def midOrder(self):"""中序遍歷：左 -> 根 -> 右"""result = []def _inorder(index):if index >= len(self.array) or self.array[index] is None:return_inorder(2 * index + 1)result.append(self.array[index])_inorder(2 * index + 2)_inorder(0)return result

• 后序遍歷

    def postOrder(self):"""后序遍歷：左 -> 右 -> 根"""result = []def _postorder(index):if index >= len(self.array) or self.array[index] is None:return_postorder(2 * index + 1)_postorder(2 * index + 2)result.append(self.array[index])_postorder(0)return result

• 順序存儲的調試與代碼集合

class SeqTree:def __init__(self, array):self.array = array  # 順序存儲的數組（完全二叉樹形式）def preOrder(self):"""前序遍歷：根 -> 左 -> 右"""result = []def _preorder(index):if index >= len(self.array) or self.array[index] is None:returnresult.append(self.array[index])_preorder(2 * index + 1)  # 左子節點_preorder(2 * index + 2)   # 右子節點_preorder(0)  # 從根節點開始return resultdef midOrder(self):"""中序遍歷：左 -> 根 -> 右"""result = []def _inorder(index):if index >= len(self.array) or self.array[index] is None:return_inorder(2 * index + 1)result.append(self.array[index])_inorder(2 * index + 2)_inorder(0)return resultdef postOrder(self):"""后序遍歷：左 -> 右 -> 根"""result = []def _postorder(index):if index >= len(self.array) or self.array[index] is None:return_postorder(2 * index + 1)_postorder(2 * index + 2)result.append(self.array[index])_postorder(0)return result# 測試案例
if __name__ == "__main__":print('PyCharm')# 測試樹結構：#       1#     /   \#    2     3#     \   / \#      4 5   6arr = [1, 2, 3, None, 4, 5, 6]tree = SeqTree(arr)print("前序遍歷:", tree.preOrder())      # 輸出: [1, 2, 4, 3, 5, 6]print("中序遍歷:", tree.midOrder())       # 輸出: [2, 4, 1, 5, 3, 6]print("后序遍歷:", tree.postOrder())     # 輸出: [4, 2, 5, 6, 3, 1]

• 順序存儲的缺點：
• 由于必須按完全二叉樹的形式來存儲樹中的結點，因此將造成存儲空間的浪費，
• 在最壞的情況下，一個只有k個結點的僅有右孩子結點的二叉樹缺需要2^(k-1)個結點的存儲空間.
• 因此，滿二叉樹和完全二叉樹適合使用順序存儲結構實現.

二叉樹的鏈式存儲

二叉樹的鏈式存儲的結點結構

• 兩個指針域left和right，分別指向左孩子和右孩子結點的指針
• 一個數據域data用于存儲該結點的數據元素
• 二叉樹鏈式存儲結點

class Node(object):def __init__(self, data):self.data = dataself.left = Noneself.right = None

• 三叉樹鏈式存儲結點

class Node(object):def __init__(self, data):self.data = dataself.parent = Noneself.left = Noneself.right = None

樹的遍歷

- 樹的遍歷按某種次序訪問樹中的結點，要求樹中每個結點被訪問一次且僅被訪問一次.

先序遍歷

• 最先訪問根結點，然后訪問樹的左子樹，最后訪問樹的右子樹.

    def preOrder(self, node):"""先序遍歷:param node:樹結點"""if node != None:print(node.data, end=",")self.preOrder(node.left)self.preOrder(node.right)

中序遍歷

• 最先訪問樹的左子樹，然后訪問根結點，最后是訪問樹的右子樹.
• 案例
  
• 遍歷過程：
  • 1.A有左子樹，先訪問左子樹.
  • 2.B沒有左子樹，輸出B.
  • 3.D有左子樹，訪問其左子樹.
  • 4.F沒有左子樹，輸出F.
  • 5.F也沒有右子樹，返回F的根結點D，輸出D.
  • 6.輸出D之后，A的整個左子樹遍歷完畢，返回根結點A，輸出A.
  • 7.C有左子樹，先訪問左子樹.
  • 8.E無左子樹，輸出E.
  • 9.E無左右子樹，返回根結點C，輸出C.
  • C無右子樹，則A的右子樹遍歷完畢.

    def midOrder(self, node):"""中序遍歷:param node::return:"""if node != None:self.midOrder(node.left)print(node.data, end=",")self.midOrder(node.right)

后序遍歷

• 最先訪問樹的左子樹，然后訪問樹的右子樹，最后訪問根結點.

    def postOrder(self, node):"""后序遍歷:param node::return:"""if node != None:self.postOrder(node.left)self.postOrder(node.right)print(node.data, end=",")

輸出二叉樹的葉子結點

    def getLeaf(self, node):"""輸出葉子結點:param node::return:"""if node != None:if node.left == None and node.right == None:print(node.data, end=" ")self.getLeaf(node.left)self.getLeaf(node.right)

輸出二叉樹葉子結點的個數

• 遞歸方法實現：
  • 如果樹為空，葉子結點個數為0
  • 如果只有1個結點，則為1
  • 否則，葉子結點個數 = 左子樹葉子結點個數+右子樹葉子結點個數

    def getLeafCount(self, node):"""輸出葉子結點的個數:param node::return:"""if node == None:leafCount = 0elif node.left == None and node.right == None:leafCount = 1else:leafCount = self.getLeafCount(node.left) + self.getLeafCount(node.right)return leafCount

輸出二叉樹的高度

• 遞歸實現
  • 若樹為空樹，則高度為0
  • 若樹非空，高度應為其左右子樹高度中的最大值加1.

    def height(self, node):"""求二叉樹的高度:param node::return:"""if node != None:leafHeight = self.height(node.left)rightHeight = self.height(node.right)if leafHeight > rightHeight:max = leafHeightelse:max = rightHeightreturn max+1else:return 0

鏈表存儲的調試與代碼集合

class Node(object):def __init__(self, data):self.data = dataself.left = Noneself.right = Noneclass BinaryTree:def __init__(self, root = None):self.root = rootdef preOrder(self, node):"""先序遍歷:param node:樹結點"""if node != None:print(node.data, end=" ")self.preOrder(node.left)self.preOrder(node.right)def midOrder(self, node):"""中序遍歷:param node::return:"""if node != None:self.midOrder(node.left)print(node.data, end=" ")self.midOrder(node.right)def postOrder(self, node):"""后序遍歷:param node::return:"""if node != None:self.postOrder(node.left)self.postOrder(node.right)print(node.data, end=" ")def getLeaf(self, node):"""輸出葉子結點:param node::return:"""if node != None:if node.left == None and node.right == None:print(node.data, end=" ")self.getLeaf(node.left)self.getLeaf(node.right)def getLeafCount(self, node):"""輸出葉子結點的個數:param node::return:"""if node == None:leafCount = 0elif node.left == None and node.right == None:leafCount = 1else:leafCount = self.getLeafCount(node.left) + self.getLeafCount(node.right)return leafCountdef height(self, node):"""求二叉樹的高度:param node::return:"""if node != None:leafHeight = self.height(node.left)rightHeight = self.height(node.right)if leafHeight > rightHeight:max = leafHeightelse:max = rightHeightreturn max+1else:return 0if __name__ == "__main__":#  構建示例樹#       1#     /   \#    2     3#     \   / \#      4 5   6root = Node('1')root.left = Node('2')root.right = Node('3')root.left.right = Node('4')root.right.left = Node('5')root.right.right = Node('6')tree = BinaryTree(root)print("前序遍歷:")tree.preOrder(root)print("\n中序遍歷:")tree.midOrder(root)print("\n后序遍歷:")tree.postOrder(root)print("\n樹的葉子結點:")tree.getLeaf(root)print("\n輸出葉子結點的個數:")print(tree.getLeafCount(root))print("輸出二叉樹的高度:")print(tree.height(root))