数据结构显示树的所有结点_您需要了解的有关树数据结构的所有信息

数据结构显示树的所有结点

When you first learn to code, it’s common to learn arrays as the “main data structure.”

第一次学习编码时，通常将数组学习为“主要数据结构”。

Eventually, you will learn about hash tables too. If you are pursuing a Computer Science degree, you have to take a class on data structure. You will also learn about linked lists, queues, and stacks. Those data structures are called “linear” data structures because they all have a logical start and a logical end.

最终，您还将了解hash tables 。 如果要攻读计算机科学学位，则必须参加有关数据结构的课程。 您还将了解linked lists ， queues和stacks 。 这些数据结构被称为“线性”数据结构，因为它们都具有逻辑起点和逻辑终点。

When we start learning about trees and graphs, it can get really confusing. We don’t store data in a linear way. Both data structures store data in a specific way.

当我们开始学习trees和graphs ，它会变得非常混乱。 我们不会以线性方式存储数据。 两种数据结构均以特定方式存储数据。

This post is to help you better understand the Tree Data Structure and to clarify any confusion you may have about it.

这篇文章是为了帮助您更好地理解“树数据结构”，并澄清您可能对此感到的困惑。

In this article, we will learn:

在本文中，我们将学习：

• What is a tree
  什么是树
• Examples of trees
  树木的例子
• Its terminology and how it works
  它的术语及其工作方式
• How to implement tree structures in code.
  如何在代码中实现树结构。

Let’s start this learning journey. :)

让我们开始学习之旅。 :)

定义 (Definition)

When starting out programming, it is common to understand better the linear data structures than data structures like trees and graphs.

开始编程时，通常比树和图之类的数据结构更好地理解线性数据结构。

Trees are well-known as a non-linear data structure. They don’t store data in a linear way. They organize data hierarchically.

树是众所周知的非线性数据结构。 它们不会以线性方式存储数据。 他们分层组织数据。

让我们深入研究现实生活中的例子！ (Let’s dive into real life examples!)

What do I mean when I say in a hierarchical way?

当我以分层方式说话时，我是什么意思？

Imagine a family tree with relationships from all generation: grandparents, parents, children, siblings, etc. We commonly organize family trees hierarchically.

想象一下一棵与各代人有亲戚关系的家谱：祖父母，父母，孩子，兄弟姐妹等。我​​们通常按层次组织家谱。

The above drawing is is my family tree. Tossico, Akikazu, Hitomi, and Takemi are my grandparents.

上图是我的家谱。 Tossico, Akikazu, Hitomi,和Takemi是我的祖父母。

Toshiaki and Juliana are my parents.

Toshiaki和Juliana是我的父母。

TK, Yuji, Bruno, and Kaio are the children of my parents (me and my brothers).

TK, Yuji, Bruno和Kaio是我父母(我和我的兄弟)的孩子。

An organization’s structure is another example of a hierarchy.

组织的结构是层次结构的另一个示例。

In HTML, the Document Object Model (DOM) works as a tree.

在HTML中，文档对象模型(DOM)就像一棵树。

The HTML tag contains other tags. We have a head tag and a body tag. Those tags contains specific elements. The head tag has meta and title tags. The body tag has elements that show in the user interface, for example, h1, a, li, etc.

HTML标签包含其他标签。 我们有一个head标签和一个body标签。 这些标签包含特定元素。 head标签具有meta和title标签。 body标签具有在用户界面中显示的元素，例如h1 ， a ， li等。

技术定义 (A technical definition)

A tree is a collection of entities called nodes. Nodes are connected by edges. Each node contains a value or data, and it may or may not have a child node .

tree是称为nodes的实体的nodes 。 节点通过edges连接。 每个node包含一个value或data ，并且它可能有也可能没有child node 。

The first node of the tree is called the root. If this root node is connected by another node, the root is then a parent node and the connected node is a child.

tree的first node称为root 。 如果此root node由另一个node连接，则该root是parent node ，而连接的node是child node 。

All Tree nodes are connected by links called edges. It’s an important part of trees, because it’s manages the relationship between nodes.

所有Tree nodes通过称为edges的链接连接。 它是trees的重要组成部分，因为它管理nodes之间的关系。

Leaves are the last nodes on a tree. They are nodes without children. Like real trees, we have the root, branches, and finally the leaves.

Leaves是tree.的最后一个nodes tree. 它们是没有孩子的节点。 像真正的树木一样，我们有root ， branches ，最后还有leaves 。

Other important concepts to understand are height and depth.

其他要理解的重要概念是height和depth 。

The height of a tree is the length of the longest path to a leaf.

tree的height是通往leaf的最长路径的长度。

The depth of a node is the length of the path to its root.

node的depth是到其root的路径的长度。

