数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++中二叉树最深奇数层节点的深度？
让我们首先定义一个结构体，该结构体将表示一个树节点，其中包含 int 类型的键值以及其左子节点和右子节点。如果这是第一个创建的节点，则它是根节点，否则是子节点。
struct Node {
int data;
struct Node *leftChild, *rightChild;
};接下来，我们创建 createNode(int key) 函数，该函数接收一个 int 类型的键值并将其赋值给节点的 key 成员。该函数返回指向已创建的 struct Node 的指针。此外，新创建节点的左子节点和右子节点都设置为 null。
Node* createNode(int data){
Node* node = new Node;
node->data = data;
node->leftChild = node->rightChild = NULL;
return node;
}接下来，我们有 isLeaf(Node *currentNode) 函数，该函数接收一个节点并检查它是否具有任何子节点。它根据节点是否是叶子节点返回 true 或 false。
bool isLeaf(Node *currentNode){
return (currentNode->leftChild == NULL &&
currentNode->rightChild == NULL);
}deepestOddLvlDepth(Node *currentNode, int currentLevel=0) 函数接收 currentNode 和 currentLevel。如果未向其传递值，则 currentLevel 的默认值为 0。如果 currentNode 为 null，则函数返回 0。
int deepestOddLvlDepth(Node *currentNode, int currentLevel=0){
if ( currentNode == NULL)
return 0;在每次递归级别上，currentLevel 都会递增 1，直到满足基本条件。然后，我们检查 currentNode 是否是奇数层的叶子节点。然后遍历左子节点和右子节点，直到找到我们最深奇数层叶子节点的深度。左子节点深度和右子节点深度的最大值将返回到主函数以打印结果。
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
更新于: 2021年1月16日
84 次查看
广告