使用递归的中序和前序遍历 - 二叉搜索树 C++
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/12770845/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
inorder and preorder traversal using recursion - binary search tree c++
提问by user1333781
so i need to implement a member function, pre-order and inorder traversal of a binary search tree using recursion. i'm having trouble implementing all three, since they're coming out with the wrong outputs. The traversals are supposed to add data values it encounters to a given linked list.
所以我需要使用递归来实现一个成员函数，二叉搜索树的前序和中序遍历。我在实现所有三个方面都遇到了麻烦，因为它们的输出错误。遍历应该将它遇到的数据值添加到给定的链表中。
My member function only prints out the right nodes of the tree. I have attached my code, and it would be amazing if someone could give me some pointers as to where the errors lie and why the output is not printing what it's supposed to be. Thanks in advance!!!
我的成员函数只打印出树的正确节点。我已经附上了我的代码，如果有人能给我一些关于错误在哪里以及为什么输出没有打印它应该是的内容的指示，那将是令人惊奇的。提前致谢！！！
Output I currently get:
我目前得到的输出：
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]
Output I want:
我想要的输出：
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]
My code:
我的代码：
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);
}
}
回答by n. 'pronouns' m.
Preorder:
预购：
do stuff with the node // pre means before
recurse left
recurse right
Inorder:
为了：
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
回答by Bijay yadav
#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;
}
回答by Christian Stieber
Well, your inorder only inserts the actual node data into the result if there has been a left subtree. The data insert should be unconditional:
好吧，如果存在左子树，您的 inorder 只会将实际节点数据插入到结果中。数据插入应该是无条件的：
if (left != NULL) left->inorderTraversal(result);
result->insert(nodeData);
if (right != NULL) right->inorderTraversal(result);
Your preorder inserts the data twice, but looks ok otherwise.
您的预订将数据插入两次，但其他方面看起来还可以。
