python使用递归的方式建立二叉树

 更新时间:2019年07月03日 14:53:25   作者:aguncn   我要评论

这篇文章主要介绍了python使用递归的方式建立二叉树,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧

树和图的数据结构,就很有意思啦。

# 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.pyanone<__main__.binarytree object at 0x00000000024139b0>b<__main__.binarytree object at 0x00000000024139e8>chello 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

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持脚本之家。

相关文章

  • python自动化测试工具splinter简介和使用实例

    python自动化测试工具splinter简介和使用实例

    这篇文章主要介绍了python自动化测试工具splinter简介和使用实例,splinter可以非常棒的模拟浏览器的行为,splinter提供了丰富的api,可以获取页面的信息判断当前的行为所产生的结果
    2014-05-05
  • python实现对比不同字体中的同一字符的显示效果

    python实现对比不同字体中的同一字符的显示效果

    这篇文章主要介绍了python实现对比不同字体中的同一字符的显示效果,也就是对比不同字体中某个字的显示效果,这在做设计时非常有用,需要的朋友可以参考下
    2015-04-04
  • 对于python的django框架使用的一些实用建议

    对于python的django框架使用的一些实用建议

    这篇文章主要介绍了对于python的django框架使用的一些实用建议,包括一些优秀模块的介绍,要的朋友可以参考下
    2015-04-04
  • python打包exe开机自动启动的实例(windows)

    python打包exe开机自动启动的实例(windows)

    今天小编就为大家分享一篇python打包exe开机自动启动的实例(windows),具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
    2019-06-06
  • python实现发送邮件功能代码

    python实现发送邮件功能代码

    这篇文章主要介绍了python实现发送邮件功能代码,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
    2017-12-12
  • python面向对象程序设计多继承和多态用法示例

    python面向对象程序设计多继承和多态用法示例

    这篇文章主要介绍了python面向对象程序设计多继承和多态用法,结合实例形式分析了python面向对象程序设计中多继承、多态的概念、原理、实现方法及相关操作注意事项,需要的朋友可以参考下
    2019-04-04
  • python利用百度ai实现文字识别功能

    python利用百度ai实现文字识别功能

    这篇文章主要为大家详细介绍了python利用百度ai实现文字识别,主要涉及通用文字识别、网络图片文字识别、身份证识别等文字识别功能具有一定的参考价值,感兴趣的小伙伴们可以参考一下
    2018-11-11
  • python实现诗歌游戏(类继承)

    python实现诗歌游戏(类继承)

    这篇文章主要为大家详细介绍了python实现诗歌游戏,根据上句猜下句、猜作者、猜朝代、猜诗名,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
    2019-02-02
  • python实现对象转换为xml的方法示例

    python实现对象转换为xml的方法示例

    这篇文章主要介绍了python实现对象转换为xml的方法,结合实例形式分析了python对象属性、节点的操作及与xml相互转换的相关实现技巧,需要的朋友可以参考下
    2017-06-06
  • python根据日期返回星期几的方法

    python根据日期返回星期几的方法

    这篇文章主要介绍了python根据日期返回星期几的方法,涉及python针对日期模块的相关使用技巧,需要的朋友可以参考下
    2015-07-07

最新评论