怎么在python中利用递归建立二叉树

这篇文章将为大家详细讲解有关怎么在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.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

关于怎么在python中利用递归建立二叉树就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到。