02.md

二、树、堆和图

学习目标

本章结束时，您将能够:

• 分析和识别可以使用非线性数据结构的地方
• 实现和操作树结构来表示数据和解决问题
• 使用各种方法遍历树
• 实现一个图结构来表示数据和解决问题
• 基于给定的场景，使用不同的方法表示图

在本章中，我们将研究两种非线性数据结构，即树和图，以及它们如何用于表示现实场景和解决各种问题。

简介

在前一章中，我们实现了不同类型的线性数据结构，以线性方式存储和管理数据。在线性结构中，我们最多可以沿两个方向前进或后退。然而，这些结构的范围非常有限，不能用于解决高级问题。在这一章中，我们将探讨一类更高级的问题。我们将看到，我们之前实现的解决方案不够好，无法直接使用。因此，我们将扩展这些数据结构，以制作更复杂的结构，用于表示非线性数据。

看完这些问题后，我们将讨论使用树数据结构的基本解决方案。我们将实现不同类型的树来解决不同类型的问题。之后，我们将看一看一种特殊类型的树，叫做堆，以及它可能的实现和应用。接下来，我们将看看另一个复杂的结构-图表。我们将实现图的两种不同表示。这些结构有助于将现实世界的场景转化为数学形式。然后，我们将应用我们的编程技能和技术来解决与这些场景相关的问题。

对树和图的深刻理解是理解更高级问题的基础。数据库(B-trees)、数据编码/压缩(Huffman tree)、图着色、分配问题、最小距离问题以及许多其他问题都是使用树和图的某些变体来解决的。

现在，让我们看一些不能用线性数据结构表示的问题的例子。

非线性问题

借助线性数据结构无法表示的两种主要情况是层次问题和循环依赖。让我们仔细看看这些案例。

等级问题

让我们看几个本来就有层次属性的例子。以下是一个组织的结构:

图 2.1:组织结构

我们可以看到，CEO 是公司的负责人，管理副总监。副主任领导另外三名官员，以此类推。

数据本质上是分层的。这种类型的数据很难用简单的数组、向量或链表来管理。为了巩固我们的理解，让我们看看另一个用例；也就是一个大学课程的结构，如下图所示:

图 2.2:大学课程结构中的课程层次结构

上图显示了一所假设大学中某些课程的课程依赖关系。我们可以看到，要学习《高等物理 II》，学生必须顺利完成以下课程:高等物理和高等数学。同样，许多其他课程也有自己的先决条件。

给定这样的数据，我们可以有不同类型的查询。例如，我们可能想找出哪些课程需要成功完成，这样我们就可以学习《高等数学》。

这类问题可以用一种叫做树的数据结构来解决。所有的对象都被称为树的节点，而从一个节点到另一个节点的路径被称为边。我们将在本章稍后的图表部分对此进行更深入的研究。

循环依赖

让我们看看另一个复杂的现实场景，它可以用非线性结构更好地表示。下图代表了几个人之间的友谊:

图 2.3:朋友网络

这种结构称为图。人名或元素被称为节点，它们之间的关系被表示为边。这样的结构通常被各种社交网络用来代表他们的用户和他们之间的联系。我们可以观察到，爱丽丝是查理的朋友，查理是艾德的朋友，艾德是格蕾丝的朋友，等等。我们还可以推断爱丽丝、鲍勃和查理彼此认识。我们也可以推断，艾德对于格蕾丝来说是一级连接，查理是二级连接，爱丽丝和鲍勃是三级连接。

图表有用的另一个领域是当我们想要表示城市之间的道路网络时，正如您将在本章后面的图表部分看到的那样。

tree–颠倒了！

正如我们在上一节中所讨论的，树只不过是通过某种层次关系连接到其他节点的一些对象或节点。如果我们以图的方式显示这个层次，它看起来像一棵树，而不同的边看起来像它的分支。主节点不依赖于任何其他节点，也称为根节点，通常在顶部表示。所以，不像真正的树，这棵树是颠倒的，根在它的顶部！

让我们尝试为一个非常基本的组织层次结构构建一个结构。

练习 7:创建组织结构

在本练习中，我们将实现在本章介绍中看到的组织树的基本版本。让我们开始吧:

1. 首先，让我们包含所需的标题:

   #include <iostream>
   #include <queue>

2. For simplicity, we'll assume that any person can have, at most, two subordinates. We'll see that this is not difficult to extend to resemble real-life situations. This kind of tree is also known as a binary tree. Let's write a basic structure for that:

   struct node
   {
       std::string position;
       node *first, *second;
   };

   正如我们所看到的，任何节点都有两个到其他节点的链接——都是它们的下属。通过这样做，我们可以显示数据的递归结构。我们现在只存储这个位置，但是我们可以很容易地扩展到包括这个位置的名字，甚至包括这个位置的人的所有信息的整个结构。

3. 我们不希望最终用户处理这种原始数据结构。所以，让我们用一个叫做org_tree :

   struct org_tree
   {
       node *root;

   的界面来包装它

4. Now, let's add a function to create the root, starting with the highest commanding officer of the company:

   static org_tree create_org_structure(const std::string& pos)
   {
       org_tree tree;
       tree.root = new node{pos, NULL, NULL};
       return tree;
   }

   这是一个静态函数，只是为了创建树。现在，让我们看看如何扩展树。

5. Now, we want to add a subordinate of an employee. The function should take two parameters – the name of the already existing employee in the tree and the name of the new employee to be added as a subordinate. But before that, let's write another function that will help us find a particular node based on a value to make our insertion function easier:

   static node* find(node* root, const std::string& value)
   {
       if(root == NULL)
           return NULL;
       if(root->position == value)
           return root;
       auto firstFound = org_tree::find(root->first, value);
       if(firstFound != NULL)
           return firstFound;
       return org_tree::find(root->second, value);
   }

   当我们遍历树寻找一个元素时，这个元素要么是我们所在的节点，要么是在右边或左边的子树中。

   因此，我们需要首先检查根节点。如果它不是所需的节点，我们将尝试在左侧子树中找到它。最后，如果我们没有成功做到这一点，我们将查看正确的子树。

6. Now, let's implement the insertion function. We'll make use of the find function in order to reuse the code:

   bool addSubordinate(const std::string& manager, const std::string& subordinate)
   {
       auto managerNode = org_tree::find(root, manager);
       if(!managerNode)
       {
           std::cout << "No position named " << manager << std::endl;
           return false;
       }
       if(managerNode->first && managerNode->second)
       {
           std::cout << manager << " already has 2 subordinates." << std::endl;
           return false;
       }
       if(!managerNode->first)
           managerNode->first = new node{subordinate, NULL, NULL};
       else
           managerNode->second = new node{subordinate, NULL, NULL};
       return true;
   }
   };

   如我们所见，该函数返回一个布尔值，指示我们是否可以成功插入节点。

