<center id="qkqgy"><optgroup id="qkqgy"></optgroup></center>
  • <menu id="qkqgy"></menu>
    <nav id="qkqgy"></nav>
    <xmp id="qkqgy"><nav id="qkqgy"></nav>
  • <xmp id="qkqgy"><menu id="qkqgy"></menu>
    <menu id="qkqgy"><menu id="qkqgy"></menu></menu>
    <tt id="qkqgy"><tt id="qkqgy"></tt></tt>


  • 遍歷二叉樹就是以一定的規則將二叉樹中的結點排列成一個線性序列,從而得到二叉樹節點的各種遍歷序列。其實質就是對一個非線性結構進行線性操作,使在這個序列中,除了第一個和最后一個結點,每個結點都有一個直接前驅和直接后繼。
    先序遍歷
    如果二叉樹為空,則什么也不做;
    否則:
    1.訪問根節點
    2.先序遍歷左子樹
    3.先序遍歷右子樹

    中序遍歷
    如果二叉樹為空,則什么也不做;
    否則:
    1.中序遍歷左子樹
    2.訪問根節點
    3.中序遍歷右子樹
    后序遍歷
    如果二叉樹為空,則什么也不做;
    否則:
    1.后序遍歷左子樹
    2.后序遍歷右子樹
    3.訪問根節點

    層次遍歷:

    要進行層次遍歷需要借助一個隊列。先將二叉樹根結點入隊,然后出隊,訪問該結點,如果它有左子樹,則將左子樹根結點入隊;如果它有右子樹,則將右子樹根結點入隊。然后出隊,對出隊結點訪問,如此反復,直到隊列為空。

    代碼如下:
    # 二叉樹類 class BTree(object): # 初始化 def __init__(self, data=None, left=None,
    right=None): self.data = data # 數據域 self.left = left # 左子樹 self.right = right #
    右子樹 # 前序遍歷:中->左->右 def preorder(self): if self.data: print(self.data, end=' ')
    if self.left: self.left.preorder() if self.right: self.right.preorder() #
    中序遍歷:左->中->右 def inorder(self): if self.left : self.left.inorder() if self.data
    : print(self.data, end=' ') if self.right : self.right.inorder() # 后序遍歷:左->右->中
    def postorder(self): if self.left : self.left.postorder() if self.right : self.
    right.postorder() if self.data : print(self.data, end=' ') # 層序遍歷: def
    levelorder(self): # 返回某個節點的左孩子 def LChild_Of_Node(node): return node.left if
    node.left else None # 返回某個節點的右孩子 def RChild_Of_Node(node): return node.right if
    node.right else None # 層序遍歷列表 level_order = [] #
    傳入的self為根結點,添加根節點中的數據到level_order,即:二叉樹的根節點入隊 if self.data : print("self:",self.
    data) level_order.append([self]) # 二叉樹的高度 height = self.height() if height >= 1:
    # 對第二層及其以后的層數進行操作, 在level_order中添加節點而不是數據 for _ in range(2, height + 1): level =
    [] # 該層的節點 for node in level_order[-1]: # 如果它有左子樹,則將左子樹節點入隊 if LChild_Of_Node(
    node): level.append(LChild_Of_Node(node)) # 如果它有右子樹,則將右子樹結點入隊 if RChild_Of_Node(
    node): level.append(RChild_Of_Node(node)) if level: # 如果該層非空,則添加該層 level_order.
    append(level) # 取出每層中的數據 for i in range(0, height): # 層數 for index in range(len(
    level_order[i])): level_order[i][index] = level_order[i][index].data return
    level_order# 二叉樹的高度 def height(self): # 空的樹高度為0, 只有root節點的樹高度為1 if self.data is
    None: return 0 #左右子樹都為空,則當前結點為葉子結點 elif self.left is None and self.right is None
    : return 1 elif self.left is None and self.right : return 1 + self.right.height(
    ) elif self.left and self.right is None: return 1 + self.left.height() else:
    return 1 + max(self.left.height(), self.right.height()) # 二叉樹的葉子節點 def leaves(
    self): if self.data is None: return None elif self.left is None and self.right
    is None: print(self.data, end=' ') elif self.left is None and self.right : self.
    right.leaves() elif self.right is None and self.left : self.left.leaves() else:
    self.left.leaves() self.right.leaves() if __name__ == '__main__': right_tree =
    BTree(6) right_tree.left = BTree(2) right_tree.right = BTree(4) left_tree =
    BTree(5) left_tree.left = BTree(1) left_tree.right = BTree(3) tree = BTree(11)
    tree.left = left_tree tree.right = right_tree left_tree = BTree(7) left_tree.
    left= BTree(3) left_tree.right = BTree(4) right_tree = tree # 增加新的變量 tree =
    BTree(18) tree.left = left_tree tree.right = right_tree print('先序遍歷為:') tree.
    preorder() print() print('中序遍歷為:') tree.inorder() print() print('后序遍歷為:') tree.
    postorder() print() print('層序遍歷為:') level_order = tree.levelorder() print(
    level_order) print() height = tree.height() print('樹的高度為%s.' % height) print(
    '葉子節點為:') tree.leaves() print() # 先序遍歷為: # 18 7 3 4 11 5 1 3 6 2 4 # 中序遍歷為: # 3
    7 4 18 1 5 3 11 2 6 4 # 后序遍歷為: # 3 4 7 1 3 5 2 4 6 11 18 # 層序遍歷為: # self: 18 #
    [[18], [7, 11], [3, 4, 5, 6], [1, 3, 2, 4]] # # 樹的高度為4. # 葉子節點為: # 3 4 1 3 2 4
    也可以換一種方式構造二叉樹,利用層序遍歷的原理逐層創建,代碼如下:
    # 二叉樹類 class BTree(object): # 初始化 def __init__(self, data=None, left=None,
    right=None): self.data = data # 數據域 self.left = left # 左子樹 self.right = right #
    右子樹 # 前序遍歷:中->左->右 def preorder(self): if self.data: print(self.data, end=' ')
    if self.left: self.left.preorder() if self.right: self.right.preorder() #
    中序遍歷:左->中->右 def inorder(self): if self.left : self.left.inorder() if self.data
    : print(self.data, end=' ') if self.right : self.right.inorder() # 后序遍歷:左->右->中
    def postorder(self): if self.left : self.left.postorder() if self.right : self.
    right.postorder() if self.data : print(self.data, end=' ') # 層序遍歷: def
    levelorder(self): # 返回某個節點的左孩子 def LChild_Of_Node(node): return node.left if
    node.left else None # 返回某個節點的右孩子 def RChild_Of_Node(node): return node.right if
    node.right else None # 層序遍歷列表 level_order = [] #
    傳入的self為根結點,添加根節點中的數據到level_order,即:二叉樹的根節點入隊 if self.data : print("self:",self.
    data) level_order.append([self]) # 二叉樹的高度 height = self.height() if height >= 1:
    # 對第二層及其以后的層數進行操作, 在level_order中添加節點而不是數據 for _ in range(2, height + 1): level =
    [] # 該層的節點 for node in level_order[-1]: # 如果它有左子樹,則將左子樹節點入隊 if LChild_Of_Node(
    node): level.append(LChild_Of_Node(node)) # 如果它有右子樹,則將右子樹結點入隊 if RChild_Of_Node(
    node): level.append(RChild_Of_Node(node)) if level: # 如果該層非空,則添加該層 level_order.
    append(level) # 取出每層中的數據 for i in range(0, height): # 層數 for index in range(len(
    level_order[i])): level_order[i][index] = level_order[i][index].data return
    level_order# 二叉樹的高度 def height(self): # 空的樹高度為0, 只有root節點的樹高度為1 if self.data is
    None: return 0 #左右子樹都為空,則當前結點為葉子結點 elif self.left is None and self.right is None
    : return 1 elif self.left is None and self.right : return 1 + self.right.height(
    ) elif self.left and self.right is None: return 1 + self.left.height() else:
    return 1 + max(self.left.height(), self.right.height()) # 二叉樹的葉子節點 def leaves(
    self): if self.data is None: return None elif self.left is None and self.right
    is None: print(self.data, end=' ') elif self.left is None and self.right : self.
    right.leaves() elif self.right is None and self.left : self.left.leaves() else:
    self.left.leaves() self.right.leaves() # 利用列表構造二叉樹 # 列表中至少有一個元素 def
    create_BTree_By_List(array): i = 1 # 將原數組拆成層次遍歷的數組,每一項都儲存這一層所有的節點的數據 level_order
    = [] sum = 1 #二叉樹每層元素數目為pow(2,n-1),索引為i-1:i*2-1 while sum < len(array):
    level_order.append(array[i-1:2*i-1]) i *= 2 sum += i level_order.append(array[i-
    1:])#如果不是滿二叉樹,則剩余的放到最后一層 # BTree_list: 這一層所有的節點組成的列表 # forword_level:
    上一層節點的數據組成的列表 def Create_BTree_One_Step_Up(BTree_list, forword_level):
    new_BTree_list= []#最終得到一層有左右子樹的結點 i = 0 for elem in forword_level:
    #這是父節點的集合,給結點分配左右子樹 root = BTree(elem) if 2*i < len(BTree_list):#左子樹 root.left =
    BTree_list[2*i] if 2*i+1 < len(BTree_list):#右子樹 root.right = BTree_list[2*i+1]
    new_BTree_list.append(root) i += 1 return new_BTree_list # 只有一層:即只有一個節點 if len(
    level_order) == 1: return BTree(level_order[0][0]) else: # 二叉樹的層數大于1 #
    創建最后一層的節點列表 BTree_list = [BTree(elem) for elem in level_order[-1]] #
    從下往上,逐層創建二叉樹:BTree_list是每一層的節點集合 for i in range(len(level_order)-2, -1, -1):
    BTree_list= Create_BTree_One_Step_Up(BTree_list, level_order[i]) return
    BTree_list[0] if __name__ == '__main__': array = [chr(x) for x in range(65,91)]
    tree= create_BTree_By_List(array) print('先序遍歷為:') tree.preorder() height = tree.
    height() print('樹的高度為%s.'%height) print('層序遍歷為:') level_order = tree.levelorder(
    ) print(level_order) print('葉子節點為:') tree.leaves() # 先序遍歷為: # A B D H P Q I R S
    E J T U K V W C F L X Y M Z G N O 樹的高度為5. # 層序遍歷為: # self: A # [['A'], ['B',
    'C'], ['D', 'E', 'F', 'G'], ['H', 'I', 'J', 'K', 'L', 'M', 'N', 'O'], ['P',
    'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']] # 葉子節點為: # P Q R S T U V W X
    Y Z N O
    <>非遞歸遍歷

    前序遍歷

    根據前序遍歷訪問的順序,優先訪問根結點,然后再分別訪問左孩子和右孩子。即對于任一結點,其可看做是根結點,因此可以直接訪問,訪問完之后,若其左孩子不為空,按相同規則訪問它的左子樹;當訪問完左子樹時,再訪問它的右子樹
    對于任一結點P:
    1)訪問結點P,并將結點P入棧

    2)判斷結點P的左孩子是否為空,若為空,則取棧頂結點并進行出棧操作,并將棧頂結點的右孩子置為當前的結點P,循環至1);若不為空,則將將結點P入棧并把P的左孩子置為當前的結點P
    3)直到P為NULL并且棧為空,則遍歷結束。
    def preorder_non_recursive(self): mystack = [] # 保存節點的棧 tmp = self # 保存根節點
    while mystack or tmp: # 訪問左子樹直至葉子節點 while tmp: print(tmp.data, end=" ") mystack.
    append(tmp) tmp = tmp.left # 左子樹為空之后再訪問右子樹 tmp = mystack.pop() tmp = tmp.right
    print("stack", mystack)
    中序遍歷

    根據中序遍歷的順序,對于任一結點,優先訪問其左孩子,而左孩子結點又可以看做一根結點,然后繼續訪問其左孩子結點,直到遇到左孩子結點為空的結點才進行訪問,然后按相同的規則訪問其右子樹
    對于任一結點P
    1)若其左孩子不為空,則將P入棧并將P的左孩子置為當前的P,然后對當前結點P再進行相同的處理
    2)若其左孩子為空,則取棧頂元素并進行出棧操作,訪問該棧頂結點,然后將當前的P置為棧頂結點的右孩子
    def inorder_non_recursive(self): mystack = [] tmp = self while mystack or tmp:
    # 從根節點開始,尋找左子樹并入棧 while tmp: mystack.append(tmp) tmp = tmp.left # 出棧并處理當前節點的右子樹
    tmp= mystack.pop() print(tmp.data, end=" ") tmp = tmp.right
    后序遍歷

    在后序遍歷中,要保證左孩子和右孩子都已被訪問并且左孩子在右孩子前訪問才能訪問根結點,這就為流程的控制帶來了難題。
    對于任一結點P,將其入棧,然后沿其左子樹一直往下搜索,直到搜索到沒有左孩子的結點,此時該結點出現在棧頂,但是此時不能將其出棧并訪問,因此其右孩子還為被訪問。
    所以接下來按照相同的規則對其右子樹進行相同的處理,當訪問完其右孩子時,該結點又出現在棧頂,此時可以將其出棧并訪問。

    這樣就保證了正確的訪問順序。可以看出,在這個過程中,每個結點都兩次出現在棧頂,只有在第二次出現在棧頂時,才能訪問它。因此需要多設置一個變量標識該結點是否是第一次出現在棧頂。
    def postorder_non_recursive(self): """利用堆棧后序遍歷""" stack1 = [] stack2 = []
    stack1.append(self) while stack1: # 找出后序遍歷的逆序,存放在 stack2中 node = stack1.pop() if
    node.left: stack1.append(node.left) if node.right: stack1.append(node.right)
    stack2.append(node) while stack2: # 將 stack2中的元素出棧,即是后序遍歷序列 print(stack2.pop().
    data, end=' ')

    技術
    今日推薦
    閱讀數 486
    閱讀數 80
    閱讀數 32
    閱讀數 28
    下載桌面版
    GitHub
    百度網盤(提取碼:draw)
    Gitee
    云服務器優惠
    阿里云優惠券
    騰訊云優惠券
    華為云優惠券
    站點信息
    問題反饋
    郵箱:ixiaoyang8@qq.com
    QQ群:766591547
    關注微信
    巨胸美乳无码人妻视频