資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究用 C++ 查詢二叉樹先序遍歷中的第 n 個節點
在這個問題中，我們給定一個二叉樹和一個整數 N。任務是找到二叉樹先序遍歷中的第 n 個節點。
一個二叉樹有一個特殊條件，即每個節點最多可以有兩個子節點。
遍歷是一個訪問樹的所有節點的過程，也可能列印它們的值。
讓我們來看一個例子來理解這個問題：
輸入
N = 6
輸出
6
解釋
Pre order traversal of tree : 1, 2, 4, 5, 3, 6, 7
解決方案方法
其思想是使用二叉樹的先序遍歷，該遍歷是透過遞迴呼叫完成的。在每次呼叫中，我們將訪問根節點，然後首先為左子樹呼叫 preOrder()，然後呼叫 preOrder()。在這個遍歷過程中，我們將計數節點數，並列印計數為 N 的節點。
程式說明了我們解決方案的工作原理：
示例
#include <iostream>
using namespace std;
struct Node {
int data;
Node *left, *right;
};
struct Node* createNode(int item){
Node* temp = new Node;
temp->data = item;
temp->left = NULL;
temp->right = NULL;
return temp;
}
void findPreOrderTraversalRec(struct Node* root, int N){
static int nodeCount = 0;
if (root == NULL)
return;
if (nodeCount <= N) {
nodeCount++;
if (nodeCount == N)
cout << root->data;
findPreOrderTraversalRec(root->left, N);
findPreOrderTraversalRec(root->right, N);
}
}
int main() {
struct Node* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right->left = createNode(6);
root->right->right = createNode(7);
int N = 6;
cout<<N<<"th node in preorder traversal is ";
findPreOrderTraversalRec(root, N);
return 0;
}輸出
6th node in preorder traversal is 6
更新於：2021年3月13日
209 次瀏覽
廣告