مدونة عماد – Emad's Blog

طرق الاجتياز في شجرة البيانات بلغة سي بلس بلس

نشر في 13 مايو 2012 في C++,Codes,CS,ICS,JazanU,Projects,دروس

من ويكيبيديا، الموسوعة الحرة

شجرة (بنية بيانات)

في علم الحاسوب, الشجرة هي هيكل بيانات واسع الاستخدام يحاكي بنية شجرة هرمية مع مجموعة من الرؤوس المرتبطة.

طرق الاجتياز

المرور خلال عناصر الشجرة, عن طريق العلاقات بين الآباء والأبناء, يسمى اجتياز الشجرة. عادة, بالإمكان تنفيذ عملية ما عندما يصل المؤشر إلى رأس معين. اجتياز الذي يتم به المرور على كل أب قبل أبنائه يسمى اجتياز بترتيب خلفي; اجتياز الذي يتم به المرور على كل أب قبل أبنائه يسمى اجتياز بترتيب أمامي; اجتياز الذي يتم به المرور على الشجرة الفرعية اليسرى ثم الرأس نفسه يسمى اجيازا مرتبا. (الحالة الأخيرة, تشير إلى شجرتين فرعيتين بالضبط, شجرة فرعية يمني وشجرة فرعية يسرى, يفترض بالتحديد شجرة ثنائية.)

البرنامج يقوم بترتيب أي شجرة بيانات من النوع الثنائي وقد كان مطلوباً مني في مادة الهندسة الحاسوبية

 Tree traversal in C++

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

// Node class.
class Node {
    int key;
    Node* left;
    Node* right;
public:
    Node() { key=-1; left=NULL; right=NULL; };
    void setKey(int aKey) { key = aKey; };
    void setLeft(Node* aLeft) { left = aLeft; };
    void setRight(Node* aRight) { right = aRight; };
    int Key() { return key; };
    Node* Left() { return left; };
    Node* Right() { return right; };
};

// Tree class.
class Tree {
     Node* root;
public:
     Tree();
     ~Tree();
     Node* Root() { return root; };
     void addNode(int key);
     void inOrder(Node* n);
     void preOrder(Node* n);
     void postOrder(Node* n);
private:
     void addNode(int key, Node* leaf);
     void freeNode(Node* leaf);
};

// Constructor for building the new Tree.
Tree::Tree() {
     root = NULL;
}

// Destructor for deleting any unneeded Node.
Tree::~Tree() {
     freeNode(root);
}

// Free the Node.
void Tree::freeNode(Node* leaf)
{
    if ( leaf != NULL )
    {
       freeNode(leaf->Left());
       freeNode(leaf->Right());
       delete leaf;

    }
}

// Add a Node (Public).
void Tree::addNode(int key) {
     // No elements? Add the root
     if ( root == NULL ) {
        cout << "Adding the root node\t" << key << endl << endl;
        Node* n = new Node();

        n->setKey(key);
    root = n;
     }
     else {
    cout << "Adding the node\t" << key << endl << endl;
    addNode(key, root);
     }
}

// Add a node (Private).

void Tree::addNode(int key, Node* leaf) {
    if ( key <= leaf->Key() ) {
       if ( leaf->Left() != NULL )
      addNode(key, leaf->Left());
       else {
      Node* n = new Node();
      n->setKey(key);

      leaf->setLeft(n);
       }
    }
    else {
       if ( leaf->Right() != NULL )
      addNode(key, leaf->Right());
       else {
      Node* n = new Node();
      n->setKey(key);

      leaf->setRight(n);
       }
    }
}

// Print the Tree In-Order.
// Traverse the left sub-tree, root, right sub-tree.
void Tree::inOrder(Node* n) {
    if ( n ) {
       inOrder(n->Left());
       cout << n->Key() << " ";
       inOrder(n->Right());
    }
}

// Print the Tree Preorder.
// Traverse the root, left sub-tree, right sub-tree.
void Tree::preOrder(Node* n) {

    if ( n ) {
       cout << n->Key() << " ";
       preOrder(n->Left());
       preOrder(n->Right());
    }
}

// Print the Tree Postorder.
// Traverse left sub-tree, right sub-tree, root.

void Tree::postOrder(Node* n) {
    if ( n ) {
       postOrder(n->Left());
       postOrder(n->Right());
       cout << n->Key() << " ";
    }
}

// Test main program

void main() {
   // The Drawing for the Example Tree.
   cout << "Example\n";
   cout << "\t\t\t40 << the root\n\n" << "\t20\t\t\t\t60\n\n"
	   << "10\t\t30\t\t50\t\t70\n\n\n\n";

   // You Must do this.
   cout << "1. First enter the number of nodes in your tree.\n"
	   << "2. Note that YOU MUST enter the root as the first node!\n\n";

   // The Beginning of the Program.
   Tree* tree = new Tree();
   cout << "=============|| Adding The Tree ||=============\n";
   cout << "How many nodes you want to enter?\t";
   int noOfNodes, chash;
   cin >> noOfNodes;
   for (int i=1; i<=noOfNodes; i++){
	   if (i == 1){
		   cout << "Please enter node #" << i <<" (The Root)\t";
		   cin >> chash;
		   tree->addNode(chash);
	   }
	   else{
		   cout << "Please enter node #" << i << "\t";
		   cin >> chash;
		   tree->addNode(chash);
	   }
   }

   cout << "\n==============|| Traversal ||==============\n";
   cout << "In Order Traversal: \t";
   tree->inOrder(tree->Root());
   cout << endl << endl;

   cout << "Preorder Traversal: \t";
   tree->preOrder(tree->Root());
   cout << endl << endl;

   cout << "Postorder Traversal: \t";
   tree->postOrder(tree->Root());
   cout << endl << endl;

   delete tree;
   getch();
}

متتالية فيبوناتشي بلغة ++C

نشر في 11 مايو 2012 في C++,Codes,CS,JazanU,Projects

من ويكيبيديا

متتالية فيبوناتشي أو أعداد فيبوناتشي في الرياضيات هي الأرقام التي تكون في المتتالية التالية:

بتعريفها فإن أول من أرقام فيبوناتشي هما 0 و 1، ويكون كل رقم هو نتاج مجموع الرقمين السابقين له. بعض المدارس حذفت الرقم 0 الأساسي واستبدلته بالرقم 1 مرتين.

الكود البرمجي بلغة ++C بطلب من أحد الزملاء:

Write a C++ program to Calculate the sum of the first n Fibonacci numbers? As an example, the sum of the first 7 numbers is 1+1+2+3+5+8+13=33

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

int fib(int);
int sumfib(int);
int FibonacciNumber;
void main(){
	cout << "Please Enter the Fibonacci Number\t";
	cin >> FibonacciNumber;
	cout << "\nThe Fibonacci Number is\t" << fib(FibonacciNumber) << endl;
	cout << "The Sum of the first " << FibonacciNumber
		<< " Fibonacci Numbers are\t" << sumfib(FibonacciNumber);
	_getch();
}

int fib(int n){
	if(n < 2)
		return n;
	else
		return fib(n-1) + fib(n-2);
}
int sumfib(int sum){
	int cash=0;
	for(int i=0; i<=sum; i++){
		cash+= fib(i);
	}
	return cash;
}