کمک درباره برنامه درخت دودویی

[Senmurv]

سلام به همگی

راستش تو یه برنامه در قسمت Create درخت دچار مشکل شدم برنامه ای که باید بنویسم برنامه ای که" گره های هر نوع درخت دودویی را به همراه فرزندانش" باید بگیره و سه پیمایش پیشوندی، میانوندی و پسوندی را در خروجی نمایش بده، مثلا گره های درخت مقابل که به

صورت زیر در ورودی دریافت کند.​

a: b c
b: d e
c: f Null
d: Null g
e: h i
f: Null j

f: Null j
مثلا این به این معناست که فرزند چپ NULL و فرزند j فرزند راسته

و خروجی آن هم به صورت :
Preorder: abdgehicfj
Inorder: dgbheiafjc
Postorder: gdhiebjfca
که اینجا رو مشکلی نی ولی مشکل من اینه در قسمت Create درخت گیج شدم.
زمانی که اولین a رو به همراه فرزنداش از وردودی می گیرم برنامه رو به صورتی که خودشو بازخوانی کنه رو انجام می ده ولی در ادامه چون درخت مثلا b ساخته شده در قسمت دوم گیر میکنه.

کسی میتونه این مشکل رو حل کنه؟

 

[sayyad84]

با سلام،
می شه قسمتی از برنامه که مربوط به تولید درخته رو بنویسید؟
از آرایه استفاده می کنید یا از لیست پیوندی؟

 

[Senmurv]

سلام-ممنونم.
ببینید اون چیزی که مصلمه برنامه ام در قسمت Create کاملا اشتباهه از نظر خودم!
اگه بخواهم درباره اشکالات توضیحی بدم اینه که در دستور switch قسمت اول case که مربوط Create فقط برای شاخه اول دستور درسته ولی در ادامه اشتباهه. و دستور Create هم مشکلاتی با توجه به قسمت اول خواهد داشت.
​

#include <iostream.h>
#include <process.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

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

class BT{
public:
node * tree;
void createTree(node **,char item,char iteml,char itemr);
void preOrder(node *); //PreOrder Function
void inOrder(node *); //InOrder Function
void postOrder(node *); //PostOrder Function
//void determineHeight(node *,int *);
//int totalNodes(node *);
//node **searchElement(node **,char);
//void deleteNode(char);
BT(){
tree=NULL;
}
};

//*********************** Main Body ****************************

void main(){
BT obj;
int choice,n;
char item,iteml,itemr;
node **tmp;
while(1){
clrscr();
cout<<"\n Travesal Tree:\n";
cout<<"\n\t1- Creat New Tree\n";
cout<<"\t2- Travesal (Inorder,Preorder,Postorder)\n";
//cout<<"\t3- Information your tree about\n";
//cout<<"\t4- Serach Node\n";
//cout<<"\t5- Delete Node\n";
cout<<"\t3- Exit\n";
cout<<"\n Select >>> ";
cin>>choice;
if (choice > 3 || choice<1)
{
cprintf("\n\n\t\tWarning : Select is incorrect (1-3) ");
getch();
}
switch(choice){


case 1 : //for Create Tree
{
cout<<"\n\t\tHow many nodes you want to creat : ";
cin>>n;
cout<<"\n";
int j;
for(j=1;j<=n;j++){
cout<<"\t\t:: Enter value "<<j<<" : ";
cin>>item;
cout<<"\t\tL : ";
cin>>iteml;
j++;
cout<<"\t\tR : ";
cin>>itemr;
j++;
obj.createTree(&obj.tree,item,iteml,itemr);
}
break;
}


//All Traversals(Inorder-Preorder-Postorder)
case 2 :
{
cout<<"\n\n Inorder Traversal : ";
obj.inOrder(obj.tree);
cout<<"\n\n Pre-order Traversal : ";
obj.preOrder(obj.tree);
cout<<"\n\n Post-order Traversal : ";
obj.postOrder(obj.tree);
getch();
break;
}


case 3 : exit(1);
}//switch
}
}


//********************* Create Tree *****************************

void BT :: createTree(node **tree,char item,char iteml,char itemr)
{

if(*tree == NULL) //if tree = NULL

{
*tree = new node;
(*tree)->data = item;
(*tree)->left = NULL;
(*tree)->right = NULL;
}
else if( iteml != NULL )
createTree( &((*tree)->left),iteml,NULL,NULL);
else if ( item != NULL )
createTree( &((*tree)->right),itemr,NULL,NULL);
}



//************************ Preorder *********************

void BT :: preOrder(node *tree){
if( tree!=NULL){
cout<<" "<< tree->data;
preOrder(tree->left);
preOrder(tree->right);
}
}

//************************ Inorder **********************

void BT :: inOrder(node *tree){
if( tree!=NULL){
inOrder( tree->left);
cout<<" "<< tree->data;
inOrder(tree->right);
}
}

//********************** Postorder ***********************

void BT :: postOrder(node *tree){
if( tree!=NULL){
postOrder( tree->left);
postOrder( tree->right);
cout<<" "<<tree->data;
}
}

​

 

[sayyad84]

