原文:
给定一棵二叉树和一个键，编写一个函数，打印给定二叉树中键的所有祖先。 例如，如果给定的树跟在二叉树后面，键是 7，那么你的函数应该打印 4、2 和 1。
1
/ \
2 3
/ \
4 5
/
7
感谢 mike、sambasiva 和 wgpshashank 的贡献。
c
// c program to print ancestors of given node
#include
using namespace std;
/* a binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};
/* if target is present in tree, then prints the ancestors
and returns true, otherwise returns false. */
bool printancestors(struct node *root, int target)
{
/* base cases */
if (root == null)
return false;
if (root->data == target)
return true;
/* if target is present in either left or right subtree of this node,
then print this node */
if ( printancestors(root->left, target) ||
printancestors(root->right, target) )
{
cout << root->data << " ";
return true;
}
/* else return false */
return false;
}
/* helper function that allocates a new node with the
given data and null left and right pointers. */
struct node* newnode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = null;
node->right = null;
return(node);
}
/* driver program to test above functions*/
int main()
{
/* construct the following binary tree
1
/ \
2 3
/ \
4 5
/
7
*/
struct node *root = newnode(1);
root->left = newnode(2);
root->right = newnode(3);
root->left->left = newnode(4);
root->left->right = newnode(5);
root->left->left->left = newnode(7);
printancestors(root, 7);
getchar();
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java program to print ancestors of given node
/* a binary tree node has data, pointer to left child
and a pointer to right child */
class node
{
int data;
node left, right, nextright;
node(int item)
{
data = item;
left = right = nextright = null;
}
}
class binarytree
{
node root;
/* if target is present in tree, then prints the ancestors
and returns true, otherwise returns false. */
boolean printancestors(node node, int target)
{
/* base cases */
if (node == null)
return false;
if (node.data == target)
return true;
/* if target is present in either left or right subtree
of this node, then print this node */
if (printancestors(node.left, target)
|| printancestors(node.right, target))
{
system.out.print(node.data " ");
return true;
}
/* else return false */
return false;
}
/* driver program to test above functions */
public static void main(string args[])
{
binarytree tree = new binarytree();
/* construct the following binary tree
1
/ \
2 3
/ \
4 5
/
7
*/
tree.root = new node(1);
tree.root.left = new node(2);
tree.root.right = new node(3);
tree.root.left.left = new node(4);
tree.root.left.right = new node(5);
tree.root.left.left.left = new node(7);
tree.printancestors(tree.root, 7);
}
}
// this code has been contributed by mayank jaiswal
计算机编程语言
# python program to print ancestors of given node in
# binary tree
# a binary tree node
class node:
# constructor to create a new node
def __init__(self, data):
self.data = data
self.left = none
self.right = none
# if target is present in tree, then prints the ancestors
# and returns true, otherwise returns false
def printancestors(root, target):
# base case
if root == none:
return false
if root.data == target:
return true
# if target is present in either left or right subtree
# of this node, then print this node
if (printancestors(root.left, target) or
printancestors(root.right, target)):
print root.data,
return true
# else return false
return false
# driver program to test above function
root = node(1)
root.left = node(2)
root.right = node(3)
root.left.left = node(4)
root.left.right = node(5)
root.left.left.left = node(7)
printancestors(root, 7)
# this code is contributed by nikhil kumar singh(nickzuck_007)
c
using system;
// c# program to print ancestors of given node
/* a binary tree node has data, pointer to left child
and a pointer to right child */
public class node
{
public int data;
public node left, right, nextright;
public node(int item)
{
data = item;
left = right = nextright = null;
}
}
public class binarytree
{
public node root;
/* if target is present in tree, then prints the ancestors
and returns true, otherwise returns false. */
public virtual bool printancestors(node node, int target)
{
/* base cases */
if (node == null)
{
return false;
}
if (node.data == target)
{
return true;
}
/* if target is present in either left or right subtree
of this node, then print this node */
if (printancestors(node.left, target)
|| printancestors(node.right, target))
{
console.write(node.data " ");
return true;
}
/* else return false */
return false;
}
/* driver program to test above functions */
public static void main(string[] args)
{
binarytree tree = new binarytree();
/* construct the following binary tree
1
/ \
2 3
/ \
4 5
/
7
*/
tree.root = new node(1);
tree.root.left = new node(2);
tree.root.right = new node(3);
tree.root.left.left = new node(4);
tree.root.left.right = new node(5);
tree.root.left.left.left = new node(7);
tree.printancestors(tree.root, 7);
}
}
// this code is contributed by shrikant13
java 描述语言
输出:
4 2 1
时间复杂度: o(n)，其中 n 是给定二叉树中的节点数。
如果你发现任何不正确的地方，或者你想分享更多关于上面讨论的话题的信息，请写评论。
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