7. Now, let's use this code to create a tree in the main function:

   int main()
   {
       auto tree = org_tree::create_org_structure("CEO");
       if(tree.addSubordinate("CEO", "Deputy Director"))
           std::cout << "Added Deputy Director in the tree." << std::endl;
       else
           std::cout << "Couldn't add Deputy Director in the tree" << std::endl;
       if(tree.addSubordinate("Deputy Director", "IT Head"))
           std::cout << "Added IT Head in the tree." << std::endl;
       else
           std::cout << "Couldn't add IT Head in the tree" << std::endl;
       if(tree.addSubordinate("Deputy Director", "Marketing Head"))
           std::cout << "Added Marketing Head in the tree." << std::endl;
       else
           std::cout << "Couldn't add Marketing Head in the tree" << std::endl;
       if(tree.addSubordinate("IT Head", "Security Head"))
           std::cout << "Added Security Head in the tree." << std::endl;
       else
           std::cout << "Couldn't add Security Head in the tree" << std::endl;
       if(tree.addSubordinate("IT Head", "App Development Head"))
           std::cout << "Added App Development Head in the tree." << std::endl;
       else
           std::cout << "Couldn't add App Development Head in the tree" << std::endl;
   if(tree.addSubordinate("Marketing Head", "Logistics Head"))
           std::cout << "Added Logistics Head in the tree." << std::endl;
       else
           std::cout << "Couldn't add Logistics Head in the tree" << std::endl;
       if(tree.addSubordinate("Marketing Head", "Public Relations Head"))
           std::cout << "Added Public Relations Head in the tree." << std::endl;
       else
           std::cout << "Couldn't add Public Relations Head in the tree" << std::endl;
       if(tree.addSubordinate("Deputy Director", "Finance Head"))
           std::cout << "Added Finance Head in the tree." << std::endl;
       else
           std::cout << "Couldn't add Finance Head in the tree" << std::endl;
   }

   在执行前面的代码时，您应该会得到以下输出:

   Added Deputy Director in the tree.
   Added IT Head in the tree.
   Added Marketing Head in the tree.
   Added Security Head in the tree.
   Added App Development Head in the tree.
   Added Logistics Head in the tree.
   Added Public Relations Head in the tree.
   Deputy Director already has 2 subordinates.
   Couldn't add Finance Head in the tree

下图显示了该输出:

图 2.4:基于组织层次结构的二叉树

到目前为止，我们只是插入了元素。现在，我们来看看如何穿过这棵树。虽然我们已经看到了如何使用find函数遍历，但这只是我们可以做到的方法之一。我们可以用许多其他方式遍历树，所有这些我们将在下一节中讨论。

穿越树木

一旦我们有了一棵树，就有各种方法可以遍历它并到达我们需要的节点。让我们简单看一下各种遍历方法:

• Preorder traversal: In this method, we visit the current node first, followed by the left child of the current node, and then the right child of the current node in a recursive fashion. Here, the prefix "pre" indicates that the parent node is visited before its children. Traversing the tree shown in figure 2.4 using the preorder method goes like this:

  CEO, Deputy Director, IT Head, Security Head, App Development Head, Marketing Head, Logistics Head, Public Relations Head,

  正如我们所看到的，我们总是先访问父节点，然后是左子节点，然后是右子节点。我们这样做不仅仅是为了根，也是为了相对于它的子树的任何节点。我们使用这样一个函数来实现前序遍历:

  static void preOrder(node* start)
  {
      if(!start)
          return;
      std::cout << start->position << ", ";
      preOrder(start->first);
      preOrder(start->second);
  }

• In-order traversal: In this type of traversal, first we'll visit the left node, then the parent node, and finally the right node. Traversing the tree that's shown in figure 2.4 goes like this:

  Security Head, IT Head, App Development Head, Deputy Director, Logistics Head, Marketing Head, Public Relations Head, CEO, 

  我们可以用这样的函数来实现:

  static void inOrder(node* start)
  {
      if(!start)
          return;
      inOrder(start->first);
  std::cout << start->position << ", ";
      inOrder(start->second);
  }

• Post-order traversal: In this traversal, we first visit both the children, followed by the parent node. Traversing the tree that's shown in figure 2.4 goes like this:

  Security Head, App Development Head, IT Head, Logistics Head, Public Relations Head, Marketing Head, Deputy Director, CEO, 

  我们可以用这样的函数来实现:

  static void postOrder(node* start)
  {
      if(!start)
          return;
      postOrder(start->first);
      postOrder(start->second);
      std::cout << start->position << ", ";
  }

• Level order traversal: This requires us to traverse the tree level by level, from top to bottom, and from left to right. This is similar to listing the elements at each level of the tree, starting from the root level. The results of such a traversal are usually represented as per the levels, as shown here:

  CEO, 
  Deputy Director, 
  IT Head, Marketing Head, 
  Security Head, App Development Head, Logistics Head, Public Relations Head, 

  在下面的练习中演示了这种遍历方法的实现。

练习练习 8:演示层级顺序遍历

在本练习中，我们将在我们在练习 7 、创建组织结构中创建的组织结构中实现层级顺序遍历。与前面的遍历方法不同，这里我们不遍历直接连接到当前节点的节点。这意味着遍历在没有递归的情况下更容易实现。我们将扩展在练习 7 中显示的代码来演示这个遍历。让我们开始吧:

1. First, we'll add the following function inside the org_tree structure from Exercise 7:

   static void levelOrder(node* start)
   {
       if(!start)
           return;
       std::queue<node*> q;
       q.push(start);
       while(!q.empty())
       {
           int size = q.size();
           for(int i = 0; i < size; i++)
           {
               auto current = q.front();
               q.pop();
               std::cout << current->position << ", ";
               if(current->first)
                   q.push(current->first);
               if(current->second)
                   q.push(current->second);
           }
           std::cout << std::endl;
       }
   }

   如前面的代码所示，首先，我们遍历根节点，然后遍历其子节点。在访问孩子时，我们会在当前级别完成后将他们的孩子推到队列中进行处理。其思想是从第一级开始排队，然后将下一级的节点添加到队列中。我们将继续这样做，直到队列为空，这表明下一级中没有更多节点。

2. 我们的输出应该是这样的:

   CEO, 
   Deputy Director, 
   IT Head, Marketing Head, 
   Security Head, App Development Head, Logistics Head, Public Relations Head, 

