• 0
الخارقة

هل يمكن رسم binary tree لهدا الكود؟

سؤال

اخوانى اخواتى

هدا كود بلغة السى واجهتنى صعوبة فى رسم الشجرة كما بالصورة


////////////////////////////////////////////////////////////////////////////////
//
//
//
// -----------------------------------------------------------------------------
//
// File : main.cpp
// Project :
// Role :
// Date :
// Author(s) : Adil C (3AM copyright © 2010) //
////////////////////////////////////////////////////////////////////////////////

#include <iostream>

#include <conio.h>
#include <stdio.h>
#include <stdlib.h>

////////////////////////////////////////////////////////////////////////////////
// Defines & Enumerations & structer
////////////////////////////////////////////////////////////////////////////////

struct node {
int data;
struct node* left;
struct node* right;
};

#define clrscr() system("CLS");
#define pause() system("PAUSE");

////////////////////////////////////////////////////////////////////////////////
// Global variables
////////////////////////////////////////////////////////////////////////////////



////////////////////////////////////////////////////////////////////////////////
// Prototypes
////////////////////////////////////////////////////////////////////////////////

struct node* NewNode(int);
int maxDepth(struct node*);
int size(struct node*);
int minValue(struct node*);
struct node* insert(struct node*, int);
void print(struct node *pnode);

/*=============================================================================*/
using namespace std;
////////////////////////////////////////////////////////////////////////////////
//
// M A I N F U N C T I O N
//
////////////////////////////////////////////////////////////////////////////////

void main(void)
{
struct node * root = '\0';
char choice;
int data, continu = 1;

do
{
clrscr();


root = insert(root, 10);
root = insert(root, 5);
root = insert(root, -3);
root = insert(root, 6);
root = insert(root, 7);
root = insert(root, 8);
root = insert(root, 1);
root = insert(root, 0);
root = insert(root, -1);

cout << "\nB) Max depth for tree";
cout << "\nC) Size of tree";
cout << "\nF) Print Tree";
cout << "\nD) Min value in tree";
cout << "\nE) Exit";

cout << "\nplease enter your choice: [ ]\b\b";
cin >> choice;

switch(choice)
{
case 'a' :
case 'A' : cout<<"\nplease enter your data for insert: ";
cin>>data;
root = insert(root, data);
break;
case 'b' :
case 'B' : if(root == '\0')
cout<< "\nsorry ! no tree was found";
else{
int maxD = maxDepth(root);
cout<< "\nmax Depth ="<< maxD;
}
break;
case 'c' :
case 'C' : if(root == '\0')
cout<< "\nsorry ! no tree was found";
else{
int Size = size(root);
cout<< "\nthe size of the tree = " << Size;
}
break;
case 'd' :
case 'D' : if(root == '\0')
cout<< "\nsorry ! no tree was found";
else{
int Min = minValue(root);
cout<< "\nthe min value ot the tree = " << Min;
}
break;
case 'e':
case 'E':
continu = 0;
break;

case 'f':
case 'F': if(root == '\0')
cout<< "\nsorry ! no tree was found";
else
{
print(root);
}
break;

default:
cout << "Input Error!!!" << endl;
break;
}
if(choice != 'e' && choice != 'E')
getch();
}while(continu);//اصافة

}
//==============================================================================
//
// F U N C T I O N S
//
//==============================================================================

struct node* NewNode(int data)
{
struct node* node = new(struct node); // "new" is like "malloc"
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}


int maxDepth(struct node* node) {
if (node==NULL)
return(0);

else {
// compute the depth of each subtree
int lDepth = maxDepth(node->left);
int rDepth = maxDepth(node->right);
// use the larger one
if (lDepth > rDepth)
return(lDepth+1);
else return(rDepth+1);
}
}


struct node* insert(struct node* node, int data) {
// 1. If the tree is empty, return a new, single node
if (node == NULL) {
return(NewNode(data));
}
else {
// 2. Otherwise, recur down the tree
if (data <= node->data )
node->left = insert(node->left, data);
else
node->right = insert(node->right, data);
return(node); // return the (unchanged) node pointer
}
}

int size(struct node* node) {
if (node==NULL)
return(0);
else
return(size(node->left) + 1 + size(node->right));
}


int minValue(struct node* node) {
struct node* current = node;
// loop down to find the leftmost leaf
while (current->left != NULL) {
current = current->left;
}

return(current->data);
}
void print(struct node *pnode)
{
int pdata = 0;

if(pnode != NULL)
{
print(pnode->left);
print(pnode->right);
if(pnode->left != NULL)
{
if(pnode->data > pnode->left->data)
cout << pnode->data << endl;
else
cout << pnode->data;
}
else if(pnode->right != NULL)
{
if(pnode->data < pnode->right->data)
cout << pnode->data << endl;
else
cout << pnode->data;
}
else
{
cout << pnode->data;
}

}
}





post-156441-029089900 1290820012_thumb.j

تم تعديل بواسطه الخارقة
إضافة الكود
0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

5 إجابة على هذا السؤال .

  • 0

من الأفضل إضافة الكود بدلاً من المرفقات إن لم يكن طويل ( لقد أضفته ) .

-

يبدو كود بناء الشجرة ، غير واضح بالنسبة لك ، حيث أرى أرقام غريبة مستخدمة في البرنامج لا علاقة لها بالسؤال ؟


//root = insert(root, 10);
//root = insert(root, 5);
//root = insert(root, -3);
//root = insert(root, 6);
//root = insert(root, 7);
//root = insert(root, 8);
//root = insert(root, 1);
//root = insert(root, 0);
//root = insert(root, -1);

