亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

python使用遞歸的方式建立二叉樹

系統 1665 0

樹和圖的數據結構,就很有意思啦。

python使用遞歸的方式建立二叉樹_第1張圖片

            
# coding = utf-8

 

 

class BinaryTree:

  def __init__(self, root_obj):

    self.key = root_obj

    self.left_child = None

    self.right_child = None

 

  def insert_left(self, new_node):

    node = BinaryTree(new_node)

    if self.left_child is None:

      self.left_child = node

    else:

      node.left_child = self.left_child

      self.left_child = node

 

  def insert_right(self, new_node):

    node = BinaryTree(new_node)

    if self.right_child is None:

      self.right_child = node

    else:

      node.right_child = self.right_child

      self.right_child = node

 

  def get_right_child(self):

    return self.right_child

 

  def get_left_child(self):

    return self.left_child

 

  def set_root_val(self, obj):

    self.key = obj

 

  def get_root_val(self):

    return self.key

 

 

root = BinaryTree('a')

print(root.get_root_val())

print(root.get_left_child())

root.insert_left('b')

print(root.get_left_child())

print(root.get_left_child().get_root_val())

root.insert_right('c')

print(root.get_right_child())

print(root.get_right_child().get_root_val())

root.get_right_child().set_root_val('hello')

print(root.get_right_child().get_root_val())
          
            
C:\Users\Sahara\.virtualenvs\test\Scripts\python.exe C:/Users/Sahara/PycharmProjects/test/python_search.py

a

None

<__main__.BinaryTree object at 0x00000000024139B0>

b

<__main__.BinaryTree object at 0x00000000024139E8>

c

hello

 

Process finished with exit code 0
          

Python實現二叉樹遍歷的遞歸和非遞歸算法

前序遍歷

            
 # -----------前序遍歷 ------------
  # 遞歸算法
  def pre_order_recursive(self, T):
    if T == None:
      return
    print(T.root, end=' ')
    self.pre_order_recursive(T.lchild)
    self.pre_order_recursive(T.rchild)

  # 非遞歸算法
  def pre_order_non_recursive(self, T):
    """借助棧實現前驅遍歷
    """
    if T == None:
      return
    stack = []
    while T or len(stack) > 0:
      if T:
        stack.append(T)
        print(T.root, end=' ')
        T = T.lchild
      else:
        T = stack[-1]
        stack.pop()
        T = T.rchild

          

中序遍歷

            
# -----------中序遍歷 ------------
  # 遞歸算法
  def mid_order_recursive(self, T):
    if T == None:
      return
    self.mid_order_recursive(T.lchild)
    print(T.root, end=' ')
    self.mid_order_recursive(T.rchild)

  # 非遞歸算法
  def mid_order_non_recursive(self, T):
    """借助棧實現中序遍歷
    """
    if T == None:
      return
    stack = []
    while T or len(stack) > 0:
      if T:
        stack.append(T)
        T = T.lchild
      else:
        T = stack.pop()
        print(T.root, end=' ')
        T = T.rchild

          

后序遍歷

            
# -----------后序遍歷 ------------
  # 遞歸算法
  def post_order_recursive(self, T):
    if T == None:
      return
    self.post_order_recursive(T.lchild)
    self.post_order_recursive(T.rchild)
    print(T.root, end=' ')

  # 非遞歸算法
  def post_order_non_recursive(self, T):
    """借助兩個棧實現后序遍歷
    """
    if T == None:
      return
    stack1 = []
    stack2 = []
    stack1.append(T)
    while stack1:
      node = stack1.pop()
      if node.lchild:
        stack1.append(node.lchild)
      if node.rchild:
        stack1.append(node.rchild)
      stack2.append(node)
    while stack2:
      print(stack2.pop().root, end=' ')
    return

          

層次遍歷

            
# -----------層次遍歷 ------------
  def level_order(self, T):
    """借助隊列(其實還是一個棧)實現層次遍歷
    """
    if T == None:
      return
    stack = []
    stack.append(T)
    while stack:
      node = stack.pop(0) # 實現先進先出
      print(node.root, end=' ')
      if node.lchild:
        stack.append(node.lchild)
      if node.rchild:
        stack.append(node.rchild)
          