树木的变种

在前面的练习中，我们主要看了二叉树，这是最常见的一种树。在二叉树中，每个节点最多可以有两个子节点。然而，普通的二叉树并不总是服务于这个目的。接下来，我们将看看二叉树的一个更专业的版本，叫做二叉查找树。

比娜里搜索树

A 二叉查找树 ( BST )是二叉树的流行版本。BST 只不过是一棵二叉树，具有以下属性:

• 父节点的值≥左子节点的值
• 父节点的值≤右子节点的值

简而言之，左子≤父≤右子。

这就引出了一个有趣的特点。在任何时间点，我们总是可以说，所有小于或等于父节点的元素都将在左侧，而大于或等于父节点的元素将在右侧。因此，搜索一个元素的问题在每一步都在减少一半，就搜索空间而言。

如果 BST 的构造方式是，除了最后一级的元素外，所有元素都有两个子元素，那么树的高度将是 log n ，其中 n 是元素的数量。因此，搜索和插入的时间复杂度为 O(对数 n) 。这种类型的二叉树也被称为完全二叉树。

在基站中搜索

让我们看看如何在二叉查找树中搜索、插入和删除元素。考虑一个具有唯一正整数的 BST，如下图所示:

图 2.5:在二叉查找树中搜索元素

假设我们必须搜索 7。从上图中箭头所代表的步骤中我们可以看到，在将值与当前节点的数据进行比较后，我们选择了边。正如我们已经提到的，左边的所有节点总是小于当前节点，右边的所有节点总是大于当前节点。

因此，我们从比较根节点和 7 开始。如果它大于 7，我们移动到左边的子树，因为那里的所有元素都小于父节点，反之亦然。我们比较每个子节点，直到我们偶然发现 7，或者一个小于 7 的节点没有正确的节点。在这种情况下，到达节点 4 会到达我们的目标 7。

如我们所见，我们没有穿越整棵树。相反，每次当前节点不是所需节点时，我们都会将范围缩小一半，这是通过选择左侧或右侧来实现的。这类似于线性结构的二分搜索法，我们将在章节4分治中了解。

在 BST 中插入新元素

现在，让我们看看插入是如何工作的。步骤如下图所示:

图 2.6:将元素插入二叉查找树

如您所见，首先，我们必须找到要插入新值的父节点。因此，我们必须采取类似于我们搜索的方法；也就是说，从根节点开始，通过将每个节点与我们的新元素进行比较来确定方向。最后一步，18 大于 17，但是 17 没有合适的孩子。因此，我们在那个位置插入 18。

从 BST 中删除元素

现在，让我们看看删除是如何工作的。考虑以下英国标准时间:

图 2.7:12 岁的二叉查找树

我们将删除树中的根节点 12。让我们看看如何删除任何值。这比插入要复杂一点，因为我们需要找到被删除节点的替换，以便 BST 的属性保持真实。

第一步是找到要删除的节点。之后，有三种可能:

• 该节点没有子节点:只需删除该节点。
• 该节点只有一个子节点:将父节点的相应指针指向唯一存在的子节点。
• 该节点有两个子节点:在这种情况下，我们用它的后继节点替换当前节点。

后继节点是当前节点之后的下一个最大数字。或者，换句话说，后继元素是所有元素中大于当前元素的最小元素。因此，我们将首先去右边的子树，它包含所有比当前元素大的元素，并找到其中最小的元素。找到最小的节点意味着尽可能地去子树的左边，因为左边的子节点总是比它的父节点少。在图 2.7 所示的树中，12 的右子树从 18 开始。所以，我们从那里开始看，然后试着向下移动到左边 15 岁的孩子。但是 15 号没有留下孩子，另一个孩子 16 号比 15 号大。因此，15 岁应该是这里的接班人。

要将 12 替换为 15，首先，我们将在删除 12 的同时复制根处的后继值，如下图所示:

图 2.8:复制到根节点的后继节点

接下来，我们需要从右侧子树的旧位置删除后继节点 15，如下图所示:

图 2.9:从原来位置删除的继任者

在最后一步，我们删除节点 15。我们对这个删除也使用相同的过程。由于 15 岁只有一个孩子，我们用 15 岁的孩子代替了 18 岁的左孩子。因此，以 16 为根的整个子树成为 18 的左子树。

注意

后续节点最多只能有一个子节点。如果它有一个左子节点，我们会选择该子节点而不是当前节点作为后继节点。

树上操作的时间复杂性

现在，让我们看看这些函数的时间复杂性。理论上，我们可以说我们每次都将搜索范围缩小了一半。因此，搜索具有 n 个节点的基站所需的时间是 T(n) = T(n / 2) + 1 。该方程导致时间复杂度为 T(n) = O(对数 n) 。

但这其中有蹊跷。如果我们仔细观察插入函数，插入的顺序实际上决定了树的形状。而且我们总是会把搜索范围缩小一半也不一定是真的，就像前面公式中 T(n/2) 描述的那样。因此，复杂性 O(对数 n) 并不总是准确的。我们将在平衡树部分更深入地研究这个问题及其解决方案，在这里我们将看到如何更准确地计算时间复杂度。

现在，让我们实现刚刚在 C++ 中看到的操作。

练习 9:实现二叉查找树

在本练习中，我们将实现图 2.7 中所示的 BST，并添加一个find函数来搜索元素。我们还将尝试插入和删除元素，如前面小节所述。让我们开始吧:

1. 首先，让我们包含所需的标题:

   #include <iostream>

2. 现在，让我们写一个节点。这将类似于我们之前的练习，除了我们将有一个整数而不是字符串:

   struct node
   {
       int data;
       node *left, *right;
   };

