x عدم نمایش
Faradars Discount
۴۰٪ تخفیف جشنواره تخفیف بوی ماه مهر فرادرس کد تخفیف: MHR98
Faradars Discount
فرصت باقیمانده

چاپ گره های در فاصله k از ریشه درخت دودویی – راهنمای کاربردی

در این مطلب، روش نوشتن برنامه‌ای که یک گره در فاصله k از ریشه را در درخت دودویی چاپ می‌کند آموزش داده شده و یاده‌سازی آن در زبان‌های برنامه‌نویسی گوناگون شامل ++C، «جاوا» (Java)، «پایتون» (Python)، و «سی‌شارپ» (#C) با استفاده از روش مذکور، انجام شده است. فرض می‌شود که ریشه یک درخت و عدد صحیح k داده شده است. هدف آن است که همه گره‌هایی که در فاصله k از ریشه قرار دارند چاپ شوند. برای مثال، در درخت زیر، گره‌های ۴، ۵ و ۸ در فاصله ۲ از ریشه قرار دارند.

مساله را می‌توان با استفاده از روش بازگشتی حل کرد. پیاده‌سازی روش بازگشتی، رد زبان‌های برنامه‌نویسی گوناگون انجام شده است.

برنامه چاپ گره های در فاصله k از ریشه درخت دودویی در ++C

#include<bits/stdc++.h>  
#include<iostream> 
using namespace std; 
  
/* A binary tree node has data, 
pointer to left child and 
a pointer to right child */
class node  
{  
    public: 
    int data;  
    node* left;  
    node* right;  
      
    /* Constructor that allocates a new node with the  
    given data and NULL left and right pointers. */
    node(int data) 
    { 
        this->data = data; 
        this->left = NULL; 
        this->right = NULL; 
    } 
};  
  
void printKDistant(node *root , int k)  
{  
    if(root == NULL)  
        return;  
    if( k == 0 )  
    {  
        cout << root->data << " ";  
        return ;  
    }  
    else
    {  
        printKDistant( root->left, k - 1 ) ;  
        printKDistant( root->right, k - 1 ) ;  
    }  
}  
  
  
/* Driver code*/
int main()  
{  
  
    /* Constructed binary tree is  
            ۱  
            / \  
        ۲    ۳  
        / \  /  
        ۴ ۵ ۸  
    */
    node *root = new node(1);  
    root->left = new node(2);  
    root->right = new node(3);  
    root->left->left = new node(4);  
    root->left->right = new node(5);  
    root->right->left = new node(8);  
      
    printKDistant(root, 2);  
    return 0;  
}  
  
// This code is contributed by rathbhupendra

برنامه چاپ گره های در فاصله k از ریشه درخت دودویی در C

#include <stdio.h> 
#include <stdlib.h> 
  
/* 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; 
}; 
  
void printKDistant(struct node *root , int k)     
{ 
   if(root == NULL)  
      return; 
   if( k == 0 ) 
   { 
      printf( "%d ", root->data ); 
      return ; 
   } 
   else
   {       
      printKDistant( root->left, k-1 ) ; 
      printKDistant( root->right, k-1 ) ; 
   } 
} 
  
/* 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() 
{ 
  
  /* Constructed binary tree is 
            ۱ 
          /   \ 
        ۲      ۳ 
      /  \    / 
    ۴     ۵  ۸  
  */
  struct node *root = newNode(1); 
  root->left        = newNode(2); 
  root->right       = newNode(3); 
  root->left->left  = newNode(4); 
  root->left->right = newNode(5); 
  root->right->left = newNode(8);   
  
  printKDistant(root, 2); 
  
  getchar(); 
  return 0; 
}

برنامه چاپ گره های در فاصله k از ریشه درخت دودویی در جاوا

// Java program to print nodes at k distance from root 
   
/* A binary tree node has data, pointer to left child 
   and a pointer to right child */
class Node  
{ 
    int data; 
    Node left, right; 
   
    Node(int item)  
    { 
        data = item; 
        left = right = null; 
    } 
} 
   
class BinaryTree  
{ 
    Node root; 
   
    void printKDistant(Node node, int k)  
    { 
        if (node == null) 
            return; 
        if (k == 0)  
        { 
            System.out.print(node.data + " "); 
            return; 
        }  
        else 
        { 
            printKDistant(node.left, k - 1); 
            printKDistant(node.right, k - 1); 
        } 
    } 
      
    /* Driver program to test above functions */
    public static void main(String args[]) { 
        BinaryTree tree = new BinaryTree(); 
          
        /* Constructed binary tree is 
                ۱ 
              /   \ 
             ۲     ۳ 
            /  \   / 
           ۴    ۵ ۸  
        */
        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.right.left = new Node(8); 
   
        tree.printKDistant(tree.root, 2); 
    } 
} 
   
// This code has been contributed by Mayank Jaiswal

برنامه چاپ گره های در فاصله k از ریشه درخت دودویی در پایتون

# Python program to find the nodes at k distance from root 
  
# 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
  
def printKDistant(root, k): 
      
    if root is None: 
        return 
    if k == 0: 
        print root.data, 
    else: 
        printKDistant(root.left, k-1) 
        printKDistant(root.right, k-1) 
  
# Driver program to test above function 
""" 
   Constructed binary tree is 
            ۱ 
          /   \ 
        ۲      ۳ 
      /  \    / 
    ۴     ۵  ۸  
"""
root = Node(1) 
root.left = Node(2) 
root.right = Node(3) 
root.left.left = Node(4) 
root.left.right = Node(5) 
root.right.left = Node(8) 
  
printKDistant(root, 2) 
  
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)

برنامه چاپ گره های در فاصله k از ریشه درخت دودویی در #C

using System; 
  
// c# program to print nodes at k distance from root  
  
/* 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; 
  
    public Node(int item) 
    { 
        data = item; 
        left = right = null; 
    } 
} 
  
public class BinaryTree 
{ 
    public Node root; 
  
    public virtual void printKDistant(Node node, int k) 
    { 
        if (node == null) 
        { 
            return; 
        } 
        if (k == 0) 
        { 
            Console.Write(node.data + " "); 
            return; 
        } 
        else
        { 
            printKDistant(node.left, k - 1); 
            printKDistant(node.right, k - 1); 
        } 
    } 
  
    /* Driver program to test above functions */
    public static void Main(string[] args) 
    { 
        BinaryTree tree = new BinaryTree(); 
  
        /* Constructed binary tree is  
                ۱  
              /   \  
             ۲     ۳  
            /  \   /  
           ۴    ۵ ۸   
        */
        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.right.left = new Node(8); 
  
        tree.printKDistant(tree.root, 2); 
    } 
} 
  
// This code is contributed by Shrikant13

 خروجی

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

۴ ۵ ۸

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

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

منبع [+]

یک ستارهدو ستارهسه ستارهچهار ستارهپنج ستاره (No Ratings Yet)
Loading...

پاسخی بگذارید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *