الفريق العربي للبرمجةأرشيف المنتديات · 2000 – 2023
نسخة أرشيفية للقراءة فقط — التسجيل والمشاركة مغلقان، والمحتوى محفوظ كما كان.

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

بدأه الخارقة في 27 نوفمبر 2010 · 5 رد · 4,109 مشاهدة · في الأسئلة المجابة
مشاركة: واتساب X فيسبوك تيليجرام
#1 صاحب الموضوع

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

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

////////////////////////////////////////////////////////////////////////////////
//
//
//
// -----------------------------------------------------------------------------
//
//  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

المرفقات
blah.jpg

تم تعديل هذه المشاركة بواسطة الخارقة في 28 نوفمبر 2010 في 01:55 — السبب: إضافة الكود

#2

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

-

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

		//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

logo1.png تطبيق طمأنينة ، نسخة بيتا على أندرويد

عبدالله الشمّري - Al-Shammari

CodingAlone.com

twitter @abshammeri

abshammeri AT gmail.com

github : abshammeri

#3

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

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

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

#4

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

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

#5

السلام عليكم

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);

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

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

بالتوفيق

المرفقات
btt - Copy.png
1
amdvsintel22.jpg

--i use AMD--

لا اله الا الله محمد رسول الله

أستعن بالله و لا تعجز

تابعنى على تويتر

***

#6

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

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

مواضيع مشابهة