ความลึกของโหนดระดับคี่ที่ลึกที่สุดใน Binary Tree ใน C ++?

ให้เรากำหนดโครงสร้างที่จะเป็นตัวแทนของโหนดต้นไม้ที่มีคีย์ int และโหนดลูกของโหนดซ้ายและขวา หากนี่เป็นโหนดแรกที่สร้างขึ้น แสดงว่าเป็นโหนดรูท มิฉะนั้นจะเป็นโหนดย่อย

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

ต่อไป เราสร้างฟังก์ชัน createNode(int key) ที่ใช้ค่าคีย์ int และกำหนดให้กับสมาชิกคีย์ของโหนด ฟังก์ชันจะส่งกลับตัวชี้ไปยังโหนดโครงสร้างที่สร้างขึ้น นอกจากนี้ ลูกซ้ายและขวาของโหนดที่สร้างขึ้นใหม่จะถูกตั้งค่าเป็นโมฆะ

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

ต่อไป เรามีฟังก์ชัน isLeaf(Node *currentNode) ที่รับโหนดและตรวจสอบว่าโหนดมีลูกหรือไม่ คืนค่าจริงหรือเท็จโดยอิงหากโหนดนั้นเป็นโหนดปลายสุดหรือไม่

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

deepestOddLvlDepth(Node *currentNode, int currentLevel=0) รับ currentNode และ currentLevel ระดับปัจจุบันมีค่าเริ่มต้นเป็น 0 หากไม่มีค่าที่ส่งไป หาก currentNode เป็นโมฆะ ฟังก์ชันจะคืนค่า 0

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

ระดับปัจจุบันจะเพิ่มขึ้น 1 ในแต่ละระดับการเรียกซ้ำจนกว่าจะตรงตามเงื่อนไขพื้นฐาน จากนั้นเราจะตรวจสอบว่าโหนดปัจจุบันเป็นโหนดปลายสุดคี่หรือไม่ จากนั้นลูกซ้ายและขวาจะถูกสำรวจจนกว่าเราจะพบความลึกของโหนดลีฟในระดับคี่ที่ลึกที่สุด ความลึกสูงสุดของ leftChildDepth และ rightChild จะถูกส่งกลับไปยังฟังก์ชันหลักสำหรับการพิมพ์ผลลัพธ์

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

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อค้นหาความลึกของโหนดระดับคี่ที่ลึกที่สุดในไบนารีทรี

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

ผลลัพธ์

รหัสด้านบนจะสร้างผลลัพธ์ต่อไปนี้

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