python - 使用中序和先序遍历输出二叉树

Question

class Node:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right
 
def inorderTraversal(root):
 
    if root is None:
        return
 
    inorderTraversal(root.left)
    print(root.data, end=' ')
    inorderTraversal(root.right)
 
def preorderTraversal(root):
 
    if root is None:
        return
 
    print(root.data, end=' ')
    preorderTraversal(root.left)
    preorderTraversal(root.right)
 
def construct(start, end, preorder, pIndex, dict):
 
    # base case
    if start > end:
        return None, pIndex
 
    root = Node(preorder[pIndex])
    pIndex = pIndex + 1
 
    index = dict[root.data]
 
    root.left, pIndex = construct(start, index - 1, preorder, pIndex, dict)
 
    root.right, pIndex = construct(index + 1, end, preorder, pIndex, dict)
 
    return root, pIndex     

def constructTree(inorder, preorder):
 
    dict = {}
    for i, e in enumerate(inorder):
        dict[e] = i
 
    pIndex = 0
 
    return construct(0, len(inorder) - 1, preorder, pIndex, dict)[0]
 
 
if __name__ == '__main__':
 
 
    inorder = [4, 2, 1, 7, 5, 8, 3, 6]
    preorder = [1, 2, 4, 3, 5, 7, 8, 6]
 
    root = constructTree(inorder, preorder)
 
    print("The inorder traversal is ", end='')
    inorderTraversal(root)
 
    preorderTraversal(root)

我有这段构建二叉树的代码，但它无法在终端中显示树。这很难做到!这里有没有人可以添加一个可以在终端中显示二叉树的方法？

对于上面的例子，它可能看起来像

Binary Tree

Answer 1

为解决您的任务而实现的算法。例如，在与您的图片相同的数据上测试输出，尝试更大数量的数字以查看更漂亮的图片。

在我的算法中，每个子树的宽度和高度以及边的长度都是自适应的。

懂俄语的可以看我的other post关于同一主题，控制台中的二叉树构造。另一篇文章用 C++ 实现了几种可视化算法。如果您至少不懂俄语，则可以从那里复制 C++ 代码。

Try it online!

class Node:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right
        
def print_tree(node):
    def inner(node):
        if node is None:
            return []
        sdat = str(node.data)
        l, r = inner(node.left), inner(node.right)
        cl, cr = len((l or ('',))[0]), len((r or ('',))[0])
        s = max(cl, cr)
        sll, slr = (s - cl + 1) // 2, (s - cl) // 2
        srl, srr = (s - cr) // 2, (s - cr + 1) // 2
        v = [' ' * s + sdat + ' ' * s]
        v.extend([' ' * (s - i - 1) + '/' + ' ' * i + ' ' * len(sdat) +
            ' ' * i + '\\' + ' ' * (s - i - 1) for i in range(s // 2)])
        v.extend([(' ' * sll + l[i] + ' ' * slr if i < len(l) else ' ' * s) +
            ' ' * len(sdat) + (' ' * srl + r[i] + ' ' * srr if i < len(r) else ' ' * s)
            for i in range(max(len(l), len(r)))])
        return v
    print('\n'.join(inner(node)))
        
if __name__ == '__main__':
    root = Node(1, Node(2, Node(4)), Node(3, Node(5, Node(7), Node(8)), Node(6)))
    print_tree(root)

输出:

       1
      / \
     /   \
    /     \
   2       3
  4       / \
         5   6
        7 8

---

上面的第一个算法是使用预序完成的。我正在使用 inorder 提供第二种算法。它有一个不同的更简单的输出:

Try it online!

class Node:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right
        
def print_tree(node):
    def inner(node, *, upref = '', cpref = '', dpref = ''):
        if node is None:
            return
        inner(node.right, upref = dpref + '  |',
            cpref = dpref + '  /', dpref = dpref + '   ')
        print(cpref + '--' + str(node.data))
        inner(node.left, upref = upref + '   ',
            cpref = upref + '  \\', dpref = upref + '  |')
    inner(node)
        
if __name__ == '__main__':
    root = Node(1, Node(2, Node(4)), Node(3, Node(5, Node(7), Node(8)), Node(6)))
    print_tree(root)

输出:

     /--6
  /--3
  |  |  /--8
  |  \--5
  |     \--7
--1
  \--2
     \--4

---

实现预排序的第三种算法，但它比第一种算法简单得多:

Try it online!

class Node:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right
        
def print_tree(node):
    def inner(node, *, last = True, pref = ''):
        if node is None:
            return
        print(pref + ('\\-' if last else '|-') + str(node.data))
        inner(node.right, last = False, pref = pref + ('  ' if last else '| '))
        inner(node.left, last = True, pref = pref + ('  ' if last else '| '))
    inner(node)
        
if __name__ == '__main__':
    root = Node(1, Node(2, Node(4)), Node(3, Node(5, Node(7), Node(8)), Node(6)))
    print_tree(root)

输出:

\-1
  |-3
  | |-6
  | \-5
  |   |-8
  |   \-7
  \-2
    \-4