C++ 中二叉树的对角遍历?
c++server side programmingprogramming
考虑在斜率为 -1 的线之间穿过的节点。二叉树的对角遍历将遍历并打印这些线之间的所有节点。
让我们首先定义一个结构，该结构表示包含数据及其左节点和右节点子节点的树节点。如果这是要创建的第一个节点，则它是根节点，否则是子节点。
struct Node {
int data;
struct Node *leftChild, *rightChild;
};
接下来，我们创建 createNode(int data) 函数，该函数接受一个 int 值并将其分配给节点的数据成员。该函数返回指向创建的结构 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, intdepth, map<int, vector<int>> &myMap) 函数接受根节点、当前深度和一个以 int 值作为键并以 int 向量作为值的映射。我们将 myMap 作为引用传递给此函数。然后，该函数检查根是否为空，如果不是，则在执行中序遍历时，将元素 root->data 推送到当前深度的向量数据结构的后面。
void traverseDiagonal(Node* root, intdepth, 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);
接下来，在我们的主函数中，我们使用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
