A
_____/ \_____
/ \
B C
_/ \_ _/ \_
/ \ / \
D E F G
\
H
文本显示Python版本
class BinTreeHelper(object):
def __init__(self, root, data_key="data", lchild_key="lchild", rchild_key="rchild"):
self.root = root
self.data_key = data_key
self.lchild_key = lchild_key
self.rchild_key = rchild_key
@staticmethod
def print_not_enter(s):
print(s, end="")
def get_lchild(self, node):
return getattr(node, self.lchild_key)
def get_rchild(self, node):
return getattr(node, self.rchild_key)
def get_data(self, node):
return getattr(node, self.data_key)
def get_depth(self):
def _get_depth(node, depth):
lchild = self.get_lchild(node)
rchild = self.get_rchild(node)
left_depth = _get_depth(lchild, depth + 1) if lchild else depth
right_depth = _get_depth(rchild, depth + 1) if rchild else depth
return max((left_depth, right_depth))
return _get_depth(self.root, 1)
def display_in_text(self):
root = self.root
queue = list()
nhigth = self.get_depth()
END = "LEVEL_END"
queue.append(root)
queue.append(END)
d = nhigth
while d >= 1:
na = 1
for j in range(0, d - 1): # 计算2n-1
na *= 2
# 第一步：输出每层结点的数据域
while True:
p = queue.pop(0) # 从队头取出一个结点p
queue.append(p) # 结点放回到队尾，因此结点可重复提取
if p == END:
break
for j in range(0, 2 * na - 2): # 输出2n+1-2个空格
self.print_not_enter(" ")
self.print_not_enter(self.get_data(p) if p else " ") # 输出结点数据或空格
for j in range(0, 2 * na + 1): # 输出2n+1+1个空格
self.print_not_enter(" ")
print("") # 一层的结点数据输出结束，回车
if d == 1: # 如果是最后一层，不用输出下面的链接字符
break
# 第二步：输出每层结点与其子结点的第一行链接字符
while True: # 循环直至一层结束
p = queue.pop(0) # 从队头取出一个结点p
queue.append(p) # 结点放回到队尾，因此结点可重复提取
if p == END:
break
# 输出2n个空格或2n- 1（倒数第二层）个空格
for j in range(0, na if d != 2 else na - 1):
self.print_not_enter(" ")
p_and_left_exist = p and self.get_lchild(p)
p_and_right_exist = p and self.get_rchild(p)
# 为左子结点连接符输出’_’或空格
for j in range(0, na - 3):
self.print_not_enter("_" if p_and_left_exist else " ")
self.print_not_enter("/" if p_and_left_exist else " ") # 为左子结点连接符输出’/’或空格
self.print_not_enter(" ")
self.print_not_enter("\\" if p_and_right_exist else " ") # 为右子结点连接符输出’\’或空格
# 为右子结点连接符输出’_’或空格
for j in range(0, na - 3):
self.print_not_enter("_" if p_and_right_exist else " ")
# 输出2n+3个空格或2n+ 2（倒数第二层）个空格
for j in range(0, na + 3 if d != 2 else na + 2):
self.print_not_enter(" ")
print("") # 结点数据下面的连接符输出结束，回车
# 第三步：输出每层结点与其子结点的第二行链接字符
if d != 2:
while True:
p = queue.pop(0) # 从队头取出一个结点p
queue.append(p) # 结点放回到队尾，因此结点可重复提取
if p == END:
break
for j in range(0, na - 1):
self.print_not_enter(" ") # 输出2n-1个空格
p_and_left_exist = p and self.get_lchild(p)
p_and_right_exist = p and self.get_rchild(p)
self.print_not_enter("/" if p_and_left_exist else " ") # 为左子结点连接符输出’/’或空格
for j in range(0, 2 * na - 3):
self.print_not_enter(" ") # 输出2n+1-3个空格
self.print_not_enter("\\" if p_and_right_exist else " ")
for i in range(0, na + 2):
self.print_not_enter(" ") # 输出2n+2个空格
print("") # 结点数据下面的第二层连接符输出结束，回车
# 第四步：更新队列中的结点，即把队列中的结点换成下一层的结点
while True: # 更新队列的循环体
p = queue.pop(0)
if p == END:
break
queue.append(self.get_lchild(p) if p else None)
queue.append(self.get_rchild(p) if p else None)
queue.append(END)
d -= 1
class Node(object):
def __init__(self, data, left_node=None, rigth_node=None):
self.data = data
self.left_child = left_node
self.right_child = rigth_node
if __name__ == "__main__":
root = Node("A", Node("B", Node("D"), Node("E", None, Node("H"))), Node("C", Node("F"), Node("G")))
btH = BinTreeHelper(root, lchild_key="left_child", rchild_key="right_child")
t = btH.display_in_text()
参考文献：
[1] 江顺亮 任燕《电脑知识与技术：学术交流》二叉树结构的文本模式显示 2012