使用python打印一棵二叉树

# 构建二叉树
class Node:'节点类型'def __init__(self, item):self.item = itemself.left = Noneself.right = Noneclass Tree:'二叉树'def __init__(self):self.root = Nonedef add_node(self, root, value):'构建二叉搜索树，向当前二叉树添加节点,返回以root为根节点的二叉树'if root is None:node = Node(value)root = nodeif self.root is None:self.root = nodeelif value < root.item:root.left = self.add_node(root.left, value)elif value > root.item:root.right = self.add_node(root.right, value)return rootdef in_order(self, root):'中序遍历打印二叉树信息'if root is None:returnself.in_order(root.left)print(root.item)self.in_order(root.right)def depth(self, root):'求二叉树的深度'if root is None:return 0leftDepth = self.depth(root.left) + 1rightDepth = self.depth(root.right) + 1height = rightDepthif leftDepth > rightDepth:height = leftDepthreturn heightdef print_tree(self, root):'''打印一棵二叉树，二叉树节点值为0~9 10个整数或者26个大小写英文字母使用/\模拟左右分支,如下所示e                           /     \c       g/ \     / \b   d   f   h/a但是在打印满二叉树时，最多打印三层，对于深度为4的二叉树，存在节点冲突，无法打印'''if root is None:return# 基本思想：# 查询二叉树高度，预留足够的打印区域current = self.depth(root)# 计算深度为depth的满二叉树需要的打印区域：叶子节点需要的打印区域，恰好为奇数# 同一个节点左右孩子间隔 3 个空格# 相邻节点至少间隔一个空格，max_word = 3 * (2 ** (current - 1)) - 1node_space = int(max_word / 2)  # 每一个节点前面的空格数# queue1和queue2用来存放节点以及节点打印时的位置# queue1：当前层# queue2：下一层queue1 = [[self.root, node_space + 1]]queue2 = []while queue1:# 使用i_position列表记录左右斜杠的位置i_position = []# 确定左右斜杠的位置# "/"比当前节点的位置少1# "\"比当前节点的位置多1for i in range(len(queue1)):node = queue1[i][0]  # 节点打印位置i_space = queue1[i][1] - 1  # 左右斜线打印位置# 对于根节点，左右各空出两个空格if node.item == self.root.item:i_space -= 2# 存储左斜线和左孩子if node.left is not None:i_position.append([i_space, '/'])queue2.append([node.left, i_space - 1])i_space += 2if node.item == self.root.item:i_space += 4# 存储右斜线和右孩子if node.right is not None:i_position.append([i_space, '\\'])queue2.append([node.right, i_space + 1])# 打印节点和左右斜杠# 打印节点if len(queue1) > 0:# 找到打印位置最远的节点的位置last_node = queue1[len(queue1) - 1][1]# 当前打印节点的数目index = 0for i in range(last_node + 1):# 打印节点if index < len(queue1) and i == queue1[index][1]:print(queue1[index][0].item, end='')index += 1else:# 打印空格print(' ', end='')print()# 打印左右斜杠index = 0if len(i_position) > 0:for i in range(i_position[len(i_position) - 1][0] + 1):if i == i_position[index][0]:print(i_position[index][1], end='')index += 1else:print(' ', end='')print()# 更新queue1和queue2queue1 = []while queue2:queue1.append(queue2.pop(0))node_space -= 2tree = Tree()
tree.add_node(tree.root, 'e')
tree.add_node(tree.root, 'c')
tree.add_node(tree.root, 'g')
tree.add_node(tree.root, 'b')
tree.add_node(tree.root, 'h')
tree.add_node(tree.root, 'd')
tree.add_node(tree.root, 'f')
tree.print_tree(tree.root)