обход и предзаказ с использованием рекурсии — двоичное дерево поиска Переполнение стека
поэтому мне нужно реализовать функцию-член, предварительный порядок и обход inorder бинарного дерева поиска с помощью рекурсии. У меня проблемы с реализацией всех трех, так как они выходят с неправильными результатами. Предполагается, что обходы добавляют значения данных, с которыми они сталкиваются, к заданному связанному списку.
Моя функция-член распечатывает только правые узлы дерева. Я приложил свой код, и было бы удивительно, если бы кто-то мог дать мне несколько указаний относительно того, где находятся ошибки и почему вывод не печатает, как это должно быть. Заранее спасибо!!!
Вывод, который я сейчас получаю:
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
Postorder:
recurse left
recurse right
do stuff with the node // post means after
Другие решения
Ну, ваш порядок вставляет фактические данные узла в результат, только если было левое поддерево. Вставка данных должна быть безусловной:
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 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;
}