3. 现在，让我们在节点上添加一个包装器来提供一个干净的接口:

   struct bst
   {
       node* root = nullptr;

4. Before writing the insertion function, we'll need to write the find function:

   node* find(int value)
   {
       return find_impl(root, value);
   }
       private:
   node* find_impl(node* current, int value)
   {
       if(!current)
       {
           std::cout << std::endl;
           return NULL;
       }
       if(current->data == value)
       {
           std::cout << "Found " << value << std::endl;
           return current;
       }
       if(value < current->data)  // Value will be in the left subtree
       {
           std::cout << "Going left from " << current->data << ", ";
           return find_impl(current->left, value);
       }
       if(value > current->data) // Value will be in the right subtree
       {
           std::cout << "Going right from " << current->data << ", ";
           return find_impl(current->right, value);
       }
   }

   由于这是递归的，我们将实现保存在一个单独的函数中，并使其私有，以防止有人直接使用它。

5. Now, let's write an insert function. It will be similar to the find function, but with small tweaks. First, let's find the parent node, which is where we want to insert the new value:

   public:
   void insert(int value)
   {
       if(!root)
           root = new node{value, NULL, NULL};
       else
           insert_impl(root, value);
   }
   private:
   void insert_impl(node* current, int value)
   {
       if(value < current->data)
       {
           if(!current->left)
               current->left = new node{value, NULL, NULL};
           else
               insert_impl(current->left, value);
       }
       else
       {
           if(!current->right)
               current->right = new node{value, NULL, NULL};
               else
                   insert_impl(current->right, value);
       }
   }

   正如我们所看到的，我们正在检查该值应该插入左还是右子树。如果期望的一侧什么都没有，我们直接在那里插入节点；否则，我们递归调用该侧的insert函数。

6. 现在，让我们编写一个inorder遍历函数。当应用于 BST 时，有序遍历提供了一个重要的优势，正如我们将在输出中看到的:

   public:
   void inorder()
   {
       inorder_impl(root);
   }
   private:
   void inorder_impl(node* start)
   {
       if(!start)
           return;
       inorder_impl(start->left);        // Visit the left sub-tree
       std::cout << start->data << " ";  // Print out the current node
       inorder_impl(start->right);       // Visit the right sub-tree
   }

7. Now, let's implement a utility function to get the successor:

   public:
   node* successor(node* start)
   {
       auto current = start->right;
       while(current && current->left)
           current = current->left;
       return current;
   }

   这遵循了我们在删除 BST 小节中讨论的逻辑。

8. 现在来看看delete的实际实现。因为删除需要重新初始化父节点，所以我们将通过每次返回新节点来实现。我们将通过放置一个更好的接口来隐藏这种复杂性。我们将命名接口deleteValue，因为delete是一个保留的关键字，按照 C++ 标准:

   void deleteValue(int value)
   {
       root = delete_impl(root, value);
   }
   private:
   node* delete_impl(node* start, int value)
   {
       if(!start)
           return NULL;
       if(value < start->data)
           start->left = delete_impl(start->left, value);
       else if(value > start->data)
           start->right = delete_impl(start->right, value);
       else
       {
           if(!start->left)  // Either both children are absent or only left child is absent
           {
               auto tmp = start->right;
               delete start;
               return tmp;
           }
           if(!start->right)  // Only right child is absent
           {
               auto tmp = start->left;
               delete start;
               return tmp;
           }
           auto succNode = successor(start);
           start->data = succNode->data;
           // Delete the successor from right subtree, since it will always be in the right subtree
           start->right = delete_impl(start->right, succNode->data);
       }
       return start;
   }
   };

9. Let's write the main function so that we can use the BST:

   int main()
   {
       bst tree;
       tree.insert(12);
       tree.insert(10);
       tree.insert(20);
       tree.insert(8);
       tree.insert(11);
       tree.insert(15);
       tree.insert(28);
       tree.insert(4);
       tree.insert(2);
       std::cout << "Inorder: ";
       tree.inorder();  // This will print all the elements in ascending order
       std::cout << std::endl;
       tree.deleteValue(12);
       std::cout << "Inorder after deleting 12: ";
       tree.inorder();  // This will print all the elements in ascending order
       std::cout << std::endl;
       if(tree.find(12))
           std::cout << "Element 12 is present in the tree" << std::endl;
       else
           std::cout << "Element 12 is NOT present in the tree" << std::endl;
   }

   执行上述代码时的输出应该如下所示:

   Inorder: 2 4 8 10 11 12 15 20 28 
   Inorder after deleting 12: 2 4 8 10 11 15 20 28 
   Going left from 15, Going right from 10, Going right from 11, 
   Element 12 is NOT present in the tree

观察前面的顺序遍历的结果。按顺序将首先访问左边的子树，然后访问当前节点，然后递归地访问右边的子树，如代码片段中的注释所示。因此，根据 BST 属性，我们将首先访问所有小于当前值的值，然后是当前值，之后，我们将访问所有大于当前值的值。由于这是递归发生的，我们将按照升序对数据进行排序。

平衡树

在我们理解平衡树之前，让我们从一个 BST 的例子开始，其插入顺序如下:

bst tree;
tree.insert(10);
tree.insert(9);
tree.insert(11);
tree.insert(8);
tree.insert(7);
tree.insert(6);
tree.insert(5);
tree.insert(4);

在下图的帮助下，该基站可以可视化:

图 2.10:倾斜的二叉查找树

如上图所示，几乎整棵树都向左侧倾斜。如果调用find函数，即bst.find(4)，步骤如下:

图 2.11:在倾斜的二叉查找树中找到一个元素

我们可以看到，步骤的数量几乎等于元素的数量。现在，让我们用不同的插入顺序再次尝试同样的事情，如下所示:

bst tree;
tree.insert(7);
tree.insert(5);
tree.insert(9);
tree.insert(4);
tree.insert(6);
tree.insert(10);
tree.insert(11);
tree.insert(8);

查找元素 4 所需的 BST 和步骤现在将如下所示:

图 2.12:在平衡树中找到一个元素

如我们所见，这棵树不再倾斜了。或者，换句话说，树是平衡的。这种配置大大减少了查找 4 的步骤。因此，find的时间复杂度不仅取决于元素的数量，还取决于它们在树中的配置。如果我们仔细看台阶，我们总是朝着树的底部走一步，同时寻找一些东西。最后，我们到达叶节点(没有任何子节点的节点)。这里，我们根据元素的可用性返回所需的节点或空值。所以，我们可以说台阶的数量总是小于 BST 中的最大层数，也就是 BST 的高度。所以，寻找一个元素的实际时间复杂度是 O(高度)。

为了优化时间复杂度，我们需要优化树的高度。这也叫平衡一棵树。其思想是在插入/删除后重新组织节点，以减少树的偏斜度。生成的树被称为高度平衡的 BST。

有各种方法可以做到这一点，并获得不同类型的树，如 AVL 树、红黑树等。AVL 树背后的想法是执行一些旋转来平衡树的高度，同时仍然保持 BST 属性。考虑下图所示的示例:

图 2.13:旋转树

正如我们所看到的，右边的树比左边的树更平衡。轮换不在本书的讨论范围之内，因此我们不会冒险讨论这个例子的细节。

N-和树

到目前为止，我们主要看到了二叉树或它们的变种。对于 N 元树，每个节点可以有 N 个子节点。由于 N 在这里是任意的，我们将把它存储在一个向量中。最后的结构看起来像这样:

