c++ - BinaryTree 不会分配新创建的节点

Question

问题出在有两个参数的insert方法上。函数 insert(char letter, string code) 调用 insert(TreeNode *node, char letter, char code)。但是，它不会将左 child 或右 child 分配为节点。带有三个参数的插入方法应该创建一个新节点。那么这个节点应该被分配为左或右 child 。

#include "tree.h"
#include <iostream>
#include <string>

using std::string;
using std::cout;
using std::endl;

BinaryTree::BinaryTree() {
    root = nullptr;
}

BinaryTree::~BinaryTree() {
    empty_tree(root);
}

void BinaryTree::empty_tree(TreeNode *node) {
    if (root) {
        if (node->left) {
            return empty_tree(node->left);
        }
        if (node->right) {
            return empty_tree(node->right);
        }
        delete node;
    }
}

void BinaryTree::insert(char letter, string code) {
    TreeNode *node = root;
    TreeNode *temp = nullptr;
    if (node) {
        for (string::size_type i = 0; i < code.length(); i++) {
            //temp = node;
            if (code[i] == '.') {
                if (node->left) {
                    node = node->left;
                }
                else {
                    insert(temp, letter, code[i]);
                    node->left = temp;

                }
            }
            else {
                if (node->right) {
                    node = node->right;
                }
                else {
                    return insert(temp, letter, code[i]);
                    node->right = temp;
                }
            }
        }
    }
    /*else {
        return insert();
    }*/
}

void BinaryTree::insert() {
    if (!root) {
        root= new TreeNode();
        root->letter = '*';
        root->left = nullptr;
        root->right = nullptr;
        root->code = "*";
    }
}

void BinaryTree::insert(TreeNode *node, char letter, char code) {
    if (!node) {
        node = new TreeNode();
        node->letter = letter;
        node->left = nullptr;
        node->right = nullptr;
        node->code += code;
    }
}

void BinaryTree::print_tree() {
    return print_tree(root);
}

void BinaryTree::print_tree(TreeNode *tree) {
    if (tree) {
        if (tree->left) {
            print_tree(tree->left);
        }
        if (tree->right) {
            print_tree(tree->right);
        }
        cout << "Node is " << tree->letter << " and in Morse Code is " << tree->code << endl << endl;
    }
}

下面是包含 main. morse-code.txt 文件只有从 a 到 z 的字母顺序。每行有一个字母，后跟一个空格，然后是摩尔斯电码。

#include "tree.h"
#include <iostream>
#include <fstream>
#include <string>

using std::cout;
using std::endl;

int main() {
    std::string code;
    std::ifstream infile;
    char letter;
    BinaryTree tree;;

    infile.open("morse-code.txt");
    if (!infile) {
        std::cout << "File unable to open" << std::endl;
    }
    else {
        cout << "morse-code.txt\n\n";
        tree.insert();
        while (std::getline(infile, code)) {
            tree.insert(code[0], code.substr(2, code.length()-2));
            cout << code << endl;
        }
        cout << "\n******Tree Representation******\n\n";
        tree.print_tree();
    }
    system("pause");
}

文本文件

a .-
b -...
c -.-.
d -..
e .
f ..-.
g --.
h ....
i ..
j .---
k -.-
l -.--
m --
n -.
o ---
p .--.
q --.-
r .-.
s ...
t -
u ..-
v ...-
w .--
x -..-
y -.--
z --..

树.h

#ifndef _TREE_H
#define _TREE_H

//#include <iostream>
//#include <fstream>
#include <string>

using std::string;

class BinaryTree {
private:
    struct TreeNode {
        char letter;
        string code;
        TreeNode *left;
        TreeNode *right;
    }; TreeNode *root;

public:
    BinaryTree();
    ~BinaryTree();
    void insert();
    void insert(TreeNode *new_node, char letter, char code);
    void insert(char letter, string code);
    void empty_tree(TreeNode *node);
    void print_tree(TreeNode *node);
    void print_tree();
};
#endif

