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

Python  /  管理员 发布于 7年前   190

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

# 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 = rchildclass 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 Tif __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

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