資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告