C ++中二叉树中最深的奇数级节点的深度？

2023-06-21 12:23:03 253

让我们首先定义表示包含int键及其左右节点子节点的树节点的结构。如果这是要创建的第一个节点，则它是根节点，否则是子节点。

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

接下来我们创建我们的createNode(intkey)函数，它接受一个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,intcurrentLevel=0)采用currentNode和currentLevel。如果没有值传递给currentLevel，则它的默认值为0。如果currentNode为null，则该函数返回0。

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

currentLevel在每个递归级别上递增1，直到满足基本条件。然后我们检查currentNode是否是奇数叶节点。然后遍历left和rightChild，直到找到最深的奇数级叶节点深度。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
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 << "最深奇数级叶节点的深度为： "<输出结果
上面的代码将产生以下输出。
最深奇数级叶节点的深度为： 3

C ++中二叉树中最深的奇数级节点的深度？

示例

热门推荐

随机推荐