struct nTree
{
    int data;
    std::vector<nTree*> children;
};

如我们所见，每个节点可以有任意数量的子节点。因此，整棵树是完全任意的。然而，就像普通的二叉树一样，普通的 N 元树也不是很有用。因此，我们必须为不同类型的应用构建一个不同的树，其中层次比二叉树的层次更高。在图 2.1 中显示的例子，代表了一个组织的层次结构，是一个 N 元树。

在计算机世界中，有两种非常好的、众所周知的 N 元树实现，如下所示:

• 计算机中的文件系统结构:从 Linux 中的root ( /)或 Windows 中的驱动器开始，我们可以在任何文件夹中拥有任意数量的文件(终端节点)和任意数量的文件夹。我们将在活动 1，为文件系统创建数据结构中更详细地了解这一点。
• 编译器:大多数编译器基于用于源代码的标准定义的语法来构建抽象语法树。编译器通过解析 AST 生成低级代码。

活动 4:为文件系统创建数据结构

使用 N 元树为支持以下操作的文件系统创建数据结构:转到目录、查找文件/目录、添加文件/目录和列出文件/目录。我们的树将保存文件系统中所有元素(文件和文件夹)的信息和文件夹层次结构(路径)。

执行以下步骤来解决此活动:

1. 创建一个 N 元树，在一个节点中包含两个数据元素——目录/文件的名称和一个指示它是目录还是文件的标志。

2. 添加一个数据成员来存储当前目录。

3. 用单个根目录(/)初始化树。

4. 添加查找目录/文件功能，该功能采用单个参数–path。path可以是绝对的(从/开始)也可以是相对的。

5. 添加功能以添加文件/目录并列出位于给定路径的文件/目录。

6. Similarly, add a function to change the current directory.

   注意

   这个活动的解决方案可以在第 490 页找到。

我们已经打印了前面带有d的目录，以区别于前面带有“–”(连字符)的文件。您可以尝试创建更多具有绝对或相对路径的目录和文件。

到目前为止，我们还没有支持某些 Linux 约定，比如用单点寻址任何目录，用双点寻址父目录。这可以通过扩展我们的节点来实现，也可以保存一个指向其父节点的指针。这样，我们可以非常容易地在两个方向上遍历。还有各种其他可能的扩展，例如添加符号链接，以及使用“*”扩展各种文件/目录名称的 globing 运算符。这个练习为我们提供了一个基础，这样我们就可以根据我们的需求自己构建一些东西。

堆

在前一章中，我们简单介绍了堆以及 C++ 如何通过 STL 提供堆。在这一章中，我们将深入研究堆。简单回顾一下，以下是预期的时间复杂性:

• O(1) :立即访问最大元素
• O(log n) :插入任何元素
• 0(对数 n) :删除最大元素

为了实现 O(log n) 的插入/删除，我们将使用一棵树来存储数据。但在这种情况下，我们将使用完整的树。一个完全树被定义为这样一个树，其中除了最后一级之外的所有级别的节点都有两个子节点，并且最后一级在左侧具有尽可能多的元素。例如，考虑下图所示的两棵树:

图 2.14:完整树与非完整树

因此，只要有足够的空间，可以通过在最后一层插入元素来构建一个完整的树。如果没有，我们将在新级别的最左边位置插入它们。这给了我们一个很好的机会，用数组一级一级地存储这个树。因此，树的根将是数组/向量的第一个元素，然后是它的左子元素，然后是右子元素，依此类推。与其他树不同，这是一种非常高效的内存结构，因为不需要额外的内存来存储指针。要从父节点转到它的子节点，我们可以很容易地使用数组的索引。如果父节点是第 i 第节点，则其子节点将始终是 2i + 1* 和 2i + 2* 索引。同样，我们可以通过使用*(I–1)/2*来获取 i 第子节点的父节点。我们也可以从上图中证实这一点。

现在，让我们看看每次插入/删除时需要维护的不变量(或条件)。第一个要求是即时访问 max 元素。为此，我们需要确定它的位置，以便每次都能立即访问它。我们将始终将 max 元素保持在顶部–根位置。现在，为了保持这一点，我们还需要保持另一个不变量——父节点必须大于它的两个子节点。这样的堆也称为最大堆。

正如您可能猜到的，快速访问最大元素所需的属性可以很容易地反转，以便快速访问最小元素。我们所需要做的就是在执行堆操作时反转我们的比较函数。这种堆被称为 min 堆。

堆操作

在本节中，我们将看到如何在堆上执行不同的操作。

将元素插入堆中

作为插入的第一步，我们将保留最重要的不变量，这为我们提供了一种将这个结构表示为数组的方法——一个完整的树。这可以很容易地通过在末尾插入新元素来完成，因为它将代表最后一级中的元素，就在所有现有元素之后，或者如果当前最后一级已满，则作为新级别中的第一个元素。

现在，我们需要保留另一个不变量——如果可用，所有节点的值都必须大于它们的两个子节点。假设我们当前的树已经遵循这个不变量，在最后一个位置插入新元素之后，唯一一个不变量可能失败的元素将是最后一个元素。为了解决这个问题，如果父元素比元素小，我们就用它的父元素交换元素。即使父元素已经有另一个元素，它也会比新元素小(新元素>父元素>子元素)。

因此，通过将新元素视为根而创建的子树满足所有不变量。但是，新元素可能仍然大于它的新父元素。因此，我们需要继续交换节点，直到整个树满足不变量。由于一棵完整的树的高度最多为 O(log n) ，整个操作最多需要 O(log n) 的时间。下图说明了向树中插入元素的操作:

图 2.15:将一个元素插入具有一个节点的堆中

如上图所示，在插入 11 之后，树不再具有 heap 属性。因此，我们将交换 10 和 11，使其再次成为堆。这个概念在下面的例子中更清晰，这个例子有更多的层次:

图 2.16:将一个元素插入到具有几个节点的堆中

从堆中删除元素

首先要注意的是，我们只能删除 max 元素。我们不能直接接触任何其他元素。max 元素始终出现在根处。因此，我们将移除根元素。但是我们也需要决定谁来承担它的责任。为此，我们首先需要用最后一个元素交换根，然后移除最后一个元素。这样，我们的根将被删除，但它将打破每个父节点大于其子节点的不变性。为了解决这个问题，我们将把根与其两个子节点进行比较，然后用更大的子节点替换它。现在，不变量在其中一个子树处被打破。我们在整个子树中递归地继续交换过程。这样，不变量的断点就沿着树向下冒泡了。就像插入一样，我们遵循这个规则，直到遇到不变量。所需的最大步数将等于树的高度，即 O(log n) 。下图说明了这一过程:

