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ế

• 1<=1 <=1<= Số nút <=105<= 10^5<=105
• 1<=1 <=1<= Dữ liệu của một nút <=105<= 10^5<=105

Trong một số bài toán, bạn có thể thấy số ca kiểm thử được biểu thị bằng t. Vì vậy, chúng ta chỉ cần gọi hàm findHeight() t -times

Cách tiếp cận 1. Sử dụng đệ quy

Chúng ta có thể dễ dàng tính toán chiều cao của cây nhị phân bằng cách sử dụng đệ quy. Ý tưởng rất đơn giản, chúng ta sẽ tính chiều cao của level hiện tại, và gọi đệ quy hàm findHeight() cho cây con bên trái và cây con bên phải (nếu chúng tồn tại)

Bây giờ, chiều cao của mức hiện tại sẽ là chiều cao tối đa của cây con bên trái và chiều cao của cây con bên phải. Vì vậy, hàm đệ quy sẽ cung cấp chiều cao của cây con bên trái và cây con bên phải và chúng ta sẽ gán chiều cao của nút hiện tại là chiều cao lớn nhất của chúng

Chúng tôi đệ quy cây con trái và cây con phải vì một nút có thể có con trái hoặc con phải hoặc cả hai. Tham khảo mã giả để hiểu rõ hơn về thuật toán đệ quy tìm chiều cao của cây nhị phân

thuật toán

Mã giả cho cùng

1. Kiểm tra trường hợp cơ sở
   • Nếu cây trống, trả về -1 vì chúng ta không thể tìm thấy chiều cao của cây
   • Khác, tiếp tục các bước tiếp theo
2. Gọi hàm findHeight(root) cho cây con bên trái và lưu trữ kết quả
3. Gọi hàm findHeight(root) cho cây con bên phải và lưu trữ kết quả
4. Nhận tối đa của cả hai chiều cao và gán chiều cao là kết quả
   • chiều cao = max(left_height, right_height)
5. Trả về kết quả là (chiều cao + 1), vì chúng ta cũng cần thêm nút hiện tại vào tổng 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 the left and right pointer which points to its left and right child.
*/
class Node {
public:
   int data;
   Node *left;
   Node *right;
};

/*
A recursive function that finds the height of the binary tree by maximum height between the left and right subtree.
*/
int findHeight(Node *node) {
   // Base case: If the tree is empty, return -1 as we cannot find its height.
   if (node == NULL)
      return 0;
   else {
      /* Call the findHeight() function for the left and right sub tree and store the results.
       */
      int leftHeight = findHeight(node->left);
      int rightHeight = findHeight(node->right);

      // returning the (maximum + 1) as the height of the binary tree.
      if (leftHeight > rightHeight)
         return (leftHeight + 1);
      else
         return (rightHeight + 1);
   }
}

/* 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 << "The height of binary tree is: " << findHeight(root);
   return 0;
}
Mã Java
/*
Defining a class to store a node of the binary tree. The node of the binary tree consists of data as well as the left and right pointer which points to its left and right child.
*/
class Node {
    int data;
    Node left, right;
    /* The constructor 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(int item) {
        data = item;
        left = right = null;
    }
}

public class BinaryTree {
    // creating reference of the Node class.
    Node root;

    /*
    A recursive function that finds the height of the binary tree by maximum height between the left and right subtree.
    */
    int findHeight(Node node) {

        // Base case: If the tree is empty, return -1 as we cannot find its height.

        if (node == null)
            return 0;

        else {
            /* Call the findHeight() function for the left and right sub tree and store the results.
            */
            int leftHeight = findHeight(node.left);
            int rightHeight = findHeight(node.right);

            // returning the (maximum + 1) as the height of the binary tree.
            if (leftHeight > rightHeight)
                return (leftHeight + 1);
            else
                return (rightHeight + 1);
        }
    }

    public static void main(String[] args) {

        // creating object of the BinaryTree class.
        BinaryTree tree = new BinaryTree();

        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);

        System.out.println("The height of binary tree is: " +
                tree.findHeight(tree.root));
    }
}
Mã Python
"""
Defining a class to store a node of the binary tree. The node of the binary tree consists of data as well as the left and right pointer which points to its left and right child.

The constructor will add nodes to the binary tree. Its left and the right pointer will initially point to None as there is no child currently.
"""
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


"""
A recursive function that finds the height of the binary tree by maximum height between the left and right subtree.
"""
def findHeight(node):
    if node is None:
        return 0

    else:

        # Call the findHeight() function for the left and right sub tree and store the results.
        leftHeight = findHeight(node.left)
        rightHeight = findHeight(node.right)

        # returning the (maximum + 1) as the height of the binary tree
        if (leftHeight > 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 << "The height of binary tree is: " << findHeight(root);
   return 0;
}
Mã Java
The height of binary tree is: 3.
0
Mã Python
The height of binary tree is: 3.
1
đầu ra
The height of binary tree is: 3.
Trong cách tiếp cận lặp để 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 đang sử dụng thêm không gian làm hàng đợi. Vì vậy, độ phức tạp của không gian cũng là O(n)O(n)O(n) trong đó n là kích thước của hàng đợi hoặc số lượng nút (được chèn vào cấu trúc dữ liệu hàng đợi)

Sự kết luậ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

• 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

• Cách tiếp cận đệ quy để tìm chiều cao của cây nhị phân có thể tính toán chiều cao của mức hiện tại và gọi đệ quy hàm findHeight() cho cây con bên trái và cây con bên phải (nếu chúng tồn tại)

• Trong cách tiếp cận đệ quy để tìm chiều cao của cây nhị phân, độ 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. Trong cách tiếp cận đệ quy, chúng tôi đang sử dụng thêm không gian làm hàng đợi. Vì vậy, độ phức tạp của không gian cũng là O(n)O(n)O(n) trong đó n là kích thước của hàng đợi hoặc số lượng nút (được chèn vào cấu trúc dữ liệu hàng đợi)

  Chiều cao của cây nhị phân là bao nhiêu?

  Chiều cao của Cây nhị phân được định nghĩa là độ sâu tối đa của bất kỳ nút lá nào tính từ nút gốc . Đó là độ dài của đường đi dài nhất từ ​​nút gốc đến bất kỳ nút lá nào.

  Làm thế nào bạn có thể tìm thấy chiều cao của một cây hoàn chỉnh nhị phân?

  Tóm lại, trong một cây nhị phân đầy đủ có n nút. chiều cao là h = log2(n + 1) , i. e. h là O(log n) • số lá là lh = (n + 1)/2, i. e. khoảng một nửa số nút nằm ở lá. cây nhị phân hoàn chỉnh. )

  Chiều cao của một nút trong cây nhị phân là bao nhiêu?

  Chiều cao của nút là số cạnh từ nút đến lá sâu nhất . Chiều cao của cây bằng chiều cao của gốc. Cây nhị phân đầy đủ. là một cây nhị phân trong đó mỗi nút có chính xác 0 hoặc 2 nút con.