完整代碼

            
class NodeTree:
  def __init__(self, root=None, lchild=None, rchild=None):
    """創建二叉樹
    Argument:
      lchild: BinTree
        左子樹
      rchild: BinTree
        右子樹

    Return:
      Tree
    """
    self.root = root
    self.lchild = lchild
    self.rchild = rchild


class BinTree:

  # -----------前序遍歷 ------------
  # 遞歸算法
  def pre_order_recursive(self, T):
    if T == None:
      return
    print(T.root, end=' ')
    self.pre_order_recursive(T.lchild)
    self.pre_order_recursive(T.rchild)

  # 非遞歸算法
  def pre_order_non_recursive(self, T):
    """借助棧實現前驅遍歷
    """
    if T == None:
      return
    stack = []
    while T or len(stack) > 0:
      if T:
        stack.append(T)
        print(T.root, end=' ')
        T = T.lchild
      else:
        T = stack[-1]
        stack.pop()
        T = T.rchild

  # -----------中序遍歷 ------------
  # 遞歸算法
  def mid_order_recursive(self, T):
    if T == None:
      return
    self.mid_order_recursive(T.lchild)
    print(T.root, end=' ')
    self.mid_order_recursive(T.rchild)

  # 非遞歸算法
  def mid_order_non_recursive(self, T):
    """借助棧實現中序遍歷
    """
    if T == None:
      return
    stack = []
    while T or len(stack) > 0:
      if T:
        stack.append(T)
        T = T.lchild
      else:
        T = stack.pop()
        print(T.root, end=' ')
        T = T.rchild

  # -----------后序遍歷 ------------
  # 遞歸算法
  def post_order_recursive(self, T):
    if T == None:
      return
    self.post_order_recursive(T.lchild)
    self.post_order_recursive(T.rchild)
    print(T.root, end=' ')

  # 非遞歸算法
  def post_order_non_recursive(self, T):
    """借助兩個棧實現后序遍歷
    """
    if T == None:
      return
    stack1 = []
    stack2 = []
    stack1.append(T)
    while stack1:
      node = stack1.pop()
      if node.lchild:
        stack1.append(node.lchild)
      if node.rchild:
        stack1.append(node.rchild)
      stack2.append(node)
    while stack2:
      print(stack2.pop().root, end=' ')
    return

  # -----------層次遍歷 ------------
  def level_order(self, T):
    """借助隊列(其實還是一個棧)實現層次遍歷
    """
    if T == None:
      return
    stack = []
    stack.append(T)
    while stack:
      node = stack.pop(0) # 實現先進先出
      print(node.root, end=' ')
      if node.lchild:
        stack.append(node.lchild)
      if node.rchild:
        stack.append(node.rchild)

  # ----------- 前序遍歷序列、中序遍歷序列 ―> 重構二叉樹 ------------
  def tree_by_pre_mid(self, pre, mid):
    if len(pre) != len(mid) or len(pre) == 0 or len(mid) == 0:
      return
    T = NodeTree(pre[0])
    index = mid.index(pre[0])
    T.lchild = self.tree_by_pre_mid(pre[1:index + 1], mid[:index])
    T.rchild = self.tree_by_pre_mid(pre[index + 1:], mid[index + 1:])
    return T

  # ----------- 后序遍歷序列、中序遍歷序列 ―> 重構二叉樹 ------------
  def tree_by_post_mid(self, post, mid):
    if len(post) != len(mid) or len(post) == 0 or len(mid) == 0:
      return
    T = NodeTree(post[-1])
    index = mid.index(post[-1])
    T.lchild = self.tree_by_post_mid(post[:index], mid[:index])
    T.rchild = self.tree_by_post_mid(post[index:-1], mid[index + 1:])
    return T


