1

所以我需要使用递归实现二叉搜索树的成员函数、前序和中序遍历。我在实现这三个方面都遇到了麻烦，因为它们的输出错误。遍历应该将它遇到的数据值添加到给定的链表中。

我的成员函数只打印出树的正确节点。我附上了我的代码，如果有人能给我一些关于错误所在的位置以及为什么输出没有打印出它应该是的内容的指示，那就太棒了。提前致谢！！！

我目前得到的输出：

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

您的预购会插入数据两次，但其他方面看起来还不错。

于 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 回答