我的二叉树程序在输出时崩溃
我正在尝试编写二叉树,但它崩溃了。 它一直打印出相同的数字:左节点(较小的数字)和根节点。它递归地重复该程序,直到崩溃。 我知道我的代码还有其他一些错误,但这是需要解决的主要问题,所以我的代码如下:
#include <iostream>
using namespace std;
struct node {
int value = 0;
node* left = NULL;
node* right = NULL;
};
node root;
void add(int x, node* curr)
{
if (x < (*curr).value) {
if ((*curr).left == NULL) {
node next;
next.value = x;
(*curr).left = &next;
}
else {
add(x, (*curr).left);
}
if (x > (*curr).value) {
if ((*curr).right == NULL) {
node next;
next.value = x;
(*curr).right = &next;
}
else {
add(x, (*curr).right);
}
}
}
}
void out(node ro)
{
node lefta;
node righta;
if (ro.left != NULL) {
lefta = *(ro.left);
cout << lefta.value;
out(lefta);
}
if (ro.right != NULL) {
righta = *(ro.right);
cout << " " << righta.value << endl;
out(righta);
}
}
int main()
{
int n;
cin >> n;
int x;
cin >> x;
root.value = x;
node* curr;
curr = &root;
for (int i = 1; i < n; i++) {
cin >> x;
add(x, curr);
}
out(root);
return 0;
}
崩溃后返回:
Process returned -1073741571 (0xC00000FD)
解决方案
如果您想要将新节点插入到列表中,则必须对其进行分配。
函数返回时,堆栈上的局部变量超出范围。
无论如何,您必须将您的函数add
调整为适用于如下所示的双向链表:
void add(int x, node *curr)
{
// while x less than curr->value step left
while ( curr->left != NULL && x < curr->value )
curr = curr->left;
// while x greater than curr->next->value step right
while ( curr->right != NULL && x > curr->right->value )
curr = curr->right;
// x is less than curr->right->value (curr->right may be NULL)
// either x is greater curr->value or curr->left == NULL
node *newNode = new node; // allcat new node
newNode->left = newNode->right = NULL; // <- this schould be done by a constructor of node
newNode->value = x;
if ( x < curr->value )
{
// curr->left == NULL => new node is new start of list
curr->left = newNode;
newNode->right = curr;
}
else if ( curr->right == NULL )
{
// new node is new end of list
curr->right = newNode;
newNode->left = curr;
}
else
{
// new node someweher in the list
node *rightNode = curr->right;
curr->right = newNode;
newNode->right = rightNode;
newNode->left = curr;
rightNode->left = newNode;
}
}
注意,您使用new
分配的所有节点都必须delete
销毁。
如果您希望从头到尾打印列表,则不需要递归函数,并且避免复制节点。使用指针:
void out(const node *ro)
{
if ( ro == NULL )
return;
while ( ro->left != NULL )
ro = ro->left;
while ( ro != NULL )
{
cout << ro->value;
ro = ro->right;
}
}
...
out(&root);
相关文章