图 2.17:删除堆中的元素

堆的初始化

现在，让我们看看最重要的步骤之一——堆的初始化。与向量、列表、deq 等不同，堆的初始化并不简单，因为我们需要维护堆的不变量。一个简单的解决方案是从一个空堆开始逐个插入所有元素。但这需要的时间是 O(n * log(n)) ，效率不高。

然而，有一个堆积算法可以在*0(n)*时间内完成。这背后的想法非常简单:我们不断更新树，以自下而上的方式匹配较小子树的堆属性。首先，最后一级已经具有堆的属性。接下来，我们一级一级地向根前进，使每个子树一个接一个地遵循堆属性。这个过程只有 O(n) 的时间复杂度。幸运的是，C++ 标准已经为此提供了一个名为std::make_heap的函数，它可以接受任何数组或向量迭代器，并将它们转换成堆。

练习 10:流中位数

在本练习中，我们将解决一个有趣的问题，这个问题经常出现在与数据分析相关的应用中，包括机器学习。想象一下，某个数据源一次给我们一个连续的数据元素(数据流)。我们需要在接收到每一个元素之后，找到到目前为止已经接收到的元素的中间值。一种简单的方法是每次有新元素进来时对数据进行排序，并返回中间的元素。但由于排序，这将有一个时间复杂度。根据传入元素的速率，这可能非常耗费资源。然而，我们将在堆的帮助下对此进行优化。让我们开始吧:

1. 让我们首先包含所需的标题:

   #include <iostream>
   #include <queue>
   #include <vector>

2. 现在，让我们编写一个容器来存储到目前为止收到的数据。我们将数据存储在两个堆中——一个最小堆和一个最大堆。我们将把较小的元素的前半部分存储在一个最大堆中，把较大的或者另一半存储在一个最小堆中。因此，在任何时候，都可以仅使用堆的顶部元素来计算中位数，这些元素很容易访问:

   struct median
   {
       std::priority_queue<int> maxHeap;
       std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

3. 现在，让我们编写一个insert函数，以便插入新到达的数据:

   void insert(int data)
   {
       // First element
       if(maxHeap.size() == 0)
       {
           maxHeap.push(data);
           return;
       }
       if(maxHeap.size() == minHeap.size())
       {
           if(data <= get())
               maxHeap.push(data);
           else
               minHeap.push(data);
           return;
       }
       if(maxHeap.size() < minHeap.size())
       {
           if(data > get())
           {
               maxHeap.push(minHeap.top());
               minHeap.pop();
               minHeap.push(data);
           }
           else
               maxHeap.push(data);
           return;
       }
       if(data < get())
       {
           minHeap.push(maxHeap.top());
           maxHeap.pop();
           maxHeap.push(data);
       }
       else
           minHeap.push(data);
   }

4. 现在，让我们写一个get函数，这样我们就可以从容器中得到中位数:

   double get()
   {
       if(maxHeap.size() == minHeap.size())
           return (maxHeap.top() + minHeap.top()) / 2.0;
       if(maxHeap.size() < minHeap.size())
           return minHeap.top();
       return maxHeap.top();
   }
   };

5. Now, let's write a main function so that we can use this class:

   int main()
   {
       median med;
       med.insert(1);
       std::cout << "Median after insert 1: " << med.get() << std::endl;
       med.insert(5);
       std::cout << "Median after insert 5: " << med.get() << std::endl;
       med.insert(2);
       std::cout << "Median after insert 2: " << med.get() << std::endl;
       med.insert(10);
       std::cout << "Median after insert 10: " << med.get() << std::endl;
       med.insert(40);
       std::cout << "Median after insert 40: " << med.get() << std::endl;
       return 0;
   }

   前面程序的输出如下:

   Median after insert 1: 1
   Median after insert 5: 3
   Median after insert 2: 2
   Median after insert 10: 3.5
   Median after insert 40: 5

这样，我们只需要插入任何新到达的元素，其时间复杂度仅为 O(log n) ，而如果我们用每个新元素对元素进行排序，则时间复杂度为 O(n log n) 。

活动 5:使用堆的 K 路合并

考虑一个与遗传学相关的生物医学应用，用于处理大型数据集。它需要以排序的方式排列 DNA 来计算相似性。但是由于数据集很大，它不能放在一台机器上。因此，它在分布式集群中处理和存储数据，每个节点都有一组排序值。主处理引擎要求所有数据以排序的方式存储在一个流中。因此，基本上，我们需要将多个排序数组合并成一个排序数组。借助向量模拟这种情况。

执行以下步骤来解决此活动:

1. 最小的数字将出现在所有列表的第一个元素中，因为所有列表已经被单独排序。为了更快地获得最小值，我们将构建一堆这些元素。

2. 从堆中获取最小元素后，我们需要移除它，并用它所属的同一列表中的下一个元素替换它。

3. The heap node must contain information about the list so that it can find the next number from that list.

   注意

   这个活动的解决方案可以在第 495 页找到。

现在，让我们计算前面算法的时间复杂度。如果有 k 列表可用，我们的堆大小将为 k，所有的堆操作将为 O(log k) 。建筑堆将是 O(k 原木 k) 。之后，我们将不得不对结果中的每个元素执行堆操作。总元素为 n × k 。因此，总复杂度将为 O(nk log k) 。

这个算法的奇妙之处在于，考虑到我们前面描述的现实场景，它实际上并不需要同时存储所有的 n × k 元素；它只需要在任意时间点存储 k 元素，其中 k 是集群中列表或节点的数量。正因如此， k 的值永远不会太大。在堆的帮助下，我们可以一次生成一个数字，并立即处理该数字，或者将其流式传输到其他地方进行处理，而无需实际存储它。

图表

虽然树 i 是表示分层数据的一种很好的方式，但是我们不能表示树中的循环或循环依赖关系，因为我们总是有一个单一且唯一的路径从一个节点到另一个节点。然而，有更复杂的场景具有固有的循环结构。例如，考虑一个道路网络。从一个地方到另一个地方可以有多种方式(地方可以表示为节点)。这样一组场景可以用图表更好地表示。

与树不同，图必须存储节点以及节点之间的边的数据。例如，在任何道路网络中，对于每个节点(地点)，我们必须存储关于它连接到哪些其他节点(地点)的信息。这样，我们就可以形成一个包含所有需要的节点和边的图。这叫做未加权图。我们可以为每个边添加权重或更多信息。对于我们的道路网络示例，我们可以添加每个边(路径)从一个节点(位置)到另一个节点(位置)的距离。这种表示法被称为“T4”加权图“T5”，它包含了解决诸如寻找一个地方与另一个地方之间距离最小的路径等问题所需的道路网络的所有信息。

有两种类型的图——无向图和有向图。无向图表示边是双向的。双向表示双边或可交换的属性。对于道路网络示例，点 A 和 B 之间的双向边意味着我们可以从 A 到 B，以及从 B 到 A。但是假设我们有一些单向限制的道路–我们需要使用有向图来表示。在有向图中，每当我们需要指出我们可以朝任何一个方向前进时，我们都使用两条边——从 A 点到 B 点，以及从 B 点到 A 点。我们将主要关注双向图，但是我们在这里将学习的关于结构和遍历方法的内容对于有向图也同样适用。唯一的变化是我们如何给图添加边。

因为一个图可以有循环边和从一个节点到另一个节点的多条路径，我们需要唯一地识别每个节点。为此，我们可以为每个节点分配一个标识符。为了表示图的数据，我们并不真的需要像在树中那样以编程方式构建类似节点的结构。事实上，我们可以通过组合std容器来存储整个图。

将图表示为邻接矩阵

这里有一个最简单的理解图的方法——考虑一组节点，其中任何节点都可以直接连接到组中的任何其他节点。这意味着我们可以使用一个 2D 数组来表示这一点，对于一个具有 N 节点的图来说，这个数组的大小为 N × N 。每个单元格中的值将根据单元格的索引指示相应节点之间的边的权重。因此，data[1][2]将指示节点 1 和节点 2 之间的边的权重。这种方法被称为邻接矩阵。我们可以使用-1 的权重来表示没有边。

考虑下图所示的加权图，它代表几个主要国际城市之间的航空网络，带有假设的距离:

图 2.18:部分城市间的航空网络

如上图所示，我们可以从伦敦经伊斯坦布尔或直接去迪拜。从一个地方到另一个地方有多种方式，而树木不是这样。此外，我们可以从一个节点遍历到另一个节点，并通过一些不同的边回到原始节点，这在树中也是不可能的。

让我们为上图所示的图实现矩阵表示方法。

练习 11:实现一个图并将其表示为邻接矩阵

在本练习中，我们将实现一个代表上图所示城市网络的图，并演示如何将其存储为邻接矩阵。让我们开始吧:

1. 首先，让我们包含所需的标题:

   #include <iostream>
   #include <vector>

2. 现在，让我们添加一个enum类，以便存储城市名称:

   enum class city: int
   {
       LONDON,
       MOSCOW,
       ISTANBUL,
       DUBAI,
       MUMBAI,
       SEATTLE,
       SINGAPORE
   };

3. 让我们也为city枚举添加一个<<运算符:

   std::ostream& operator<<(std::ostream& os, const city c)
   {
       switch(c)
       {
           case city::LONDON:
               os << "LONDON";
               return os;
           case city::MOSCOW:
               os << "MOSCOW";
               return os;
           case city::ISTANBUL:
               os << "ISTANBUL";
               return os;
           case city::DUBAI:
               os << "DUBAI";
               return os;
           case city::MUMBAI:
               os << "MUMBAI";
               return os;
           case city::SEATTLE:
               os << "SEATTLE";
               return os;
           case city::SINGAPORE:
               os << "SINGAPORE";
               return os;
           default:
               return os;
       }
   }

4. 让我们写struct graph，它将封装我们的数据:

   struct graph
   {
       std::vector<std::vector<int>> data;

5. 现在，让我们添加一个构造函数，该构造函数将创建一个具有给定节点数的空图(没有任何边的图):

   graph(int n)
   {
       data.reserve(n);
       std::vector<int> row(n);
       std::fill(row.begin(), row.end(), -1);
       for(int i = 0; i < n; i++)
       {
           data.push_back(row);
       }
   }

6. 现在，让我们添加最重要的功能–addEdge。需要三个参数——要连接的两个城市和边缘的重量(距离):

   void addEdge(const city c1, const city c2, int dis)
   {
       std::cout << "ADD: " << c1 << "-" << c2 << "=" << dis << std::endl;
       auto n1 = static_cast<int>(c1);
       auto n2 = static_cast<int>(c2);
       data[n1][n2] = dis;
       data[n2][n1] = dis;
   }

7. 现在，让我们添加一个函数，这样我们就可以从图中移除一条边:

   void removeEdge(const city c1, const city c2)
   {
       std::cout << "REMOVE: " << c1 << "-" << c2 << std::endl;
       auto n1 = static_cast<int>(c1);
       auto n2 = static_cast<int>(c2);
       data[n1][n2] = -1;
       data[n2][n1] = -1;
   }
   };

8. 现在，让我们编写main函数，以便使用这些函数:

   int main()
   {
       graph g(7);
       g.addEdge(city::LONDON, city::MOSCOW, 900);
       g.addEdge(city::LONDON, city::ISTANBUL, 500);
       g.addEdge(city::LONDON, city::DUBAI, 1000);
       g.addEdge(city::ISTANBUL, city::MOSCOW, 1000);
       g.addEdge(city::ISTANBUL, city::DUBAI, 500);
       g.addEdge(city::DUBAI, city::MUMBAI, 200);
       g.addEdge(city::ISTANBUL, city::SEATTLE, 1500);
       g.addEdge(city::DUBAI, city::SINGAPORE, 500);
       g.addEdge(city::MOSCOW, city::SEATTLE, 1000);
       g.addEdge(city::MUMBAI, city::SINGAPORE, 300);
       g.addEdge(city::SEATTLE, city::SINGAPORE, 700);
       g.addEdge(city::SEATTLE, city::LONDON, 1800);
       g.removeEdge(city::SEATTLE, city::LONDON);
       return 0;
   }

9. 在执行这个程序时，我们应该得到如下输出:

   ADD: LONDON-MOSCOW=900
   ADD: LONDON-ISTANBUL=500
   ADD: LONDON-DUBAI=1000
   ADD: ISTANBUL-MOSCOW=1000
   ADD: ISTANBUL-DUBAI=500
   ADD: DUBAI-MUMBAI=200
   ADD: ISTANBUL-SEATTLE=1500
   ADD: DUBAI-SINGAPORE=500
   ADD: MOSCOW-SEATTLE=1000
   ADD: MUMBAI-SINGAPORE=300
   ADD: SEATTLE-SINGAPORE=700
   ADD: SEATTLE-LONDON=1800
   REMOVE: SEATTLE-LONDON