با سلام،
فکر می کنم اگه یه نود ریشه داشته باشید به جای اشاره گر به ابتدا راحت تر باشه!
این برنامه رو نوشتم می تونید (اگه خواستید!) برنامتون رو با توجه بهش تغییر بدید! قسمت توضیح شده هم برای بررسی کارکرد صحیحشه!

#include <iostream.h>
#include <conio.h>
struct node
{
 char data;
 struct node *left;
 struct node *right;
}*Root=NULL;
void create_tree(node **p,char parent,int choice)
{
 char Temp;
 cout<<"\nEnter '"<<parent;
 if(choice == 1)
  cout<<"' left child:";
 else
  cout<<"' right child:";
 cin>>Temp;
 if(Temp == '0')
  return;
 (*p)=new node;
 (*p)->left=NULL;
 (*p)->right=NULL;
 (*p)->data=Temp;
 create_tree(&((*p)->left),(*p)->data,1);
 create_tree(&((*p)->right),(*p)->data,2);
}
int main()
{
 Root=new node;
 Root->left=NULL;
 Root->right=NULL;
 cout<<"Enter Root Data:";
 cin>>Root->data;
 
 create_tree(&(Root->left),Root->data,1);
 create_tree(&(Root->right),Root->data,2);
 
 /*
    cout<<Root->data;
 cout<<(Root->left)->data;
 cout<<(Root->right)->data;
 cout<<((Root->left)->left)->data;
 cout<<((Root->left)->right)->data;
 */
 getch();
 return 0;
 
}

امیدوارم به دردتون بخوره!​

 

[Senmurv]

برنامه ام رو تغییر دادم. مشکلم برطرف شده. ولی هنوز یه سوال برام مونده که جهت آموزش خودم می پرسم آیا می تونیم در برنامه باز هم تغییراتی بدیم که برنامه ,اون ترتیبی که در بالا گفتم هم رعایت کنه.

یعنی همون طور که در عکس میبینیم به جای اینکه در اون قسمتی که مشخص شده فرزند چپ از فرزند چپ پدر درخت رو بخواهد طبق اون ترتیبی که در پست اول مشخص کردم فرزند راست را بگیره که -در عکس دوم مشخص کردم- و البته که این کار رو تا آخر با ترنیبی که گفتم ادامه بده؟

منظورم این نوع ترتیب سواله:

a: b c

بعد از چپی فرزند بگیره:
b: d e

بعدر از راست اولی:
c: f Null

حالا دوباره بیاد از چپ شروع کنه از چپ چپ :
d: Null g

در ادامه:
e: h i

بعد از این مرحله میاد از میره از سمت راست راست که f باشه میپرسه:
f: Null j

البته این پرسش از همه عناصر ولی چون برگ ها هر دو فرزندشون NULL هستند دیگه ننوشتم.

​

سورس قسمتی از برنامه که لازمه دیده بشه رو هم میذارم:

#include <iostream.h>
#include <process.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
      
struct node{
    struct node *left;
       char data;
    struct node *right;
}*root=NULL;
      
    void create_tree(node **p,char parent,int choice);
    void preOrder(node *);
      
//*********************** Main Body ****************************
      
void main(){
    int choice;
    while(1){
        clrscr();
        cout<<"\n  Travesal Tree:\n";
        cout<<"\n\t1- Creat Tree\n";
        cout<<"\t2- Travesal (Inorder,Preorder,Postorder)\n";
        cout<<"\t3- Exit\n";
        cout<<"\n  Select >>> ";
        cin>>choice;
         if (choice > 3 || choice<1)
           {
             cout<<"\n\n\t\tWarning : Select is incorrect (1-3) ";
             getch();
           }
         switch(choice){
            case 1 :
                {
                     
root=new node;
                     root->left=NULL;
               root->right=NULL;
                     cout<<"\n\tEnter Root Data : ";
                     cin>>root->data;
                     create_tree(&(root->left),root->data,1);
                    create_tree(&(root->right),root->data,2);
                     getch();
                   break;
            }
      
            case 2 :
              {
      
            cout<<"\n\n   Preorder Traversal : ";
                preOrder(root);
            
                getch();
                break;
            }
         
        
            case 3 : exit(1);
       }//switch
    }
}
      
//*** Create Tree ****
      

void create_tree(node **p,char parent,int choice)
{
    char Temp;
     cout<<"\n\tEnter '"<<parent;
     if(choice == 1)
          cout<<"' left child : ";
     else
          cout<<"' right child : ";
     cin>>Temp;
     if(Temp == '0')
          return;
     (*p)=new node;
     (*p)->left=NULL;
     (*p)->right=NULL;
     (*p)->data=Temp;
      
     create_tree(&((*p)->left),(*p)->data,1);
     create_tree(&((*p)->right),(*p)->data,2);
}
      
//*** Preorder ***
      
