چاپ گره های در فاصله 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 خواهد بود.
اگر نوشته بالا برای شما مفید بوده است، آموزشهای زیر نیز به شما پیشنهاد می‌شوند:
- مجموعه آموزشهای برنامهنویسی
- آموزش برنامهنویسی C++
- مجموعه آموزشهای ریاضیات
- یافتن دور همیلتونی با الگوریتم پس گرد — به زبان ساده
- برنامه تشخیص وجود دور در گراف جهت دار — راهنمای کاربردی
- برنامه بررسی وجود دور در گراف بدون جهت — راهنمای کاربردی
- حل مساله n وزیر با الگوریتم پس‌گرد (Backtracking) — به زبان ساده
مجموعه: کد سرا, کدهای آماده, مهندسی کامپیوتر
Loading...