术语摘要 (Terminology summary)

• Root is the topmost node of the tree

  根是tree的最高node

• Edge is the link between two nodes

  边缘是两个nodes之间的链接

• Child is a node that has a parent node

  子 node是具有parent node

• Parent is a node that has an edge to a child node

  父 node是具有child node edge的child node

• Leaf is a node that does not have a child node in the tree

  叶子是一个node ，它没有一个child node的tree

• Height is the length of the longest path to a leaf

  高度是到leaf的最长路径的长度

• Depth is the length of the path to its root

  深度是到其root的路径的长度

二叉树 (Binary trees)

Now we will discuss a specific type of tree. We call it thebinary tree.

现在我们将讨论一种特定类型的tree 。 我们称其为binary tree 。

“In computer science, a binary tree is a tree data structure in which each node has at the most two children, which are referred to as the left child and the right child.” — Wikipedia

“在计算机科学中，二叉树是一种树数据结构，其中每个节点最多具有两个子节点，分别称为左子节点和右子节点。” — 维基百科

So let’s look at an example of a binary tree.

因此，让我们看一个binary tree的例子。

让我们编写一个二叉树 (Let’s code a binary tree)

The first thing we need to keep in mind when we implement a binary tree is that it is a collection of nodes. Each node has three attributes: value, left_child, and right_child.

实现binary tree时，我们要记住的第一件事是它是nodes的集合。 每个node具有三个属性： value ， left_child和right_child 。

How do we implement a simple binary tree that initializes with these three properties?

我们如何实现一个简单的用这三个属性初始化的binary tree ？

Let’s take a look.

让我们来看看。

class BinaryTree:def __init__(self, value):self.value = valueself.left_child = Noneself.right_child = None

Here it is. Our binary tree class.

这里是。 我们的binary tree类。

When we instantiate an object, we pass the value (the data of the node) as a parameter. Look at the left_child and the right_child. Both are set to None.

实例化对象时，我们将value (节点的数据)作为参数传递。 看一下left_child和right_child 。 两者都设置为None 。

Why?

为什么？

Because when we create our node, it doesn’t have any children. We just have the node data.

因为当我们创建node ，它没有任何子代。 我们只有node data 。

Let’s test it:

让我们测试一下：

tree = BinaryTree('a')
print(tree.value) # a
print(tree.left_child) # None
print(tree.right_child) # None

That’s it.

而已。

We can pass the string ‘a’ as the value to our Binary Tree node. If we print the value, left_child, and right_child, we can see the values.

我们可以将string “ a ”作为value传递给我们的Binary Tree node 。 如果我们打印value ， left_child和right_child ，我们可以看到这些值。

Let’s go to the insertion part. What do we need to do here?

让我们转到插入部分。 我们在这里需要做什么？

We will implement a method to insert a new node to the right and to the left.

我们将实现一种在right和left插入新node的方法。

Here are the rules:

规则如下：

• If the current node doesn’t have a left child, we just create a new nodeand set it to the current node’s left_child.

  如果当前node没有left child node ，我们只需创建一个新node并将其设置为当前节点的left_child 。

• If it does have the left child, we create a new node and put it in the current left child’s place. Allocate this left child node to the new node’s left child.

  如果确实有left child节点，我们将创建一个新节点，并将其放在当前left child节点的位置。 将此left child node分配给新节点的left child节点。

Let’s draw it out. :)

让我们画出来。 :)

Here’s the code:

这是代码：

def insert_left(self, value):if self.left_child == None:self.left_child = BinaryTree(value)else:new_node = BinaryTree(value)new_node.left_child = self.left_childself.left_child = new_node

Again, if the current node doesn’t have a left child, we just create a new node and set it to the current node’s left_child. Or else we create a new node and put it in the current left child’s place. Allocate this left child node to the new node’s left child.

同样，如果当前节点没有left child节点，则只需创建一个新节点并将其设置为当前节点的left_child 。 否则，我们将创建一个新节点，并将其放置在当前left child节点的位置。 将此left child node分配给新节点的left child节点。

And we do the same thing to insert a right child node.

并且我们做同样的事情来插入一个right child node 。

def insert_right(self, value):if self.right_child == None:self.right_child = BinaryTree(value)else:new_node = BinaryTree(value)new_node.right_child = self.right_childself.right_child = new_node

Done. :)

做完了 :)

But not entirely. We still need to test it.

但并非完全如此。 我们仍然需要测试。

Let’s build the followingtree:

让我们构建以下tree ：

To summarize the illustration of this tree:

总结一下这棵树的图示：

• a node will be the root of our binary Tree

  a node将成为我们binary Tree的root

• a left child is b node

  a left child是b node

• a right child is c node

  a right child是c node

• b right child is d node (b node doesn’t have a left child)

  b right child node是d node ( b node没有left child node )

• c left child is e node

  c left child node是e node

• c right child is f node

  c right child是f node

• both e and f nodes do not have children

  e和f nodes都没有子nodes

So here is the code for the tree:

所以这是tree的代码：

a_node = BinaryTree('a')
a_node.insert_left('b')
a_node.insert_right('c')b_node = a_node.left_child
b_node.insert_right('d')c_node = a_node.right_child
c_node.insert_left('e')
c_node.insert_right('f')d_node = b_node.right_child
e_node = c_node.left_child
f_node = c_node.right_childprint(a_node.value) # a
print(b_node.value) # b
print(c_node.value) # c
print(d_node.value) # d
print(e_node.value) # e
print(f_node.value) # f

Insertion is done.

插入完成。

Now we have to think about tree traversal.

现在我们必须考虑遍历tree 。

We have two options here: Depth-First Search (DFS) and Breadth-First Search (BFS).

这里有两个选项 ： 深度优先搜索(DFS)和宽度优先搜索(BFS) 。

• DFS “is an algorithm for traversing or searching tree data structure. One starts at the root and explores as far as possible along each branch before backtracking.” — Wikipedia

  “ DFS ”是用于遍历或搜索树数据结构的算法。 一个从根开始，并在回溯之前在每个分支上进行尽可能的探索。” — 维基百科

• BFS “is an algorithm for traversing or searching tree data structure. It starts at the tree root and explores the neighbor nodes first, before moving to the next level neighbors.” — Wikipedia

  BFS是一种用于遍历或搜索树数据结构的算法。 它从树的根部开始，先探索邻居节点，然后再转移到下一级邻居。” — 维基百科

So let’s dive into each tree traversal type.

因此，让我们深入研究每种树遍历类型。

深度优先搜索(DFS) (Depth-First Search (DFS))

DFS explores a path all the way to a leaf before backtracking and exploring another path. Let’s take a look at an example with this type of traversal.

在回溯并探索另一条路径之前， DFS会一直探索到一片叶子的路径。 让我们看一下这种遍历的示例。

The result for this algorithm will be 1–2–3–4–5–6–7.

该算法的结果将是1–2–3–3–4–5–6–7。

Why?

为什么？

Let’s break it down.

让我们分解一下。

1. Start at the root (1). Print it.

   从root (1)开始。 打印它。

2. Go to the left child (2). Print it.

2.转到left child (2)。 打印它。

3. Then go to the left child (3). Print it. (This node doesn’t have any children)

3.然后转到left child (3)。 打印它。 (此node没有任何子node )

4. Backtrack and go the right child (4). Print it. (This node doesn’t have any children)

4.回溯并找到right child (4)。 打印它。 (此node没有任何子node )

5. Backtrack to the root node and go to the right child (5). Print it.

5.回溯到root node ，然后转到right child (5)。 打印它。

6. Go to the left child (6). Print it. (This node doesn’t have any children)

6.转到left child (6)。 打印它。 (此node没有任何子node )

7. Backtrack and go to the right child (7). Print it. (This node doesn’t have any children)

7.回溯并找到right child (7)。 打印它。 (此node没有任何子node )

8. Done.

8.完成。

When we go deep to the leaf and backtrack, this is called DFS algorithm.

当我们深入到叶子并回溯时，这称为DFS算法。

Now that we are familiar with this traversal algorithm, we will discuss types of DFS: pre-order, in-order, and post-order.

现在我们已经熟悉了这种遍历算法，我们将讨论DFS的类型： pre-order ， in-order和post-order 。

预购 (Pre-order)

This is exactly what we did in the above example.

这正是我们在上面的示例中所做的。

1. Print the value of the node.

   打印node的值。

2. Go to the left child and print it. This is if, and only if, it has a left child.

   转到left child并打印它。 这是并且仅当它有一个left child 。

3. Go to the right child and print it. This is if, and only if, it has a right child.

   转到right child并打印它。 这是并且仅当它有一个right child 。

def pre_order(self):print(self.value)if self.left_child:self.left_child.pre_order()if self.right_child:self.right_child.pre_order()

为了 (In-order)

The result of the in-order algorithm for this tree example is 3–2–4–1–6–5–7.

此tree示例的有序算法的结果是3–2–4–1–1–6–5–7。

The left first, the middle second, and the right last.

左第一，中第二，右最后。

Now let’s code it.

现在让我们编写代码。

def in_order(self):if self.left_child:self.left_child.in_order()print(self.value)if self.right_child:self.right_child.in_order()

1. Go to the left child and print it. This is if, and only if, it has a left child.

   转到left child并打印它。 这是并且仅当它有一个left child 。

2. Print the node’s value

   打印node的值

3. Go to the right child and print it. This is if, and only if, it has a right child.

   转到right child并打印它。 这是并且仅当它有一个right child 。

后订单 (Post-order)

The result of the post order algorithm for this tree example is 3–4–2–6–7–5–1.

该tree示例的post order算法的结果是3–4–2–2–6–7–5–1。

The left first, the right second, and the middle last.

左第一，右第二，居中。

Let’s code this.

让我们对此进行编码。

def post_order(self):if self.left_child:self.left_child.post_order()if self.right_child:self.right_child.post_order()print(self.value)

1. Go to the left child and print it. This is if, and only if, it has a left child.

   转到left child并打印它。 这是并且仅当它有一个left child 。

2. Go to the right child and print it. This is if, and only if, it has a right child.

   转到right child并打印它。 这是并且仅当它有一个right child 。

3. Print the node’s value

   打印node的值

广度优先搜索(BFS) (Breadth-First Search (BFS))

BFS algorithm traverses the tree level by level and depth by depth.

BFS算法按级别遍历tree ，按深度遍​​历tree 。

Here is an example that helps to better explain this algorithm:

这是有助于更好地解释此算法的示例：

So we traverse level by level. In this example, the result is 1–2–5–3–4–6–7.

因此，我们逐级遍历。 在此示例中，结果为1–2–5–3–4–6–7。

• Level/Depth 0: only node with value 1

  级别/深度0：仅值为1的node

• Level/Depth 1: nodes with values 2 and 5

  级别/深度1：值为2和5的nodes

• Level/Depth 2: nodes with values 3, 4, 6, and 7

  级别/深度2：值为3、4、6和7的nodes

Now let’s code it.

现在让我们编写代码。

def bfs(self):queue = Queue()queue.put(self)while not queue.empty():current_node = queue.get()print(current_node.value)if current_node.left_child:queue.put(current_node.left_child)if current_node.right_child:queue.put(current_node.right_child)

To implement a BFS algorithm, we use the queue data structure to help.

为了实现BFS算法，我们使用queue数据结构来提供帮助。

How does it work?

它是如何工作的？

Here’s the explanation.

这是解释。

1. First add the root node into the queue with the put method.

   首先添加root node到queue与put方法。

2. Iterate while the queue is not empty.

   在queue不为空时进行迭代。

3. Get the first node in the queue, and then print its value.

   获取queue的第一个node ，然后打印其值。

4. Add both left and right children into the queue (if the current nodehas children).

   既能补充left和right children入queue (如果当前node有children )。

5. Done. We will print the value of each node, level by level, with our queuehelper.

   做完了 我们将使用queue帮助器逐级打印每个node,的值。

二进制搜索树 (Binary Search tree)

“A Binary Search Tree is sometimes called ordered or sorted binary trees, and it keeps its values in sorted order, so that lookup and other operations can use the principle of binary search” — Wikipedia

“二叉搜索树有时被称为有序或排序的二叉树，它按排序顺序保留其值，以便查找和其他操作可以使用二叉搜索的原理” — Wikipedia

An important property of a Binary Search Tree is that the value of a Binary Search Tree nodeis larger than the value of the offspring of its left child, but smaller than the value of the offspring of its right child.”

Binary Search Tree一个重要属性是Binary Search Tree node的值大于其left child子代的后代的值，但小于其right child.子代的后代的值right child. ”

Here is a breakdown of the above illustration:

这是上面插图的分解：

• A is inverted. The subtree 7–5–8–6 needs to be on the right side, and the subtree 2–1–3 needs to be on the left.

  A是倒置的。 subtree 7–5–8–6需要在右侧， subtree 2–1–3需要在左侧。

• B is the only correct option. It satisfies the Binary Search Tree property.

  B是唯一正确的选项。 它满足Binary Search Tree属性。

• C has one problem: the node with the value 4. It needs to be on the left side of the root because it is smaller than 5.

  C有一个问题：值为4的node 。它必须在root的左侧，因为它小于5。

让我们编写一个二进制搜索树！ (Let’s code a Binary Search Tree!)

Now it’s time to code!

现在是时候编写代码了！

What will we see here? We will insert new nodes, search for a value, delete nodes, and the balance of the tree.

我们在这里看到什么？ 我们将插入新节点，搜索值，删除节点以及tree的其余部分。

Let’s start.

开始吧。

插入：将新节点添加到我们的树中 (Insertion: adding new nodes to our tree)

Imagine that we have an empty tree and we want to add new nodes with the following values in this order: 50, 76, 21, 4, 32, 100, 64, 52.

想象一下，我们有tree空tree并希望以此顺序添加具有以下值的新nodes ：50、76、21、4、32、100、64、52。

The first thing we need to know is if 50 is the root of our tree.

我们需要知道的第一件事是50是否是树的root 。

We can now start inserting node by node.

我们现在可以开始插入node的node 。

• 76 is greater than 50, so insert 76 on the right side.
  76大于50，因此在右侧插入76。
• 21 is smaller than 50, so insert 21 on the left side.
  21小于50，因此在左侧插入21。

• 4 is smaller than 50. Node with value 50 has a left child 21. Since 4 is smaller than 21, insert it on the left side of this node.

  4小于50。值为50的Node具有left child Node 21。由于4小于21，因此将其插入此node的左侧。

• 32 is smaller than 50. Node with value 50 has a left child 21. Since 32 is greater than 21, insert 32 on the right side of this node.

  32小于50。值为50的Node具有left child Node 21。由于32大于21，因此在此node的右侧插入32。

• 100 is greater than 50. Node with value 50 has a right child 76. Since 100 is greater than 76, insert 100 on the right side of this node.

  100大于50。值为50的Node具有right child Node 76。由于100大于76，因此在此node的右侧插入100。

• 64 is greater than 50. Node with value 50 has a right child 76. Since 64 is smaller than 76, insert 64 on the left side of this node.

  64大于50。值为50的Node有一个right child Node 76。由于64小于76，因此在此node的左侧插入64。

• 52 is greater than 50. Node with value 50 has a right child 76. Since 52 is smaller than 76, node with value 76 has a left child 64. 52 is smaller than 64, so insert 54 on the left side of this node.

  52大于50。值为50的Node具有right child Node 76。由于52小于76，因此值为76的node具有left child node 64。52小于64，因此在该node的左侧插入54。

Do you notice a pattern here?

您在这里注意到一种模式吗？

Let’s break it down.

让我们分解一下。

1. Is the new node value greater or smaller than the current node?

   新node值是否大于或小于当前node ？

2. If the value of the new node is greater than the current node, go to the right subtree. If the current node doesn’t have a right child, insert it there, or else backtrack to step #1.

   如果新node值大于当前node,请转到右侧的subtree 。 如果当前node没有right child ，则将其插入那里，否则返回到步骤1。

3. If the value of the new node is smaller than the current node, go to the left subtree. If the current node doesn’t have a left child, insert it there, or else backtrack to step #1.

   如果新node值小于当前node ，请转到左侧的subtree 。 如果当前node没有left child node ，则将其插入其中，否则返回到步骤1。

4. We did not handle special cases here. When the value of a new node is equal to the current value of the node, use rule number 3. Consider inserting equal values to the left side of the subtree.

   我们在这里没有处理特殊情况。 当新node值等于该node,的当前值时node,使用规则编号3。请考虑在subtree的左侧插入相等的值。

Now let’s code it.

现在让我们编写代码。

class BinarySearchTree:def __init__(self, value):self.value = valueself.left_child = Noneself.right_child = Nonedef insert_node(self, value):if value <= self.value and self.left_child:self.left_child.insert_node(value)elif value <= self.value:self.left_child = BinarySearchTree(value)elif value > self.value and self.right_child:self.right_child.insert_node(value)else:self.right_child = BinarySearchTree(value)

It seems very simple.

看起来很简单。

The powerful part of this algorithm is the recursion part, which is on line 9 and line 13. Both lines of code call the insert_node method, and use it for its left and right children, respectively. Lines 11 and 15 are the ones that do the insertion for each child.

该算法的强大部分是递归部分，它位于第9行和第13行。这两行代码都调用insert_node方法，并将其分别用于其left和right children 。 第11和15是为每个child插入的行。

让我们搜索节点值...还是不... (Let’s search for the node value… Or not…)

The algorithm that we will build now is about doing searches. For a given value (integer number), we will say if our Binary Search Tree does or does not have that value.

我们现在将构建的算法是关于搜索。 对于给定的值(整数)，我们将说明Binary Search Tree是否具有该值。

An important item to note is how we defined the tree insertion algorithm. First we have our root node. All the left subtree nodes will have smaller values than the root node. And all the right subtree nodes will have values greater than the root node.

要注意的重要事项是我们如何定义树插入算法 。 首先，我们有我们的root node 。 所有的左subtree nodes将具有比更小的值root node 。 所有的右subtree nodes将有值比更大的root node 。

Let’s take a look at an example.

让我们看一个例子。

Imagine that we have this tree.

想象我们有一tree 。

Now we want to know if we have a node based on value 52.

现在我们想知道是否有一个基于值52的节点。

Let’s break it down.

让我们分解一下。

1. We start with the root node as our current node. Is the given value smaller than the current node value? If yes, then we will search for it on the left subtree.

   我们先从root node作为我们当前的node 。 给定值是否小于当前node值？ 如果是，那么我们将在左侧的subtree搜索它。

2. Is the given value greater than the current node value? If yes, then we will search for it on the right subtree.

   给定值是否大于当前node值？ 如果是，那么我们将在右侧的subtree搜索它。

3. If rules #1 and #2 are both false, we can compare the current node value and the given value if they are equal. If the comparison returns true, then we can say, “Yeah! Our tree has the given value,” otherwise, we say, “Nooo, it hasn’t.”

   如果规则＃1和＃2都为假，则如果它们相等，则可以比较当前node值和给定值。 如果比较结果为true ，那么我们可以说：“是的！ 我们的tree具有给定的值，”否则，我们说“不，它没有。”

Now let’s code it.

现在让我们编写代码。

class BinarySearchTree:def __init__(self, value):self.value = valueself.left_child = Noneself.right_child = Nonedef find_node(self, value):if value < self.value and self.left_child:return self.left_child.find_node(value)if value > self.value and self.right_child:return self.right_child.find_node(value)return value == self.value

Let’s beak down the code:

让我们简化一下代码：

• Lines 8 and 9 fall under rule #1.
  第8和9行属于规则1。
• Lines 10 and 11 fall under rule #2.
  第10和11行属于规则2。
• Line 13 falls under rule #3.
  第13行属于规则3。

How do we test it?

我们如何测试呢？

Let’s create our Binary Search Tree by initializing the root node with the value 15.

让我们来创建我们的Binary Search Tree通过初始化root node ，其值为15。

bst = BinarySearchTree(15)

And now we will insert many new nodes.

现在我们将插入许多新nodes 。

bst.insert_node(10)
bst.insert_node(8)
bst.insert_node(12)
bst.insert_node(20)
bst.insert_node(17)
bst.insert_node(25)
bst.insert_node(19)

For each inserted node , we will test if our find_node method really works.

对于每个插入的node ，我们将测试find_node方法是否真的有效。

print(bst.find_node(15)) # True
print(bst.find_node(10)) # True
print(bst.find_node(8)) # True
print(bst.find_node(12)) # True
print(bst.find_node(20)) # True
print(bst.find_node(17)) # True
print(bst.find_node(25)) # True
print(bst.find_node(19)) # True

Yeah, it works for these given values! Let’s test for a value that doesn’t exist in our Binary Search Tree.

是的，它适用于这些给定的值！ 让我们测试一下Binary Search Tree中不存在的Binary Search Tree 。

print(bst.find_node(0)) # False

Oh yeah.

哦耶。

Our search is done.

我们的搜索完成。

删除：删除并整理 (Deletion: removing and organizing)

Deletion is a more complex algorithm because we need to handle different cases. For a given value, we need to remove the node with this value. Imagine the following scenarios for this node : it has no children, has a single child, or has two children.

删除是一种更复杂的算法，因为我们需要处理不同的情况。 对于给定的值，我们需要删除具有该值的node 。 想象一下该node的以下情形：它没有children node ，有一个child node或有两个children node 。

• Scenario #1: A node with no children (leaf node).

  方案1：一个node无children ( leaf node )。

#        |50|                              |50|
#      /      \                           /    \
#    |30|     |70|   (DELETE 20) --->   |30|   |70|
#   /    \                                \
# |20|   |40|                             |40|

If the node we want to delete has no children, we simply delete it. The algorithm doesn’t need to reorganize the tree.

如果要删除的node没有子node ，则只需删除它。 该算法不需要重组tree 。

• Scenario #2: A node with just one child (left or right child).

  场景2 ：只有一个孩子( left或right孩子)的node 。

#        |50|                              |50|
#      /      \                           /    \
#    |30|     |70|   (DELETE 30) --->   |20|   |70|
#   /            
# |20|

In this case, our algorithm needs to make the parent of the node point to the child node. If the node is the left child, we make the parent of the left child point to the child. If the node is the right child of its parent, we make the parent of the right child point to the child.

在这种情况下，我们的算法需要使node的父node指向child节点。 如果该node是left child ，我们做的父left child点的child 。 如果该node是right child其父的，我们做的父right child点的child 。

• Scenario #3: A node with two children.

  场景3 ：一个有两个孩子的node 。

#        |50|                              |50|
#      /      \                           /    \
#    |30|     |70|   (DELETE 30) --->   |40|   |70|
#   /    \                             /
# |20|   |40|                        |20|

When the node has 2 children, we need to find the node with the minimum value, starting from the node’sright child. We will put this node with minimum value in the place of the node we want to remove.

当node有2个孩子，我们需要找到node与最小值，从起始node的right child 。 我们将使用最小值将该node放置在要删除的node的位置。

It’s time to code.

是时候编写代码了。

def remove_node(self, value, parent):if value < self.value and self.left_child:return self.left_child.remove_node(value, self)elif value < self.value:return Falseelif value > self.value and self.right_child:return self.right_child.remove_node(value, self)elif value > self.value:return Falseelse:if self.left_child is None and self.right_child is None and self == parent.left_child:parent.left_child = Noneself.clear_node()elif self.left_child is None and self.right_child is None and self == parent.right_child:parent.right_child = Noneself.clear_node()elif self.left_child and self.right_child is None and self == parent.left_child:parent.left_child = self.left_childself.clear_node()elif self.left_child and self.right_child is None and self == parent.right_child:parent.right_child = self.left_childself.clear_node()elif self.right_child and self.left_child is None and self == parent.left_child:parent.left_child = self.right_childself.clear_node()elif self.right_child and self.left_child is None and self == parent.right_child:parent.right_child = self.right_childself.clear_node()else:self.value = self.right_child.find_minimum_value()self.right_child.remove_node(self.value, self)return True

1. First: Note the parameters value and parent. We want to find the nodethat has this value , and the node’s parent is important to the removal of the node.

   首先 ：注意参数value和parent 。 我们要查找的node具有此value ，和node的家长要去除的重要node 。

2. Second: Note the returning value. Our algorithm will return a boolean value. It returns True if it finds the node and removes it. Otherwise it will return False.

   第二 ：记下返回值。 我们的算法将返回布尔值。 如果找到并删除该node ，则返回True 。 否则它将返回False 。

3. From line 2 to line 9: We start searching for the node that has the valuethat we are looking for. If the value is smaller than the current nodevalue , we go to the left subtree, recursively (if, and only if, the current node has a left child). If the value is greater, go to the right subtree, recursively.

   从第2行到第9行 ：我们开始搜索具有我们要查找的value的node 。 如果该value小于current nodevalue ，则递归地转到left subtree (当且仅当current node具有left child )。 如果该value更大，则递归转到right subtree 。

4. Line 10: We start to think about the remove algorithm.

   第10行 ：我们开始考虑remove算法。

5. From line 11 to line 13: We cover the node with no children , and it is the left child from its parent. We remove the node by setting the parent’s left child to None.

   从第11行到第13行 ：我们覆盖了没有children node ，它是parent node的left child parent 。 我们通过将parent node的left child node设置为None来删除该node 。

6. Lines 14 and 15: We cover the node with no children , and it is the right child from it’s parent. We remove the node by setting the parent’s right child to None.

   第14和15行 ：我们覆盖了没有children node ，它是来自parent node的right child parent 。 我们通过将parent的right child为None来删除该node 。

7. Clear node method: I will show the clear_node code below. It sets the nodes left child , right child, and its value to None.

   清除节点方法 ：我将在下面显示clear_node代码。 它将节点设置为left child , right child ，并将其value为None 。

