数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++实现二叉树的对角线遍历？
考虑斜率为-1的直线之间的节点。二叉树的对角线遍历就是遍历并打印这些直线之间的所有节点。
首先，让我们定义一个结构体来表示树节点，其中包含数据及其左右子节点。如果这是创建的第一个节点，则它是根节点，否则是子节点。
struct Node {
int data;
struct Node *leftChild, *rightChild;
};接下来，我们创建`createNode(int data)`函数，它接受一个整数值并将其赋值给节点的数据成员。该函数返回指向已创建的`Node`结构体的指针。此外，新创建节点的左右子节点都设置为null。
struct Node* newNode(int data){
struct Node* node = new Node();
node->data = data;
node->leftChild = node->rightChild = NULL;
return node;
}`traverseDiagonal(Node* root, int depth, map<int, vector<int>> &myMap)`函数接受我们的根节点、当前深度和一个映射（键为整数值，值为整数值向量）。我们将`myMap`作为引用传递给此函数。然后，该函数检查根节点是否为空，如果不为空，则在执行中序遍历时，我们将元素`root->data`推送到当前深度处的向量数据结构的末尾。
void traverseDiagonal(Node* root, int depth, map<int, vector<int>> &m){
if(root){
m[depth].push_back(root->data);然后，我们对树进行递归中序遍历，跟踪对角线距离，并在遍历树的左子节点时将深度加1。在遍历树的右子节点时，我们不向深度添加任何值。
traverseDiagonal(root->leftChild, depth+1, myMap); traverseDiagonal(root->rightChild, depth, myMap);
接下来，在我们的`main`函数中，我们使用`createNode(data)`函数创建树。
Node *root = createNode(10); root->leftChild = createNode(5); root->rightChild = createNode(15); root->leftChild->leftChild = createNode(4); root->leftChild->rightChild = createNode(6); root->rightChild->rightChild = createNode(17); root->rightChild->rightChild->leftChild = createNode(16);
然后，我们声明一个映射`myMap`，其中键为int，值为int的向量。然后将此映射与根节点和当前深度一起传递给`traverseDiagonal`。
map<int, vector<int>> myMap; traverseDiagonal(root, 0, myMap);
在`myMap`映射填充值之后，我们使用基于范围的for循环对其进行迭代，并打印这些对角线值。
for(auto k: myMap){
for(auto Nodes: k.second)
cout<<Nodes<<" ";
cout<<endl;
}示例
让我们看一下以下实现，以查找二叉树的对角线遍历。
#include <iostream>
#include <map>
#include <vector>
using namespace std;
struct Node{
int data;
Node *leftChild, *rightChild;
};
Node* createNode(int data){
Node* node = new Node();
node->data = data;
node->leftChild = node->rightChild = NULL;
return node;
}
void traverseDiagonal(Node* root, int depth, map<int, vector<int>> &myMap){
if(root){
m[depth].push_back(root->data);
traverseDiagonal(root->leftChild, depth+1, myMap);
traverseDiagonal(root->rightChild, depth, myMap);
}
}
int main(){
Node *root = createNode(10);
root->leftChild = createNode(5);
root->rightChild = createNode(15);
root->leftChild->leftChild = createNode(4);
root->leftChild->rightChild = createNode(6);
root->rightChild->rightChild = createNode(17);
root->rightChild->rightChild->leftChild = createNode(16);
map<int, vector<int>> myMap;
traverseDiagonal(root, 0, myMap);
for(auto k: myMap){
for(auto Nodes: k.second)
cout<<Nodes<<" ";
cout<<endl;
}
}输出
以上代码将产生以下输出：
10 15 17 5 6 16 4
更新于：2021年1月16日
171 次浏览
广告