数据结构
网络
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+ 浏览量
广告