如何在 C++ 中使用二叉树？

Question

我有一个程序，其中有一个二叉树，表示为具有两个指针和一个根的结构。然后我想输入 n 个元素（由 br 变量表示）作为树节点的值。然后我使用 add(param1,...) 函数输入这些元素。但是，当我按 return 键时，在我输入所有这些之后，程序崩溃了。请问为什么会这样？

// TreeGraph.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
using namespace std;
struct elem {
    char key;
    elem *left, *right;
} *root = NULL;
void add(int n, elem * &t);
int num,br,i;
int main()
{
    cout << "Въведете брой елементи\n";
    cin >> br;
    cout << "Въведете стойнсотите на листата на дървото\n";
    while (i != br) {
    cin >> num;
    add(num, root);
    i++;
    }
    return 0;
}
void add(int n, elem * &t) {
    if (t) {
        t = new elem;
        t->key = n;
        t->left = t->right = NULL;
    }
    else {
        if (t->key < n)
            add(n, t->right);
        else
            add(n, t->left);
    }
}

Answer 1

问题不是无限循环。您取消引用空指针，因此程序崩溃。

在此代码中：

void add(int n, elem * &t) {
    if (t) {
        t = new elem;
        t->key = n;
        t->left = t->right = NULL;
    }
    else {
        if (t->key < n)
            add(n, t->right);
        else
            add(n, t->left);
    }
}

您添加节点的条件不正确。应该是if (!t)。二叉搜索树中新节点的位置必须是具有至少一个空子指针的节点的子节点。要添加节点，您需要递归到这些空指针之一，然后在那里添加节点。

想一想当您将初始为空的根传递给 add 函数时会发生什么。第一个 if 语句中的条件为假，因此当您尝试检查条件 if (t->key < n) 时，您正在尝试访问不存在的对象的 key 字段。

如何在 C++ 中使用二叉树？

How to work with binary tree in C++?

c++

binary-tree

pointers

add