أولاً يجب معرفة الفكرة من الشجرة الثنائية Binary Tree ، وهي تقسيم الشجرة إلى أجزاء ، حيث كل أب يحتوي على اثنين من الأبناء فقط( بشكل مباشر ) ، ابن على يسار الأب وابن على يمين الأب بحيث الابن الذي على يسار الأب له قيمة أصغر من الابن الذي على يمين الأب والهدف من ذلك تسريع خوارزمية البحث ( باختصار نصف المشوار على الأقل ) .

الكود الذي كتبه " عادل " ، صحيح على ما يبدو ، والدليل أنه يطبع هذه الشجرة بشكل صحيح :


root = insert(root, 3);
root = insert(root, 2);
root = insert(root, 1);
root = insert(root, 5);
root = insert(root, 4);
root = insert(root, 9);
root = insert(root, 8);
root = insert(root, 10);

يمكن تحسين طريقة الطباعة بإضافة بعض الفواصل :

void print(struct node *pnode)
{
int pdata = 0;

if(pnode != NULL)
{
print(pnode->left);
print(pnode->right);
if(pnode->left != NULL)
{
if(pnode->data > pnode->left->data)
cout << pnode->data << endl;
else
cout << pnode->data << ",";
}
else if(pnode->right != NULL)
{
if(pnode->data < pnode->right->data)
cout << pnode->data << endl;
else
cout << pnode->data << ",";
}
else
{
cout << pnode->data << ",";;
}

}
}

والنتيجة :


1,2
4,8,10,9
5
3

حيث الدالة print ، تطبع الأبناء على يسار الشجرة ، ثم الأبناء على يمين الشجرة ( الأبناء قبل الآباء ، حيث يبدأ البرنامج من المستوى الأخير حتى المستوى الأول من اليسار إلى اليمين ) ، وأخيراً يتم طباعة الجذر .

يمكن تغيير هذا السيناريو بتغييرات بسيطة جداً في الدالة print ، وأترك هذا كتمرين للطلاب :P .

لطباعة الشجرة ، هناك ثلاثة طرق مشهورة وهي postordre و preorder و inorder .. طريقة inorder تطبع الشجرة بشكل أكثر مقروئية ..

http://lcm.csa.iisc.ernet.in/dsa/node87.html

traverse tree

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

اخ الشمرى شكرا لتوضيحك ... بالنبة لفكرة الشجرة واضحه جدا

وكدلك الطرق التلاتة للطباعه ....

لكن ما اسال عنه طريقة اخرج الشجرة وزى ما قلت انت بتغير بسيط ارغب برسم الشجرة وليس طباعتها باحدى الطرق التلات ياريت تساعدنى لانى عندى امتحان وبحتت عنها كثيرا ولم اجدها

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

عدد كبير من المشاهدات لا مساعدات

فى انتظار المساعده

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

السلام عليكم

post-115179-055379600 1291477841_thumb.p


#include <iostream>
#include <queue>
#include <conio.h>
using namespace std;


typedef struct node_tag {
int info ;
struct node_tag * left ;
struct node_tag * right ;
} node_type,Node ;

void InsertNode(Node* &treeNode, int data)
{
if(treeNode == NULL)
{
Node * tmp = new Node;
tmp->info = data;
tmp->left = NULL;
tmp->right = NULL;
treeNode = tmp;
}
else if (data < treeNode->info)
InsertNode(treeNode->left, data);
else
InsertNode(treeNode->right, data);
}
void printBT(Node * root)
{
if(root)
{
cout << root->info << endl;
cout << " L = ";
printBT(root->left);
cout << " R = ";
printBT(root->right);
cout << "******";
}
}

void breadth_first_traversal(Node *root)
{
queue< Node* > buf_ptrs;
queue< Node* > levelorder;
if (root)
buf_ptrs.push(root);

while (buf_ptrs.size())
{
Node *front = buf_ptrs.front();
cout<< front->info << endl; //print
if (front->left)
buf_ptrs.push(front->left);
if (front->right)
buf_ptrs.push(front->right);
buf_ptrs.pop();
}
}

void padding ( char ch, int n )
{
int i;

for ( i = 0; i < n; i++ )
putchar ( ch );
}

void structure ( Node * root, int level )
{
int i;

if ( root == NULL ) {
padding ( '\t', level );
puts ( "~" );
}
else {
structure ( root->right, level + 1 );
padding ( '\t', level );
printf ( "%d\n", root->info );
structure ( root->left, level + 1 );
}
}

int main()
{
node_type * root = new Node ; /* pointer to root */
node_type * p ; /* temporary pointer */

root->info = 20;
root->left = NULL;
root->right = NULL;

int arr[] = {10,5,3,7,5,2,6,11,55,6,5,88,1,22,0};

for(int i = 0; i <15 ; i++)
InsertNode(root,arr[i]);

//printBT(root);
//breadth_first_traversal(root);
structure(root , 0);
getche();
return 0;
}

لاحظ ان دالة structure استخدمتها لاعرض الشجرة ولكن الشجرة الناتجة تحتاج الى دورانها حتى تستطيع ان تراها جيدا بشكلها الطبيعى

بالتوفيق

1

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه
  • 0

كل الشكر لك اخى على وضعك للكود

ولكن الكود لا يحتاج للدوران وانما يحتاج لشيء اخر .؟؟؟؟؟؟؟؟؟

0

شارك هذا الرد


رابط المشاركة
شارك الرد من خلال المواقع ادناه

  • يستعرض القسم حالياً   0 members

    لا يوجد أعضاء مسجلين يشاهدون هذه الصفحة .