我的问题是关于遍历。在我的问题中，遍历的顺序没有遵循应有的顺序。我正在使用中序、前序和后序遍历的一般逻辑，但它给出的顺序是错误的。
我的问题是我的代码没有像我预期的输出那样遍历。预期输出应如下所示：
Initially, how many integers you want:
5
Enter the integers: 7 9 1 2 10
Press 1 for inorder traverse, 2 for preorder traverse, 3 for postorder traverse, 4 for inserting new item, 5
for deleting an item, or 6 for exit the program:
4
Enter the item for insert:
2
This item already exists.
Press 1 for inorder traverse, 2 for preorder traverse, 3 for postorder traverse, 4 for inserting new item, 5
for deleting an item, or 6 for exit the program:
4
Enter the item for insert:
8
This item is inserted.
Press 1 for inorder traverse, 2 for preorder traverse, 3 for postorder traverse, 4 for inserting new item, 5
for deleting an item, or 6 for exit the program:
5
Enter the item for delete:
12
This item not found.
Press 1 for inorder traverse, 2 for preorder traverse, 3 for postorder traverse, 4 for inserting new item, 5
for deleting an item, or 6 for exit the program:
5
Enter the item for delete:
7
This item is deleted.
Press 1 for inorder traverse, 2 for preorder traverse, 3 for postorder traverse, 4 for inserting new item, 5
for deleting an item, or 6 for exit the program:
1
**Inorder Traverse: 1 2 8 9 10**
Press 1 for inorder traverse, 2 for preorder traverse, 3 for postorder traverse, 4 for inserting new item, 5
for deleting an item, or 6 for exit the program:
2
**Preorder Traverse: 2 1 9 8 10**
Press 1 for inorder traverse, 2 for preorder traverse, 3 for postorder traverse, 4 for inserting new item, 5
for deleting an item, or 6 for exit the program:
3
**Postorder Traverse: 1 8 10 9 2**
Press 1 for inorder traverse, 2 for preorder traverse, 3 for postorder traverse, 4 for inserting new item, 5
for deleting an item, or 6 for exit the program:
6
Program terminated
但我的输出显示这样的遍历：
Inorder Traverse: 1 2 8 9 10
Preorder Traverse: 8 1 2 9 10
Postorder Traverse: 2 1 10 9 8
我的代码如下：
#include <iostream>
using namespace std;
struct Node
{
int data;
Node *left;
Node *right;
Node(int value) : data(value), left(nullptr), right(nullptr) {}
};
class BST
{
private:
Node *root;
Node *insertRecursive(Node *root, int value)
{
if (root == nullptr)
{
return new Node(value);
}
if (value < root->data)
{
root->left = insertRecursive(root->left, value);
}
else if (value > root->data)
{
root->right = insertRecursive(root->right, value);
}
else
{
cout << "This item already exists." << endl;
}
return root;
}
Node *findMin(Node *root)
{
while (root->left != nullptr)
{
root = root->left;
}
return root;
}
Node *deleteRecursive(Node *root, int value)
{
if (root == nullptr)
{
cout << "Item not found." << endl;
return nullptr;
}
if (value < root->data)
{
root->left = deleteRecursive(root->left, value);
}
else if (value > root->data)
{
root->right = deleteRecursive(root->right, value);
}
else
{
if (root->left == nullptr)
{
Node *temp = root->right;
delete root;
return temp;
}
else if (root->right == nullptr)
{
Node *temp = root->left;
delete root;
return temp;
}
Node *temp = findMin(root->right);
root->data = temp->data;
root->right = deleteRecursive(root->right, temp->data);
}
return root;
}
void inorderTraversal(Node *root)
{
if (root == nullptr)
{
return;
}
inorderTraversal(root->left);
cout << root->data << " ";
inorderTraversal(root->right);
}
void preorderTraversal(Node *root)
{
if (root == nullptr)
{
return;
}
cout << root->data << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
void postorderTraversal(Node *root)
{
if (root == nullptr)
{
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->data << " ";
}
bool searchRecursive(Node *root, int value)
{
if (root == nullptr)
{
return false;
}
if (value < root->data)
{
return searchRecursive(root->left, value);
}
else if (value > root->data)
{
return searchRecursive(root->right, value);
}
else
{
return true;
}
}
public:
BST() : root(nullptr) {}
void insert(int value)
{
root = insertRecursive(root, value);
}
void remove(int value)
{
root = deleteRecursive(root, value);
}
bool search(int value)
{
return searchRecursive(root, value);
}
void inorder()
{
cout << "Inorder Traverse: ";
inorderTraversal(root);
cout << endl;
}
void preorder()
{
cout << "Preorder Traverse: ";
preorderTraversal(root);
cout << endl;
}
void postorder()
{
cout << "Postorder Traverse: ";
postorderTraversal(root);
cout << endl;
}
};
int main()
{
BST bst;
int n, choice, item;
cout << "Initially, how many integers do you want: ";
cin >> n;
cout << "Enter the integers: ";
for (int i = 0; i < n; i++)
{
cin >> item;
bst.insert(item);
}
cout << endl;
while (true)
{
cout << "Press 1 for inorder traverse, 2 for preorder traverse, "
<< "3 for postorder traverse, 4 for inserting new item, "
<< "5 for deleting an item, or 6 for exit the program: " << endl;
cin >> choice;
switch (choice)
{
case 1:
bst.inorder();
cout << endl;
break;
case 2:
bst.preorder();
cout << endl;
break;
case 3:
bst.postorder();
cout << endl;
break;
case 4:
cout << "Enter the item for insert: " << endl;
cin >> item;
bst.insert(item);
cout << endl;
break;
case 5:
cout << "Enter the item for delete: ";
cin >> item;
bst.remove(item);
cout << endl;
break;
case 6:
cout << "Program terminated." << endl;
return 0;
default:
cout << "Invalid choice. Please try again." << endl;
}
}
return 0;
}
您的代码是正确的，但它采用了不同的方法从树中删除节点。删除节点的正确方法有多种，它们会导致不同的树。当要删除的节点有两个子节点时，“预期输出”将找到 predecessor 节点。您的代码在该场景中找到 successor 节点。两种方法都很好。
如果您想让代码与“预期输出”保持一致，请更改此：
Node *temp = findMin(root->right);
root->data = temp->data;
root->right = deleteRecursive(root->right, temp->data);
对此：
Node *temp = findMax(root->left);
root->data = temp->data;
root->left = deleteRecursive(root->left, temp->data);
并定义
findMaxNode *findMax(Node *root)
{
while (root->right != nullptr)
{
root = root->right;
}
return root;
}