时间戳

首页 > 解决方案 > 如何在 C++ 中使用二叉树？

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

问题描述

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

// 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);
    }
}

标签： c++pointersbinary-treeadd

解决方案

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

在这段代码中：

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不存在的对象的字段。

推荐阅读