Làm thế nào để bạn tìm thấy chiều cao của cây nhị phân trong python?

Ghi chú. Chiều cao của cây nhị phân trống là -1 và chiều cao của cây nhị phân chỉ có một nút là 0

Tham khảo phần Ví dụ và Giải thích ví dụ để biết thêm chi tiết và phần Cách tiếp cận để hiểu cách tìm chiều cao của cây nhị phân

Thí dụ

Thí dụ. 1

Cây nhị phân đã cho [đầu vào] là. [5,3,6,2,4][ 5, 3, 6, 2, 4 ][5,3,6,2,4]

Cây hình thành là

      5
     / \
    3   6
   / \
  2   4
đầu ra

  

The height of binary tree is: 3.
Thí dụ. 2
Cây nhị phân đã cho [đầu vào] là. [15,10,20,8,12,16,25,9][ 15, 10, 20, 8, 12, 16, 25, 9 ][15,10,20,8,12,16,25,9 
Cây hình thành là
       15
     /    \
    10     20
   / \     / \
  8  12   16  25
  \
   9
đầu ra
The height of binary tree is: 4.

Giải thích ví dụ

Trước khi đi vào giải thích ví dụ và cách tìm chiều cao của cây nhị phân, trước tiên chúng ta hãy giới thiệu sơ qua về cây nhị phân và chiều cao của cây nhị phân

Cây nhị phân có thể được định nghĩa là một tập hợp các đối tượng hoặc phần tử hoặc thực thể được gọi là nút. Các nút này được liên kết với nhau để thể hiện một hệ thống phân cấp. Nút trên cùng của hệ thống phân cấp được gọi là nút gốc. Mỗi nút của cây nhị phân chứa một số dữ liệu và nó có thể có nhiều nhất hai nút con. Nút gốc không bao giờ có nút cha. Các nút không có nút con gọi là nút lá

Thí dụ

Bây giờ, chiều cao của cây nhị phân nhiều hơn số cạnh lớn nhất trong đường dẫn từ nút gốc đến nút lá cấp thấp nhất là một

Nói cách khác, chúng ta có thể nói rằng chiều cao của cây nhị phân là chiều cao của nút gốc trong toàn bộ cây nhị phân

trong ví dụ

      5
     / \
    3   6
   / \
  2   4
Nút gốc là 555 và nút lá cấp thấp nhất là 222 và 444. Bây giờ, trong ví dụ trên, chúng ta có cạnh đầu tiên từ 555 đến 333 và cạnh thứ hai từ 333 đến 222. Vì vậy, chiều cao của cây nhị phân là 333 [một số cạnh + 1]

Hạn chế

• 1right = addNode[5]; cout rightHeight]: return leftHeight+1 else: return rightHeight+1 if __name__ == "__main__": root = Node[1] root.left = Node[2] root.right = Node[3] root.left.left = Node[4] root.left.right = Node[5] print["The height of binary tree is: ", findHeight[root]]

  đầu ra

  The height of binary tree is: 3.
  Trong cách tiếp cận đệ quy để tìm chiều cao của cây nhị phân, chúng ta duyệt qua tất cả các nút của cây nhị phân. Vì vậy, độ phức tạp thời gian của thuật toán là O[n]O[n]O[n], trong đó n là số nút trong cây nhị phân
  Độ phức tạp không gian
  Trong đoạn mã trên, chúng tôi không sử dụng bất kỳ khoảng trống thừa nào nhưng có các lệnh gọi đệ quy của hàm findHeight[]. Vì vậy, độ phức tạp của không gian cũng là O[n]O[n]O[n]
  
    
  
  

Cách tiếp cận 2. Tìm kiếm đầu tiên trên bánh mì [BFS] hoặc Truyền tải thứ tự cấp độ của cây nhị phân

Một cách tiếp cận khác để tìm chiều cao của cây nhị phân là thực hiện Tìm kiếm đầu tiên trên bánh mì [BFS] hoặc duyệt theo thứ tự cấp độ của cây nhị phân. Chúng tôi sẽ tiếp tục tăng chiều cao khi chúng tôi tiến lên cấp độ tiếp theo. Để thực hiện duyệt thứ tự cấp độ, chúng ta cần sử dụng cấu trúc dữ liệu hàng đợi

Ý tưởng khá đơn giản, chúng ta sẽ lấy một hàng đợi và chèn nút gốc vào đó và khởi tạo một biến chiều cao. Bây giờ, chúng tôi sẽ xóa một nút khỏi hàng đợi [dequeue] và khám phá nút con bên trái và bên phải của nó, sau khi khám phá, chúng tôi sẽ tăng bộ đếm chiều cao lên một nút vì mỗi lần khám phá biểu thị rằng cấp độ hiện tại đã hoàn thành và chúng tôi nên chuyển sang cấp độ tiếp theo

Ghi chú. Cách tìm chiều cao của cây nhị phân theo thứ tự cấp độ còn được gọi là cách lặp

Tham khảo mã giả được cung cấp bên dưới để hiểu rõ hơn

thuật toán

Mã giả cho cùng

1. Khởi tạo hàng đợi và biến chiều cao
2. Chèn nút gốc vào hàng đợi
3. Xóa tất cả các nút hiện có trong hàng đợi
4. Thêm tất cả các nút con i. e. con trái hoặc phải [nếu có] và tăng bộ đếm chiều cao lên 1
5. Sau khi tất cả các nút được khám phá [i. e. hàng đợi trở nên trống], kết quả trả về chiều cao

Triển khai mã

Hãy để chúng tôi triển khai mã giống nhau bằng các ngôn ngữ khác nhau

Mã C++

#include 
using namespace std;

/*
Defining a class to store a node of the binary tree. The node of the binary tree consists of data as well as left and right pointer which points to its left and right child.
*/
class Node {
public:
   int data;
   Node *left;
   Node *right;
};

/*
A function that finds the height of the binary tree by maximum height between the left and right subtree.
*/
int findHeight[Node *root] {
   // Initialize a queue and a height variable.
   int height = 0;

   queue q;

   // Insert the root node into the queue and a null to mark last
   q.push[root];
   q.push[NULL];

   // running the discussed steps until the queue becomes empty
   while [!q.empty[]] {
      // removing the node from the queue.
      Node *temp = q.front[];
      q.pop[];

      // if NULL is encountered, increment the height counter.
      if [temp == NULL]
         height++;

      // if NULL is not encountered, explore left and right child
      if [temp != NULL] {
         if [temp->left]
            q.push[temp->left];

         if [temp->right]
            q.push[temp->right];
      }
      else if [!q.empty[]]
         q.push[NULL];
   }
   return height;
}

/* A function that will add nodes to the binary tree. Its left and the right pointer will initially point to NULL as there is no child currently.
 */
Node *addNode[int data] {
   Node *newNode = new Node[];
   newNode->data = data;
   newNode->left = NULL;
   newNode->right = NULL;

   return newNode;
}

// main function
int main[] {
   // creating object of the Node class.
   Node *root = addNode[1];

   root->left = addNode[2];
   root->right = addNode[3];
   root->left->left = addNode[4];
   root->left->right = addNode[5];

   cout