در این مطلب، روش نوشتن برنامه چاپ اجداد یک گره در درخت دودویی بیان شده و پیاده‌سازی آن در زبان‌های برنامه‌نویسی گوناگون شامل ++C، «جاوا» (Java)، «پایتون» (Python)، و «سی‌شارپ» (#C) با استفاده از روش مذکور، انجام شده است. فرض می‌شود که یک درخت دودویی و یک کلید داده شده؛ هدف نوشتن تابعی است که همه اجداد کلید را در درخت دودویی داده شده چاپ کند.

برای مثال، اگر درختی که در ورودی داده شده، به صورت درخت دودویی زیر و کلید داده شده ۷ باشد، تابع باید مقادیر ۴، ۲ و ۱ را در خروجی چاپ کند.

 

برنامه چاپ اجداد یک گره در درخت دودویی در ++C

// C++ program to print ancestors of given node 
#include<iostream> 
#include<stdio.h> 
#include<stdlib.h> 
  
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 
              ۱ 
            /   \ 
          ۲      ۳ 
        /  \ 
      ۴     ۵ 
     / 
    ۷ 
  */
  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 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 
                  ۱ 
                /   \ 
               ۲     ۳ 
              /  \ 
             ۴    ۵ 
            / 
           ۷ 
        */
        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  
                ۱  
                / \  
            ۲    ۳  
            / \  
            ۴ ۵  
            /  
        ۷  
        */
        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

 خروجی

خروجی قطعه کدهای بالا، به صورت زیر است.

۴ ۲ ۱

پیچیدگی زمانی این روش از درجه (O(n است که در آن، n تعداد گره‌ها در یک درخت دودویی محسوب می‌شود.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌‌های برنامه‌‌‌نویسی
• آموزش برنامه‌نویسی C++‎
• مجموعه آموزش‌های ریاضیات
• یافتن دور همیلتونی با الگوریتم پس گرد — به زبان ساده
• برنامه تشخیص وجود دور در گراف جهت دار — راهنمای کاربردی
• برنامه بررسی وجود دور در گراف بدون جهت — راهنمای کاربردی
• حل مساله n وزیر با الگوریتم پس‌گرد (Backtracking) — به زبان ساده

 

منبع [+]