C ++中二叉树的对角遍历？

Z时代
2024-01-10
分类：综合

考虑在坡度-1的线之间通过的节点。二叉树的对角线遍历将遍历并打印这些行之间存在的所有那些节点。

让我们首先定义一个结构，该结构将表示一个包含数据及其左节点和右节点子节点的树节点。如果这是要创建的第一个节点，则它是根节点，否则是子节点。

struct Node {
   int data;
   struct Node *leftChild, *rightChild;
};

接下来我们创建我们的 createNode(int data)该函数接受一个int值并将其分配给该节点的数据成员。该函数将指针返回到创建的结构节点。同样，新创建的节点的左和右子级设置为null。

struct Node* newNode(int data){
   struct Node* node = new Node();
   node->data = data;
   node->leftChild = node->rightChild = NULL;
   return node;
}

traverseDiagonal（Node *根，int深度，map <int，vector <int >>＆myMap）函数将我们的根节点，当前深度以及以int值作为键并将int的向量作为值的映射。我们将myMap作为对此函数的引用。然后该函数检查root是否为null，如果不是，则在执行顺序遍历时，将元素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);

接下来，在主要功能中，我们使用 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(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;
   }
}