在Python中打印二进制树

Python 6月前 14

这篇文章将讨论二叉树以及我们如何使用它。我们还将看到我们如何用Python打印它。

我们将了解在处理二叉树时使用的术语。我们还将研究一个使用Python代码的二叉树的例子。

Python中的二叉树

Python的二叉树是目前最有效的数据结构之一，而且实现起来也比较简单。二叉树是一个树状的数据结构，有一个根节点和两个子节点，一个左节点和一个右节点。

每个节点可以有任意数量的子节点。本文将探讨如何在 Python 中创建和遍历二叉树。

让我们更好地了解与树相关的术语。

根：一棵树的最上面的节点，没有父节点。每棵树都有一个根。
边缘：边缘是一个父子链接。
叶子：一个没有子女的节点。树的最后一个节点。树有多个叶子节点。
子树：树使用一个节点作为它的根。
深度：深度是节点与根的距离。
高度：节点的高度是到子树最深节点的距离。
树的高度：树的高度是最高的节点，对应于根节点的高度相同。

树的遍历顺序

树的遍历是从根节点开始，访问左、右子节点。节点被访问的顺序被称为遍历顺序。

顺序内遍历树

有几种不同的方法来遍历二叉树。最常见的是内序遍历，它访问左、根和右子节点。

前序遍历树

另一种标准的遍历方式是预排序遍历，它首先访问根节点，然后是左子节点，最后是右子节点。

内序遍历是访问二叉树中所有节点的最有效方式，因为它只访问每个节点一次。前序遍历的效率要低一些，因为它要调用根节点两次。

然而，当我们想在遍历过程中修改树时，通常会使用前序遍历，因为先修改根节点，然后再修改左、右子节点是很容易的。

这里有一个Python中内序遍历的语法和简单实现。

def inorder(node):
  if node is not None:
    inorder(node.left)
    print(node.val)
    inorder(node.right)

所以，这就是我们想使用内序遍历方法时的代码。

而这里是前序遍历：

def preorder(node):
    if node is not None:
        print(node.val)
        preorder(node.left)
        preorder(node.right)

后序遍历

我们也可以用后序遍历树，即访问左边的子节点，右边的子节点，然后再访问根节点。然而，后序遍历不太常见，因为它的效率比其他两种遍历方式低。

还有其他的方法来遍历二叉树，比如说级序遍历，它逐级访问树上的节点。然而，我们不会在本文中介绍这种遍历方法。

现在我们已经看到了如何遍历二叉树，让我们看看如何用Python创建一棵二叉树并打印它。

在 Python 中实现二叉树

我们知道什么是二叉树以及与之相关的术语。我们将用Python实现二叉树，以更好地理解二叉树的工作原理。

我们需要二叉树的节点，这将是我们这里的类。因为我们将制作我们的数据类型，我们将把数据点与左右两边的地址放在一起。

而我们还没有这样的数据类型，所以我们将以我们需要的方式创建我们的数据类型。所以，首先，我们将创建一个类。
现在，我们将为这个类创建一个构造函数。并在类中传递构造函数，因为它是必要的。

我们还将给出参数数据，以便在其中存储树的数据。
我们将使用self 来获取数据到data 参数中。
因为没有数据，创建一个节点是不可能的。而如果我们没有数据，我们将如何处理这个节点？

而如果我们没有数据，我们就不会有左和右。从逻辑上讲，我们需要数据，这就是为什么我们在这里使用数据。

现在我们将需要一个节点。
1. 左结点
2. 右节点
我们将在下面的代码中实现它。
我们现在已经实现了二叉树（在下面的代码中）。我们已经创建了左节点和右节点，并将它们设置为等于None 。

因为当节点制作完成后，它们应该是类似于None 。由于树从根开始，所以没有左右的数据；我们将在以后添加数据。

现在我们将为树创建一些对象。为了创建binaryTreeNode ，我们必须创建一个变量并将其分配给binaryTreeNode() 。
我们已经为我们的class binaryTreeNode ，创建了三个对象，但是这些对象目前还没有与任何东西链接。因此，如果我们打印任何对象，看看它包含什么，我们将按照下面提到的代码。
现在我们将给出根的左边和右边的数据点，因为我们已经创建了三个对象，bnt1,bnt2 和bnt3 。我们认为bnt1 是根，bnt2 和bnt3 是bnt1 的左边和右边。
在这种情况下，我们的二进制树看起来就像下面这个。代码的输出将是这样的。
```
	   1
	  /
	/
  2       3
```
这里的根是1，左边的部分是2，右边的部分是3。现在我们将用Python打印它，看看它是如何工作的。
我们只想在得到根之后打印整个树。为此，我们将不得不定义一个方法。

