Độ sâu của nút cấp lẻ sâu nhất trong Cây nhị phân trong C ++?

Đầ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 có chứa khóa int 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 ta tạo hàm createNode (int key) lấy giá trị khóa int và gán nó cho thành viên chính 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.

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

Tiếp theo, chúng ta có hàm isLeaf (Node * currentNode) lấy một nút và kiểm tra xem nó có con nào hay không. Nó trả về true hoặc false dựa trên nếu nút có phải là nút lá hay không.

bool isLeaf(Node *currentNode){
   return (currentNode->leftChild == NULL &&
   currentNode->rightChild == NULL);
}

DeepOddLvlDepth (Node * currentNode, int currentLevel =0) lấy currentNode và currentLevel. CurrentLevel có giá trị mặc định là 0 nếu không có giá trị nào được chuyển cho nó. Nếu currentNode là null thì hàm trả về 0.

int deepestOddLvlDepth(Node *currentNode, int currentLevel=0){
   if ( currentNode == NULL)
      return 0;

Mức currentLevel được tăng thêm 1 ở mỗi mức đệ quy cho đến khi điều kiện cơ bản được đáp ứng. Sau đó, chúng tôi kiểm tra xem currentNode có phải là một nút lá lẻ hay không. Sau đó, left và rightChild được đi ngang cho đến khi chúng ta tìm thấy độ sâu nút lá cấp lẻ sâu nhất của mình. Độ sâu tối đa của leftChildDepth và rightChild được trả về hàm chính để in kết quả.

int deepestOddLvlDepth(Node *currentNode, int currentLevel=0){
   if ( currentNode == NULL)
      return 0;
      currentLevel ++;
   if ( currentLevel % 2 != 0 && isLeaf(currentNode))
      return currentLevel;
   int leftChildLevel = deepestOddLvlDepth(currentNode->leftChild,currentLevel);
   int rightChildLevel = deepestOddLvlDepth(currentNode->rightChild,currentLevel);
   return max(leftChildLevel,rightChildLevel);
}

Ví dụ

Chúng ta hãy xem cách triển khai sau để tìm độ sâu nút cấp lẻ sâu nhất trong cây nhị phân.

#include<iostream>
using namespace std;
struct Node{
   int key;
   struct Node *leftChild, *rightChild;
};
Node* createNode(int key){
   Node* node = new Node;
   node->key = key;
   node->leftChild = node->rightChild = NULL;
   return node;
}
bool isLeaf(Node *currentNode){
   return (currentNode->leftChild == NULL &&
   currentNode->rightChild == NULL);
}
int deepestOddLvlDepth(Node *currentNode, int currentLevel=0){
   if ( currentNode == NULL)
      return 0;
      currentLevel ++;
   if ( currentLevel % 2 != 0 && isLeaf(currentNode))
      return currentLevel;
      int leftChildLevel = deepestOddLvlDepth(currentNode->leftChild,currentLevel);
      int rightChildLevel = deepestOddLvlDepth(currentNode->rightChild,currentLevel);
      return max(leftChildLevel,rightChildLevel);
}
int main(){
   Node *root = createNode(15);
   root->leftChild = createNode(33);
   root->rightChild = createNode(18);
   root->rightChild->leftChild = createNode(19);
   root->rightChild->rightChild = createNode(20);
   root->rightChild->rightChild->leftChild = createNode(28);
   root->rightChild->rightChild->rightChild = createNode(29);
   cout << "The depth of the deepest odd level leaf node is: "<<deepestOddLvlDepth(root) << endl;
   return 0;
}

Đầu ra

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

The depth of the deepest odd level leaf node is: 3