void preOrder(node *root){
    if( root!=NULL){
        cout<<"   "<< root->data;
        preOrder(root->left);
        preOrder(root->right);
      
[LEFT]    {
{
[/LEFT]

​

 

[Senmurv]

با سلام،
فکر می کنم اگه یه نود ریشه داشته باشید به جای اشاره گر به ابتدا راحت تر باشه!
این برنامه رو نوشتم می تونید (اگه خواستید!) برنامتون رو با توجه بهش تغییر بدید! قسمت توضیح شده هم برای بررسی کارکرد صحیحشه!

امیدوارم به دردتون بخوره!​

سلام خیلی ممنونم که لطف کردید.و راهنمایی ام کردید.
راستی این قسمتی که "گفتید اگه یه نود ریشه داشته باشی" راحت تری منطورتون خوب منوجه نشدم.

 

[sayyad84]

سلام خیلی ممنونم که لطف کردید.و راهنمایی ام کردید.
راستی این قسمتی که "گفتید اگه یه نود ریشه داشته باشی" راحت تری منطورتون خوب منوجه نشدم.

با سلام،
خواهش می کنم!
این طور که من فهمیدم tree یه اشاره گر بود به ابتدای درخت ولی برنامه ی من root یه نود بود به عنوان ریشه ی درخت! (به صورت Global) من این طوری راحت تر بودم و نوع استفاده ازش کاملاً به شما بستگی داره!
در مورد برنامه هم فکر کنم این ساده ترین راه بود! چون برنامه بازگشتیه تا زمانی که فرزندان چپ کامل نشن به راست نمی ره!
البته مطمئناً راهی هست ولی این که بازگشتی باشه نمی دونم!!

 

[Senmurv]

در واقع داشتید همون (root) رو میگفتید.(من کمی گیج زدم!).
پس نباید با بازگشتی حل بشه...Ok! در هر مرحله با توجه به ارتفاعی که گره . تعداد عناصری که باید فرزند چپ و راست پرسید 2 برابر میشه.مشکل اینجاس. که چی به چیه!!

 

[sayyad84]

فکر می کنم در روش غیربازگشتی کار سخت تر باشه!
زیربرنامه ی تولید درخت رو کمی تغییر دادم و فکر کنم حرفی که بالا زدم رو باید پس بگیرم!! حالا می تونید هردو فرزند رو به ترتیب وارد کنید ولی بازم سمت چپ به سمت راست اولویت خواهد داشت! امیدوارم با این یکی مشکلتون حل بشه!

void create_tree(node **p,node **q,char parent)
{
 char T1,T2;
 cout<<"\nEnter '"<<parent<<"' left child:";
 cin>>T1;
 cout<<"\nEnter '"<<parent<<"' right child:";
 cin>>T2;
 if((T1 == '0')&&(T2 == '0'))
  return;
 if(T1 != '0')
 {
     (*p)=new node;
     (*p)->left=NULL;
     (*p)->right=NULL;
     (*p)->data=T1;
     create_tree(&((*p)->left),&((*p)->right),(*p)->data);
    }
 if(T2 != '0')
 {
     (*q)=new node;
     (*q)->left=NULL;
     (*q)->right=NULL;
     (*q)->data=T2;
     create_tree(&((*q)->left),&((*q)->right),(*q)->data);
    }
}
 
//in main
create_tree(&(Root->left),&(Root->right),Root->data

);​

 

[Senmurv]

سلام
خیلی ممنونم.
ولی یه سوال داشتم. اگه ما در این برنامه ساختار درخت رو با آرایه پیاده سازی کنیم ممکنه مشکل برطرف بشه.
درسته؟

[LEFT]struct node{
 char data,leftchild,rightchild;
};[/LEFT]

 

[sayyad84]

سلام
خیلی ممنونم.
ولی یه سوال داشتم. اگه ما در این برنامه ساختار درخت رو با آرایه پیاده سازی کنیم ممکنه مشکل برطرف بشه.
درسته؟

[LEFT]struct node{
char data,leftchild,rightchild;
};[/LEFT]

با سلام،
برای استفاده از آرایه دیگه از Struct استفاده نمی کنن. بلکه آرایه ای درنظر می گیرن و خونه ی "1" رو برایریشه در نظر می گیرن. حالا فرزندان ریشه در خونه های 2(چپ) و 3(راست) قرار می گیرن! بنابراین اگر Parent در خونه ی i باشه، فرزندانش در 2i و 2i+1 قرار می گیرن!
در این حالت برنامه های پیمایش رو هم باید به شکل زیر تغییر بدید: (البته فکر می کنم که این طوری باشه، تست نکردم)

preOrder(int i){
if( tree[i]!='0'){
cout<<" "<< tree[i];
preOrder(2*i);
preOrder(2*i+1);
}
}

در مورد استفاده از struct هم اولاً برای ارتباط بین گره های درخت باید بشه بهشون دسترسی پیدا کرد که با داده هاشون کار سختیه! پس باید از دو مقدار صحیح به عنوان محل قرارگیری شون استفاده کنید که عاقلانه نیست!
امیدوارم به درد بخور بوده باشه!

 

[Senmurv]

خیلی ممنونم که تا این جا راهنمایی ام کردید ببخشید میشه سورس این برنامه رو واسم توضیح بدید. که چه تفاوتی با دیگر سورسها داره.
دانلود