使用递归进行序列遍历 - 二叉搜索树C++

Question

所以我需要实现一个成员函数，使用递归进行二叉搜索树的预定序和遍历。我在执行所有这三个操作时遇到了麻烦，因为他们出错了。遍历应该将它遇到的数据值添加到给定的链表中。

我的成员函数只打印出树的正确节点。我附加了我的代码，如果有人能够给我一些指出错误在哪里以及为什么输出不打印它应该是什么的东西，那将是很了不起的。提前致谢！！！

输出我目前得到：

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

Answer 1

那么，你的序只是插入实际节点数据输入结果如果有的话一直是左子树。插入数据应该是无条件的：

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

你序插入数据的两倍，但看起来确定，否则。

Answer 2

预购：

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 

Answer 3

#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;  
}