8. From line 16 to line 18: We cover the node with just one child (left child), and it is the left child from it’s parent. We set the parent's left child to the node’s left child (the only child it has).

   从第16行到第18行 ：我们仅用一个child node ( left child node覆盖该node ，它是parent的left child parent 。 我们将parent node的left child设置为node的left child (其唯一的孩子)。

9. From line 19 to line 21: We cover the node with just one child (left child), and it is the right child from its parent. We set the parent's right child to the node’s left child (the only child it has).

   从第19行到第21行 ：我们仅用一个child node ( left child node覆盖该node ，它是parent的right child parent 。 我们将parent node的right child node设置为node的left child node (它唯一的子node )。

10. From line 22 to line 24: We cover the node with just one child (right child), and it is the left child from its parent. We set the parent's left child to the node’s right child (the only child it has).

    从第22行到第24行 ：我们仅用一个child node ( right child node覆盖该node ，它是parent的left child parent 。 我们将parent的left child设置为node的right child (它唯一的子级)。

11. From line 25 to line 27: We cover the node with just one child (right child) , and it is the right child from its parent. We set the parent's right child to the node’s right child (the only child it has).

    从第25行到第27行 ：我们仅用一个child node ( right child node覆盖该node ，它是parent的right child parent 。 我们将parent的right child设置为node的right child (它唯一的子级)。

12. From line 28 to line 30: We cover the node with both left and rightchildren. We get the node with the smallest value (the code is shown below) and set it to the value of the current node . Finish it by removing the smallest node.

    从第28行至30行 ：我们覆盖的node与两个left和right的孩子。 我们拿到的node具有最小value (代码如下所示)，将其设置为value的的current node 。 通过删除最小的node完成它。

13. Line 32: If we find the node we are looking for, it needs to return True. From line 11 to line 31, we handle this case. So just return True and that’s it.

    第32行 ：如果找到要查找的node ，则需要返回True 。 从第11行到第31行，我们处理这种情况。 因此，只需返回True 。

• To use the clear_node method: set the None value to all three attributes — (value, left_child, and right_child)

  要使用clear_node方法：将None值设置为所有三个属性-( value ， left_child和right_child )

def clear_node(self):self.value = Noneself.left_child = Noneself.right_child = None

• To use the find_minimum_value method: go way down to the left. If we can’t find anymore nodes, we found the smallest one.

  要使用find_minimum_value方法：向下移至左侧。 如果我们再也找不到节点，我们将找到最小的节点。

def find_minimum_value(self):if self.left_child:return self.left_child.find_minimum_value()else:return self.value

Now let’s test it.

现在让我们对其进行测试。

We will use this tree to test our remove_node algorithm.

我们将使用此tree来测试remove_node算法。

#        |15|
#      /      \
#    |10|     |20|
#   /    \    /    \
# |8|   |12| |17| |25|
#              \
#              |19|

Let’s remove the node with the value 8. It’s a node with no child.

让我们删除node与value 8这是一个node ，没有孩子。

print(bst.remove_node(8, None)) # True
bst.pre_order_traversal()#     |15|
#   /      \
# |10|     |20|
#    \    /    \
#   |12| |17| |25|
#          \
#          |19|

Now let’s remove the node with the value 17. It’s a node with just one child.

现在，让我们删除node与value 17.这是一个node只有一个孩子。

print(bst.remove_node(17, None)) # True
bst.pre_order_traversal()#        |15|
#      /      \
#    |10|     |20|
#       \    /    \
#      |12| |19| |25|

Finally, we will remove a node with two children. This is the root of our tree.

最后，我们将删除具有两个子node 。 这是我们tree的root 。

print(bst.remove_node(15, None)) # True
bst.pre_order_traversal()#        |19|
#      /      \
#    |10|     |20|
#        \        \
#        |12|     |25|

The tests are now done. :)

现在测试已完成。 :)

目前为止就这样了！ (That’s all for now!)

We learned a lot here.

我们在这里学到了很多东西。

Congrats on finishing this dense content. It’s really tough to understand a concept that we do not know. But you did it. :)

恭喜您完成了此密集内容。 理解我们不知道的概念真的很困难。 但是你做到了。 :)

This is one more step forward in my journey to learning and mastering algorithms and data structures. You can see the documentation of my complete journey here on my Renaissance Developer publication.

这是我学习和掌握算法和数据结构的过程中又迈出的一步。 您可以在我的Renaissance Developer出版物上看到我完整旅程的文档。

Have fun, keep learning and coding.

玩得开心，继续学习和编码。

My Twitter & Github. ☺

我的Twitter和Github 。 ☺

额外资源 (Additional resources)

• Introduction to Tree Data Structure by mycodeschool

  mycodeschool对树数据结构的介绍

• Tree by Wikipedia

  维基百科的树

• How To Not Be Stumped By Trees by the talented Vaidehi Joshi

  有才华的Vaidehi Joshi如何不被树木绊倒

• Intro to Trees, Lecture by Professor Jonathan Cohen

  乔纳森·科恩 ( Jonathan Cohen)教授的树木简介

• Intro to Trees, Lecture by Professor David Schmidt

  树木简介， David Schmidt教授演讲

• Intro to Trees, Lecture by Professor Victor Adamchik

  树木介绍， Victor Adamchik教授的演讲

• Trees with Gayle Laakmann McDowell

  盖尔·拉克曼·麦克道尔(Gayle Laakmann McDowell)

• Binary Tree Implementation and Tests by TK

  TK的 二叉树实现和测试

• Coursera Course: Data Structures by University of California, San Diego

  Coursera课程： 加利福尼亚大学圣地亚哥分校的数据结构

• Coursera Course: Data Structures and Performance by University of California, San Diego

  Coursera课程： 加利福尼亚大学圣地亚哥分校的数据结构和性能

• Binary Search Tree concepts and Implementation by Paul Programming

  二进制搜索树的概念和Paul Programming的实现

• Binary Search Tree Implementation and Tests by TK

  TK的 二进制搜索树实现和测试

• Tree Traversal by Wikipedia

  维基百科的树遍历

• Binary Search Tree Remove Node Algorithm by GeeksforGeeks

  GeeksforGeeks的二叉搜索树删除节点算法

• Binary Search Tree Remove Node Algorithm by Algolist

  二叉搜索树删除节点算法通过Algolist

• Learning Python From Zero to Hero

  从零到英雄学习Python

翻译自: https://www.freecodecamp.org/news/all-you-need-to-know-about-tree-data-structures-bceacb85490c/

数据结构显示树的所有结点