Đường kính của cây nhị phân trong O (n) [Một phương thức mới] trong C ++?

Đường kính của cây nhị phân là (left_height + right_height + 1) cho mỗi nút. Vì vậy, trong phương pháp này, chúng tôi sẽ tính toán (left_height + right_height + 1) cho mỗi nút và cập nhật kết quả. Độ phức tạp thời gian ở đây vẫn là O (n).

Đầ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 hàm newNode (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* newNode = new Node;
   newNode->data = data;
   newNode->leftChild = newNode->rightChild = NULL;
   return (newNode);
}

Hàm đường kính (Node * root) lấy nút gốc và kiểm tra xem nút gốc có rỗng hay không. Sau đó, chúng tôi xác định biến ans với giá trị INT_MIN. Giá trị trả về từ height (root, ans) được lưu trữ vào biến height_of_tree. Các ans được trả về từ hàm.

int diameter(Node* root){
    if (root == NULL)
        return 0;
    int ans = INT_MIN;
    int height_of_tree = height(root, ans);
    return ans;
}

Hàm height (Node * root, int &ans) lấy nút gốc và biến ans theo tham chiếu. Sau đó, chúng tôi thực hiện duyệt inorder trên cây để tính toán độ dài từng cây con của nó và giá trị maxValue của ans được truyền dưới dạng tham số thứ hai trên mỗi lần gọi đệ quy. Ans là giá trị tối đa của (ans, 1 + left_height + right_height).

Ví dụ

Chúng ta hãy xem cách triển khai sau để tìm đường kính của cây nhị phân trong phương pháp O (n).

#include <iostream>
using namespace std;
struct Node {
    int data;
    Node* leftChild, *rightChild;
};
struct Node* newNode(int data){
   struct Node* newNode = new Node;
   newNode->data = data;
   newNode->leftChild = newNode->rightChild = NULL;
   return (newNode);
}
int height(Node* root, int& ans){
   if (root == NULL)
      return 0;
   int left_height = height(root->left, ans);
   int right_height = height(root->right, ans);
   ans = max(ans, 1 + left_height + right_height);
   return 1 + max(left_height, right_height);
}
int diameter(Node* root){
   if (root == NULL)
      return 0;
   int ans = INT_MIN;
   int height_of_tree = height(root, ans);
   return ans;
}
int main(){
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    printf("Diameter is %d\n", diameter(root));
    return 0;
}

Đầu ra

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

Diameter is 4