1

そのため、再帰を使用して二分探索木のメンバー関数、事前順序および順序順トラバーサルを実装する必要があります。間違った出力が出てくるので、3 つすべてを実装するのに問題があります。トラバーサルは、遭遇したデータ値を特定のリンクリストに追加することになっています。

私のメンバー関数は、ツリーの正しいノードのみを出力します。コードを添付しました。エラーがどこにあるのか、出力が本来あるべきものを出力しない理由について、誰かが私にいくつかのポインタを与えることができれば、それは驚くべきことです. 前もって感謝します！！！

現在取得している出力:

size of test BinaryTree: 11  
member true for 8  
member true for 38  
member true for 39  
member true for 45  
pre order: [8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 38, 38, 38, 38, 38, 38, 38, 38, 39, 39, 45, 45]  
in order: [8, 8, 8, 8, 38, 38, 38]

私が欲しい出力：

size of test BinaryTree: 11  
member true for 1  
member true for 3  
member true for 4  
member true for 7  
member true for 8  
member true for 16  
member true for 31  
member true for 33  
member true for 38  
member true for 39  
member true for 45  
pre order: [8, 4, 3, 1, 7, 38, 31, 16, 33, 39, 45]  
in order: [1, 3, 4, 7, 8, 16, 31, 33, 38, 39, 45]

私のコード:

bool BinaryTreeNode::member(Data * newData) {
   if (newData->compareTo(this->nodeData) == 0) {
           return true;
    }
   else if (newData->compareTo(this->nodeData) == -1) {
         if (left == NULL)
             return false;
        else
             return left->member(newData);
}
   else if (newData->compareTo(this->nodeData) == 1) {
        if (right == NULL)
           return false;
        else
           return right->member(newData);
}
return false;
    }        

    void BinaryTreeNode::preorderTraversal(LinkedList * result) const {
    result->insert(nodeData);
        if (left != NULL) left->preorderTraversal(result);
    result->insert(nodeData);
    if (right != NULL) right->preorderTraversal(result);
        }

    void BinaryTreeNode::inorderTraversal(LinkedList * result) const {
    if (left != NULL) {
         left->inorderTraversal(result);
         result->insert(nodeData);
    }
    if (right != NULL) {
         right->inorderTraversal(result);
    }
    }
4

3 に答える 3

9

予約注文：

do stuff with the node // pre means before
recurse left
recurse right

順番に：

recurse left
do stuff with the node // in means inside
recurse right

ポストオーダー:

recurse left
recurse right
do stuff with the node // post means after
于 2012-10-07T17:16:56.563 に答える
1

さて、左サブツリーがあった場合、inorder は実際のノード データを結果に挿入するだけです。データの挿入は無条件である必要があります。

if (left != NULL) left->inorderTraversal(result);
result->insert(nodeData);
if (right != NULL) right->inorderTraversal(result);

予約注文ではデータが 2 回挿入されますが、それ以外は問題ないようです。

于 2012-10-07T17:16:19.967 に答える
1 
#include<conio.h>
#include<iostream>
using namespace std;
  struct node
  {
         int data;
         node *left,*right;       
  };
         void add(node **root)
         {
              node *temp,*save,*r;
              temp=*root;
              int num;
              cout<<"Enter node in BST\t";
              cin>>num;
              if(*root==NULL)
              {
                            cout<<"Root:"<<num<<"\n";
                            temp=new node;
                            temp->data=num;
                            temp->left=NULL;
                            temp->right=NULL;
                            *root=temp;              
              }
              else
              {
                            temp=*root;
                            while(temp!=NULL)
                            {
                                   if(temp->data>num)
                                   {
                                          save=temp;
                                          temp=temp->left;                 
                                   }                 
                                   else
                                   {
                                          save=temp;
                                          temp=temp->right;    
                                   }
                            }    
                            if(save->data>num)
                            {
                                   r=new node;
                                   r->data=num;
                                   r->left=NULL;
                                   r->right=NULL;
                                   save->left=r;
                                   temp=r;                  
                            }
                            else
                            {
                                   r=new node;
                                   r->data=num;
                                   r->left=NULL;
                                   r->right=NULL;
                                   save->right=r;
                                   temp=r;    
                            }
              }
         }
         void pre(node **root)
         {
              node *temp,*save;
              node *stack[100],*r;
              int top;
              temp=*root;
              if(*root==NULL)
              {
                           cout<<"=> No node in BST\n\n";
                           return;             
              }
              else
              {
                  while(temp!=NULL)
                  {
                       cout<<temp->data<<"\n";
                       if(temp->right!=NULL)
                       {
                              stack[++top]=temp->right;           
                       }    
                     if(temp->left!=NULL)
                     {
                             temp=temp->left;        
                     }
                     else
                     {
                             temp=stack[top];
                             top--;
                             delete stack;    
                     }
                  }
              }
         }
         //Below all is using recursion
int preorder(node *root)
{
if(root==NULL)
{
              return 0;               
}
 cout<<root->data<<"\n";
 preorder(root->left);
 preorder(root->right);
}
int inorder(node *root)
{
if(root==NULL)
{
              return 0;               
}
 inorder(root->left);
 cout<<root->data<<"\n";
 inorder(root->right);
}
int postorder(node *root)
{
if(root==NULL)
{
              return 0;               
}
 postorder(root->left);
 postorder(root->right);
  cout<<root->data<<"\n";
}
int main()
{
int n;
node *p=NULL;
cout<<"Binary search tree\n";
while(n!=6)
{
        cout<<"Select: 1.Insert node in BST\n\t2.Pre-order traversal\n\t3.Pre-order    \n\t4.Inorder\n\t5.Postorder\n\t6.Exit\t";
        cin>>n;
        switch(n)
        {
                 case 1:add(&p);break;
                 case 2:pre(&p);break;
                 case 3:preorder(p);break;
                 case 4:inorder(p);break;
                 case 5:postorder(p);break;
                 case 6:cout<<"Program ends\n";break;
                 default:printf("=> Wrong option selected,Try again\n \n");break;         
        }        
}
getch();
return 0;     
}
于 2013-04-14T08:39:22.077 に答える