Answer 1

我认为插入并不是您的代码遇到的唯一问题。您的 empty_tree 不正确(不会释放所有内存，因为您过早返回。您错误的代码的特定部分是代码的以下行:“return insert(temp，letter，code [i]);”您的其余代码看起来不错。

它应该看起来像这样:

void BinaryTree::empty_tree(TreeNode *node) {
    if (!node) return;
    delete node;
    empty_tree(node->left );
    empty_tree(node->right);
    /* See Jerry's solution below. */
}

void BinaryTree::insert(char letter, string code) {
    TreeNode *node = root;
    if (!root) /* do something*/;
    for (string::size_type i = 0; i < code.length(); i++) {
        if (code[i] == '.') {
            if (node->left)
                insert(&node->left, letter, code[i]);
            node = node->left;
        }
        else {
            if (!node->right)
                insert(&node->right, letter, code[i]);
            node = node->right
        }
    }
}

void BinaryTree::insert(TreeNode **node, char letter, string code) {
    *node = new TreeNode();
    (*node)->letter = letter;
    (*node)->left = nullptr;
    (*node)->right = nullptr;
    (*node)->code = code;
}

在 tree.h 中:

typedef struct _TreeNode {
    char letter;
    string code;
    struct _TreeNode *left;
    struct _TreeNode *right;
} TreeNode; TreeNode *root;

我*编译了以下代码:

#include <iostream>
#include <string>
#include <fstream>

using namespace std;

typedef struct _TreeNode {
    char letter;
    string code;
    struct _TreeNode *left;
    struct _TreeNode *right;
} TreeNode;

class BinaryTree {
private:
    TreeNode *root;
public:
    BinaryTree();
    ~BinaryTree();
    void insert();
    void insert(TreeNode **new_node, char letter, string code);
    void insert(char letter, string code);
    void empty_tree(TreeNode *node);
    void print_tree(TreeNode *node);
    void print_tree();
};

BinaryTree::BinaryTree() {
    root = nullptr;
}

BinaryTree::~BinaryTree() {
    empty_tree(root);
}

void BinaryTree::empty_tree(TreeNode *node) {
    if (!node) return;
    delete node;
    empty_tree(node->left );
    empty_tree(node->right);
}

void BinaryTree::insert(char letter, string code) {
    TreeNode *node = root;
    if (!root) insert();
    for (string::size_type i = 0; i < code.length(); i++) {
        if (code[i] == '.') {
            if (!node->left)
                insert(&node->left, letter, code.substr(0,i));
            node = node->left;
        } else {
            if (!node->right)
                insert(&node->right, letter, code.substr(0,i));
            node = node->right;
        }
    }
}

void BinaryTree::insert() {
    root = new TreeNode();
    root->letter = '*';
    root->left = nullptr;
    root->right = nullptr;
    root->code = "*";
}

void BinaryTree::insert(TreeNode **node, char letter, string code) {
    *node = new TreeNode();
    (*node)->letter = letter;
    (*node)->left = nullptr;
    (*node)->right = nullptr;
    (*node)->code = code;
}

void BinaryTree::print_tree() {
    return print_tree(root);
}

void BinaryTree::print_tree(TreeNode *tree) {
    if (tree) {
        if (tree->left ) print_tree(tree->left );
        cout << "Node is " << tree->letter << " and in Morse Code is "
             << tree->code << endl << endl;
        if (tree->right) print_tree(tree->right);
    }
}

int main() {
    string code;
    ifstream infile;
    char letter;
    BinaryTree tree;

    infile.open("morse-code.txt");
    if (!infile) {
        cout << "File unable to open" << endl;
    }
    else {
        cout << "morse-code.txt\n\n";
        tree.insert();
        while (std::getline(infile, code)) {
            tree.insert(code[0], code.substr(2, code.length()-2));
            cout << code << endl;
        }
        cout << "\n******Tree Representation******\n\n";
        tree.print_tree();
    }
    system("pause");
}