所以我需要实现一个成员函数,使用递归对二叉搜索树进行预序和无序遍历。 我在实现所有三个时遇到问题,因为它们的输出错误。遍历应该将它遇到的数据值添加到给定的链表中。
我的成员函数只打印出树的正确节点。我已经附上了我的代码,如果有人能给我一些关于错误所在以及为什么输出没有打印它应该是什么的指示,那就太神奇了。提前谢谢!!
我目前得到的输出:
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);
}
}
预购:
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
好吧,如果有一个左子树,您的 inorder 只会将实际的节点数据插入到结果中。数据插入应该是无条件的:
if (left != NULL) left->inorderTraversal(result);
result->insert(nodeData);
if (right != NULL) right->inorderTraversal(result);
您的预购会插入数据两次,但看起来还可以。
#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 BSTt";
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 BSTnn";
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 treen";
while(n!=6)
{
cout<<"Select: 1.Insert node in BSTnt2.Pre-order traversalnt3.Pre-order nt4.Inordernt5.Postordernt6.Exitt";
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 endsn";break;
default:printf("=> Wrong option selected,Try againn n");break;
}
}
getch();
return 0;
}