資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
廣告