資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時裝研究
法律研究用 C++ 列印二叉樹中給定節點的祖先
在這個問題中，我們給定了一個二叉樹，我們必須列印其在二叉樹中的某個節點的祖先。
二叉樹是一種特殊樹，其每個節點最多有兩個子節點。因此，每個節點要麼是葉節點，要麼有一個或兩個子節點。
例如，
二叉樹中某個節點的祖先是在給定節點上層的某個節點。
讓我們舉一個祖先節點的示例 −
此二叉樹中值為 3 的節點的祖先是 8,
要解決這個問題，我們將從根節點遍歷到目標節點。在二叉樹中逐層向下。並且在路徑中打印出現的所有的節點。
示例
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
struct node{
int data;
struct node* left;
struct node* right;
};
bool AncestorsNodes(struct node *root, int target){
if (root == NULL)
return false;
if (root->data == target)
return true;
if ( AncestorsNodes(root->left, target) || AncestorsNodes(root->right, target) ){
cout << root->data << " ";
return true;
}
return false;
}
struct node* insertNode(int data){
struct node* node = (struct node*) malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
int main(){
struct node *root = insertNode(10);
root->left = insertNode(6);
root->right = insertNode(13);
root->left->left = insertNode(3);
root->left->right = insertNode(8);
root->right->left = insertNode(12);
cout<<"Ancestor Nodes are " ;
AncestorsNodes(root, 8);
getchar();
return 0;
}輸出
Ancestor Nodes are 6 10
更新於： 03-Jan-2020
2K+ 瀏覽量
廣告