在本教程中，我们将看到如何进行垂直顺序遍历。
问题陈述：
为您提供了树的根国彩网，您需要在垂直遍历它们时打印这些国彩网。
考虑下面给出的树：
垂直顺序遍历可以如下所示：
因此，垂直顺序遍历将为：
d
b
f
c
g
那么我们如何得出这个结果呢？
我们可以借助以下方法得出结果：
- 地图
- 水平距离
- 级别顺序遍历
我们将看到这三者如何参与解决。
首先如何计算水平距离？
我们可以通过以下步骤计算水平距离：
- 对于根国彩网，水平距离= 0。
- 对于左国彩网，水平距离=父水平距离– 1
- 对于右国彩网，水平距离=父水平距离+ 1
现在，让我们计算所有国彩网的水平距离。
由于“ a”是根国彩网，因此距离为0。
b = 0– 1 = -1
d = -1– 1 = -2
c = 0 + 1 = 1
g = 1 + 1 = 2
e = -1 + 1 = 0
f = 1– 1 = 0
最后，水平距离将如下所示：
现在，在哈希图中，根据升序对水平距离值进行排序。然后根据国彩网的“水平距离[HD]”值插入国彩网。
哈希图如下所示：
现在出现一个问题。为什么我们按此顺序插入“ a，e，f”？
我们在级别顺序遍历的帮助下添加了它。当我们进行级别顺序遍历时，我们将获得该顺序的那三个国彩网。
我们得到了结果。
C ++解决方案
#include <iostream>
#include <vector>
#include <map>
using namespace std;
// structure to hold binary tree node
struct Node
{
int data;
Node *left, *right;
Node(int data)
{
this->data = data;
this->left = this->right = nullptr;
}
};
void perform_vertical_order_traversal(Node *root, map<int,vector<int>>& map, int h_dist)
{
// Base case
if (root == NULL)
return;
map[h_dist].push_back(root -> data);
perform_vertical_order_traversal(root -> left, map, h_dist - 1);
perform_vertical_order_traversal(root -> right, map, h_dist + 1);
}
int main()
{
Node* root = nullptr;
/* Binary tree:
16
/ \
/ \
10 25
/ \ / \
/ \ / \
7 15 18 30
*/
root = new Node(16);
root->left = new Node(10);
root->right = new Node(25);
root->left->left = new Node(7);
root->left->right = new Node(15);
root->right->left = new Node(18);
root->right->right = new Node(30);
map<int,vector<int>> myMap;
perform_vertical_order_traversal(root, myMap, 0);
cout<<"The vertical order traversal is"<< endl;
for (auto it = myMap.begin(); it != myMap.end(); ++it)
{
for (int i=0; i< it->second.size(); ++i)
cout << it->second[i] << " ";
cout << endl; }
return 0;
}
输出：
7 10 16 15 18 25 30
该网站上可用的教程列表：
| C编程20+章 | C ++编程80+章 |
| 100多个编码问题 | 数据结构和算法85+章 |
| 系统设计20+章 | Shell脚本编写12章 |
| 4g LTE 60+章节 | 最常见的编码问题 |
| 5G NR 50+章 | Linux系统编程20+章 |