如我们所见，我们将数据存储在向量的向量中，两个维度都等于节点数。因此，该表示所需的总空间与 V2 成比例，其中 V 是节点的数量。

将一个图表示为邻接表

图的矩阵表示的一个主要问题是所需的内存量与节点数的平方成正比。正如您可能想象的那样，随着节点数量的增加，这种情况会迅速增加。让我们看看如何改进这一点，以便使用更少的内存。

在任何图中，我们都有固定数量的节点，每个节点都有固定的最大连接节点数，等于总节点数。在矩阵中，我们必须存储所有节点的所有边，即使两个节点没有直接连接在一起。相反，我们将只存储每行中节点的标识，指示哪些节点直接连接到当前节点。这种表示也称为邻接表。

让我们看看与前面的练习相比，实现有何不同。

练习 12:实现一个图并将其表示为邻接表

在本练习中，我们将实现一个代表图 2.18 中所示的城市网络的图，并演示如何将其存储为邻接表。让我们开始吧:

1. 在本练习中，我们将实现邻接表表示。让我们从标题开始，像往常一样:

   #include <iostream>
   #include <vector>
   #include <algorithm>

2. 现在，让我们添加一个enum类，以便存储城市名称:

   enum class city: int
   {
       MOSCOW,
       LONDON,
       ISTANBUL,
       SEATTLE,
       DUBAI,
       MUMBAI,
       SINGAPORE
   };

3. 让我们也为city枚举添加<<运算符:

   std::ostream& operator<<(std::ostream& os, const city c)
   {
       switch(c)
       {
           case city::MOSCOW:
               os << "MOSCOW";
               return os;
           case city::LONDON:
               os << "LONDON";
               return os;
           case city::ISTANBUL:
               os << "ISTANBUL";
               return os;
           case city::SEATTLE:
               os << "SEATTLE";
               return os;
           case city::DUBAI:
               os << "DUBAI";
               return os;
           case city::MUMBAI:
               os << "MUMBAI";
               return os;
           case city::SINGAPORE:
               os << "SINGAPORE";
               return os;
           default:
               return os;
       }
   }

4. 让我们写struct graph，它将封装我们的数据:

   struct graph
   {
       std::vector<std::vector<std::pair<int, int>>> data;

5. Let's see how our constructor defers from a matrix representation:

   graph(int n)
   {
       data = std::vector<std::vector<std::pair<int, int>>>(n, std::vector<std::pair<int, int>>());
   }

   如我们所见，我们正在用 2D 向量初始化数据，但是所有的行最初都是空的，因为在开始处没有边。

6. 让我们为此实现addEdge功能:

   void addEdge(const city c1, const city c2, int dis)
   {
       std::cout << "ADD: " << c1 << "-" << c2 << "=" << dis << std::endl;
       auto n1 = static_cast<int>(c1);
       auto n2 = static_cast<int>(c2);
       data[n1].push_back({n2, dis});
       data[n2].push_back({n1, dis});
   }

7. 现在，让我们写下removeEdge，这样我们就可以从图中删除一条边:

   void removeEdge(const city c1, const city c2)
   {
       std::cout << "REMOVE: " << c1 << "-" << c2 << std::endl;
       auto n1 = static_cast<int>(c1);
       auto n2 = static_cast<int>(c2);
       std::remove_if(data[n1].begin(), data[n1].end(), [n2](const auto& pair)
           {
               return pair.first == n2;
           });
       std::remove_if(data[n2].begin(), data[n2].end(), [n1](const auto& pair)
           {
               return pair.first == n1;
           });
   }
   };

8. Now, let's write the main function so that we can use these functions:

   int main()
   {
       graph g(7);
       g.addEdge(city::LONDON, city::MOSCOW, 900);
       g.addEdge(city::LONDON, city::ISTANBUL, 500);
       g.addEdge(city::LONDON, city::DUBAI, 1000);
       g.addEdge(city::ISTANBUL, city::MOSCOW, 1000);
       g.addEdge(city::ISTANBUL, city::DUBAI, 500);
       g.addEdge(city::DUBAI, city::MUMBAI, 200);
       g.addEdge(city::ISTANBUL, city::SEATTLE, 1500);
       g.addEdge(city::DUBAI, city::SINGAPORE, 500);
       g.addEdge(city::MOSCOW, city::SEATTLE, 1000);
       g.addEdge(city::MUMBAI, city::SINGAPORE, 300);
       g.addEdge(city::SEATTLE, city::SINGAPORE, 700);
       g.addEdge(city::SEATTLE, city::LONDON, 1800);
       g.removeEdge(city::SEATTLE, city::LONDON);
       return 0;
   }

   在执行这个程序时，我们应该得到以下输出:

   ADD: LONDON-MOSCOW=900
   ADD: LONDON-ISTANBUL=500
   ADD: LONDON-DUBAI=1000
   ADD: ISTANBUL-MOSCOW=1000
   ADD: ISTANBUL-DUBAI=500
   ADD: DUBAI-MUMBAI=200
   ADD: ISTANBUL-SEATTLE=1500
   ADD: DUBAI-SINGAPORE=500
   ADD: MOSCOW-SEATTLE=1000
   ADD: MUMBAI-SINGAPORE=300
   ADD: SEATTLE-SINGAPORE=700
   ADD: SEATTLE-LONDON=1800
   REMOVE: SEATTLE-LONDON

由于我们为每个节点存储了一个相邻节点列表，因此这种方法被称为邻接表。这个方法也使用一个向量的一个向量来存储数据，就像前面的方法一样。但是内向量的维数不等于节点数；相反，它取决于边的数量。根据我们的addEdge函数，对于图中的每条边，我们将有两个条目。这种表示所需的内存与 E 成正比，其中 E 是边数。

到目前为止，我们只看到了如何构建一个图表。我们需要遍历一个图，以便能够在使用它时执行任何操作。有两种广泛使用的方法——广度优先搜索(BFS)和深度优先搜索(DFS)，我们将在第 6 章、图算法 I 中讨论这两种方法。

总结

在这一章中，我们研究了与前一章相比更高级的一类问题，这有助于我们描述更广泛的现实场景。我们研究并实现了两种主要的数据结构——树和图。我们还研究了在不同情况下可以使用的各种类型的树。然后，我们研究了以编程方式为这些结构表示数据的不同方式。在本章的帮助下，您应该能够应用这些技术来解决类似的现实问题。

现在我们已经了解了线性和非线性数据结构，在下一章中，我们将了解一个非常具体但广泛使用的概念，称为查找，其目标是将值存储在容器中，以便搜索速度超快。我们还将研究散列背后的基本思想，以及如何实现这样一个容器。