if __name__ == '__main__':
  # ----------- 測試:前序、中序、后序、層次遍歷 -----------
  # 創建二叉樹
  nodeTree = NodeTree(1,
            lchild=NodeTree(2,
                    lchild=NodeTree(4,
                            rchild=NodeTree(7))),
            rchild=NodeTree(3,
                    lchild=NodeTree(5),
                    rchild=NodeTree(6)))
  T = BinTree()
  print('前序遍歷遞歸\t')
  T.pre_order_recursive(nodeTree) # 前序遍歷-遞歸
  print('\n')
  print('前序遍歷非遞歸\t')
  T.pre_order_non_recursive(nodeTree) # 前序遍歷-非遞歸
  print('\n')
  print('中序遍歷遞歸\t')
  T.mid_order_recursive(nodeTree) # 中序遍歷-遞歸
  print('\n')
  print('中序遍歷非遞歸\t')
  T.mid_order_non_recursive(nodeTree) # 中序遍歷-非遞歸
  print('\n')
  print('后序遍歷遞歸\t')
  T.post_order_recursive(nodeTree) # 后序遍歷-遞歸
  print('\n')
  print('后序遍歷非遞歸\t')
  T.post_order_non_recursive(nodeTree) # 后序遍歷-非遞歸
  print('\n')
  print('層次遍歷\t')
  T.level_order(nodeTree) # 層次遍歷
  print('\n')

  print('==========================================================================')

  # ----------- 測試:由遍歷序列構造二叉樹 -----------
  T = BinTree()
  pre = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']
  mid = ['B', 'C', 'A', 'E', 'D', 'G', 'H', 'F', 'I']
  post = ['C', 'B', 'E', 'H', 'G', 'I', 'F', 'D', 'A']

  newT_pre_mid = T.tree_by_pre_mid(pre, mid) # 由前序序列、中序序列構造二叉樹
  T.post_order_recursive(newT_pre_mid) # 獲取后序序列
  print('\n')

  newT_post_mid = T.tree_by_post_mid(post, mid) # 由后序序列、中序序列構造二叉樹
  T.pre_order_recursive(newT_post_mid) # 獲取前序序列

          

運行結果

前序遍歷遞歸?
1 2 4 7 3 5 6

前序遍歷非遞歸?
1 2 4 7 3 5 6

中序遍歷遞歸?
4 7 2 1 5 3 6

中序遍歷非遞歸?
4 7 2 1 5 3 6

后序遍歷遞歸?
7 4 2 5 6 3 1

后序遍歷非遞歸?
7 4 2 5 6 3 1

層次遍歷?
1 2 3 4 5 6 7

==========================================================================
C B E H G I F D A

A B C D E F G H I

以上就是本文的全部內容,希望對大家的學習有所幫助,也希望大家多多支持腳本之家。


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 97se在线观看| 色综合久久天天综合绕观看 | 91精品国产综合久久欧美 | 亚洲激情区 | 国产精品久久久久久久久久妇女 | 性大特级毛片视频 | 免费四虎永久在线精品 | 日本99视频| 在线视频久久 | 亚洲综合涩| 国产亚洲精品精品国产亚洲综合 | 欧美日本在线视频 | 999精品影视在线观看 | 在线看日本a毛片 | 全黄h全肉边做边吃奶在线观看 | 在线视频一二三区2021不卡 | 久久66热这里只会有精品 | 18p爽视频在线观看免费 | 伊人久久大杳蕉综合大象 | 日本在线视频毛片 | 香蕉国产一区二区 | 国产成+人+亚洲+欧美+日韩 | 国产一二三区精品 | 就操成人网| 亚洲精品亚洲人成毛片不卡 | 公主恋人在线观看 | 欧美日韩亚洲国产无线码 | 四虎一级片 | 无毒不卡在线观看 | 污夜影院 | 99爱色| 久久国产热 | 91精品国产乱码在线观看 | 丝袜亚洲精品中文字幕一区 | 日韩高清不卡在线 | 九九影院韩国理伦片 | 欧美日韩免费大片 | 国产精品久久久久久久久久妇女 | 97爱爱爱 | 热久久精品免费视频 | 99国产精品热久久久久久夜夜嗨 |