我们所要做的就是把这段代码复制到这里，然后在里面写上新的代码。因为它是二叉树的一部分，我们必须用已经写好的代码来写新代码。

示例代码：

class binaryTreeNode():
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
    def printTree(root):
        print(root.data)
        print('L', root.left.data, end=": ")
        print('R', root.right.data, end=": ")
bnt1= binaryTreeNode(1)
bnt2= binaryTreeNode(2)
bnt3= binaryTreeNode(3)
bnt1.left = bnt2
bnt1.right = bnt3
bnt2.left = bnt1
bnt2.right = bnt3
bnt3.left = bnt1
bnt3.right = bnt2

方法defprintTree(root) 给了我们根。因为当我们拥有树的根时，我们可以通过节点访问整个树。

在声明该方法后，我们将检查一些条件。我们可以在上面的代码中看到这个方法def PrintTree(root) 。

让我们试着打印根1，bnt1 ，看看我们得到什么。

示例代码：

print(bnt1.printTree())

输出：

1
L 2: R 3: None

输出显示，树包含两个节点（左节点和右节点）。左边节点中的数据是2 ，右边节点中的数据是3 。

我们还可以打印bnt2 和bnt3 ，看看它们包含哪些数据点。

使用 Python 打印整个二叉树

这里是整个二叉树。我们可以运行它，并通过Python的random 库了解更多关于如何使用Python打印二叉树。

class BinaryTree:
    def __init__(self, key):
        self.key = key
        self.right = None
        self.left = None
    def insert(self, key):
        if self.key == key:
            return
        elif self.key < key:
            if self.right is None:
                self.right = BinaryTree(key)
            else:
                self.right.insert(key)
        else: # self.key > key
            if self.left is None:
                self.left = BinaryTree(key)
            else:
                self.left.insert(key)
    def display(self):
        lines, *_ = self._display_aux()
        for line in lines:
            print(line)
    def _display_aux(self):
        """Returns list of strings, width, height, and horizontal coordinate of the root."""
        # No child.
        if self.right is None and self.left is None:
            line = '%s' % self.key
            width = len(line)
            height = 1
            middle = width // 2
            return [line], width, height, middle
        # Only left child.
        if self.right is None:
            lines, n, p, x = self.left._display_aux()
            s = '%s' % self.key
            u = len(s)
            first_line = (x + 1) * ' ' + (n - x - 1) * '_' + s
            second_line = x * ' ' + '/' + (n - x - 1 + u) * ' '
            shifted_lines = [line + u * ' ' for line in lines]
            return [first_line, second_line] + shifted_lines, n + u, p + 2, n + u // 2
        # Only right child.
        if self.left is None:
            lines, n, p, x = self.right._display_aux()
            s = '%s' % self.key
            u = len(s)
            first_line = s + x * '_' + (n - x) * ' '
            second_line = (u + x) * ' ' + '\' + (n - x - 1) * ' '
            shifted_lines = [u * ' ' + line for line in lines]
            return [first_line, second_line] + shifted_lines, n + u, p + 2, u // 2
        # Two children.
        left, n, p, x = self.left._display_aux()
        right, m, q, y = self.right._display_aux()
        s = '%s' % self.key
        u = len(s)
        first_line = (x + 1) * ' ' + (n - x - 1) * '_' + s + y * '_' + (m - y) * ' '
        second_line = x * ' ' + '/' + (n - x - 1 + u + y) * ' ' + '\' + (m - y - 1) * ' '
        if p < q:
            left += [n * ' '] * (q - p)
        elif q < p:
            right += [m * ' '] * (p - q)
        zipped_lines = zip(left, right)
        lines = [first_line, second_line] + [a + u * ' ' + b for a, b in zipped_lines]
        return lines, n + m + u, max(p, q) + 2, n + u // 2
import random
b = BinaryTree(100)
for _ in range(100):
    b.insert(random.randint(50, 150))
b.display()