Đường chéo của cây nhị phân trong C ++?

Để xem xét các nút đang đi qua giữa các đường có độ dốc -1. Đường chéo của cây nhị phân sẽ đi ngang và in ra tất cả các nút có mặt giữa các dòng này.

Đầu tiên chúng ta hãy xác định cấu trúc đại diện cho một nút cây chứa dữ liệu và nút con trái và phải của nó. Nếu đây là nút đầu tiên được tạo thì đó là nút gốc, ngược lại là nút con.

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

Tiếp theo, chúng tôi tạo ra hàm createNode (int data) của chúng tôi, nhận một giá trị int và gán nó cho thành viên dữ liệu của nút. Hàm trả về con trỏ tới struct Node đã tạo. Ngoài ra, nút con bên trái và bên phải của nút mới tạo được đặt thành null.

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

Hàm traverseDirical (Node * root, int depth, map > &myMap) lấy nút gốc của chúng ta, độ sâu hiện tại và một bản đồ có giá trị int làm khóa và vectơ int làm giá trị. Chúng tôi chuyển myMap làm tham chiếu đến chức năng này. Sau đó, hàm sẽ kiểm tra xem phần tử gốc có rỗng hay không và nếu không, thì chúng tôi đẩy dữ liệu phần tử root-> ở phía sau cấu trúc dữ liệu vectơ của chúng tôi ở độ sâu hiện tại khi chúng tôi thực hiện truyền tải nhỏ hơn.

void traverseDiagonal(Node* root, int depth, map<int, vector<int>> &m){
   if(root){
      m[depth].push_back(root->data);

Sau đó, chúng tôi thực hiện một trình duyệt đệ quy đệ quy của cây theo dõi khoảng cách đường chéo và thêm 1 vào độ sâu bất cứ khi nào chúng tôi đi qua phần con bên trái của cây. Chúng tôi không thêm bất cứ điều gì vào chiều sâu khi chúng tôi đi ngang qua phần con bên phải của cây.

traverseDiagonal(root->leftChild, depth+1, myMap);
traverseDiagonal(root->rightChild, depth, myMap);

Tiếp theo, trong hàm chính của chúng ta, chúng ta tạo cây bằng hàm 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);

Sau đó, chúng tôi khai báo một bản đồ myMap chứa int là khóa và vector của int là giá trị. Bản đồ này sau đó được chuyển tới traverseDirical cùng với nút gốc và độ sâu hiện tại.

map<int, vector<int>> myMap;
traverseDiagonal(root, 0, myMap);

Sau khi bản đồ myMap được điền đầy giá trị, chúng tôi lặp lại trên đó bằng cách sử dụng phạm vi dựa trên vòng lặp for và in các giá trị đường chéo đó.

for(auto k: myMap){
   for(auto Nodes: k.second)
      cout<<Nodes<<" ";
      cout<<endl;
}

Ví dụ

Chúng ta hãy xem cách triển khai sau để tìm đường chéo của cây nhị phân.

#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;
   }
}

Đầu ra

Đoạn mã trên sẽ tạo ra kết quả sau -

10 15 17
5 6 16
4