二叉树祖先节点_二叉树的祖先

一时失言乱红尘 2023-03-05 09:55 11阅读 0赞

二叉树祖先节点

**Problem statement:**

**问题陈述：**

Given a Binary Tree and a target key, write a function that **prints all the ancestors of the key in the given binary tree**.

给定二叉树和目标键，编写一个函数，以**打印给定二叉树中键的所有祖先** 。

**Example:**

**例：**

Let's the tree be like following:

让树如下所示：

![Ancestors in Binary Tree][]

Let for node value 12:
        Ancestors are:
        7, 5, 8
        While for node value 7:
        Ancestors are:
        5, 8

**Solution**

**解**

**What is Ancestors?**

**什么是祖先？**

For any node **n**,  
Its ancestors are the nodes which are on the path between roots to node **n**

对于任何节点**n** ，  
它的祖先是位于根到节点**n**之间的路径上的节点

**Thus for the above examples,**

**因此，对于以上示例，**

**Example 1:**

**范例1：**

Node is 12 //represented by value
        Root to the node path is
        8->5->7->12
        Thus the ancestors are 7, 5, 8

**Example 2:**

**范例2：**

Node is 7 //represented by value
        Root to the node path is
        8->5->7
        Thus the ancestors are 5, 8

**Algorithm:**

**算法：**

FUNCTION printAncestors(Node *root, int target)
        IF(!root)
            return false;
        IF( (root->left && root->left->data==target) ||
            (root->right && root->right->data==target ) || 
            printAncestors(root->left,target)|| 
            printAncestors(root->right,target)){
                Print root->data;
                return true;
        END IF
        return false;
    END FUNCTION

That simply means we are doing kind of DFS

这仅表示我们正在执行某种DFS

For a **currentnode** to be ancestor of the target node the conditions are:

为了使**currentnode**成为目标节点的祖先，条件是：

1.  If the target node is its child node (either left child or right child)
        //condition
        IF((root->left && root->left->data==target) ||
        (root->right && root->right->data==target ))
    
    2.  If any of the two subtree of the current node contain ancestor of the target 
        node then the current node is also an ancestor. 
        //condition
        IF(printAncestors(root->left, target)|| 
        printAncestors(root->right, target))

**Example with explanation:**

**带有说明的示例：**

For target node 7:
    Root 8 is ancestor on condition: its left subtree contains ancestor 5
    5 is ancestor since target node is its right child
    Thus ancestors are:
    5, 8 //in order

**C++ Implementation:**

**C ++实现：**

#include <bits/stdc++.h>
    using namespace std;
    
    //tree node
    class Node{
         
    	public:
    	int data;
    	Node *left;
    	Node *right;
    };
    
    bool printAncestors(Node *root, int target)
    {
        
    	if(!root)
    	return false;
    
    	if(	(root->left && root->left->data==target) ||
    		(root->right && root->right->data==target ) || 
    		printAncestors(root->left,target)|| 
    		printAncestors(root->right,target)){
        
    		cout<<root->data<<" ";
    		return true;
    	}
    	return false;
    }
    
    //creating new nodes
    Node* newnode(int data){
          
    	Node* node = (Node*)malloc(sizeof(Node)); 
    	node->data = data; 
    	node->left = NULL; 
    	node->right = NULL; 
    	return(node); 
    } 
    
    int main() {
         
    	//**same tree is builted as shown in example**
    	cout<<"tree in the example is build here"<<endl;
    	//building the tree like as in the example
    	Node *root=newnode(8); 
    	root->left= newnode(5); 
    	root->right= newnode(4); 
    	root->right->right=newnode(11);
    	root->right->right->left=newnode(3);
    	root->left->left=newnode(9); 
    	root->left->right=newnode(7);
    	root->left->right->left=newnode(1);
    	root->left->right->right=newnode(12);
    	root->left->right->right->left=newnode(2);
    
    	int s;
    
    	cout<<"enter input value to find ancestors......"<<endl;
    	cin>>s;
    
    	printAncestors(root,s);
    	return 0; 
    }

**Output**

**输出量**

tree in the example is build here
    enter input value to find ancestors......
    7
    5 8

> 翻译自: [https://www.includehelp.com/icp/ancestors-in-binary-tree.aspx][https_www.includehelp.com_icp_ancestors-in-binary-tree.aspx]

二叉树祖先节点

[Ancestors in Binary Tree]: /images/20230208/962880025e454b1ab8b32319bdcfaf77.png
[https_www.includehelp.com_icp_ancestors-in-binary-tree.aspx]: https://www.includehelp.com/icp/ancestors-in-binary-tree.aspx