二叉树c插入和更新？-Java 学习之路

我想在c中创建一个二进制树来执行插入操作，插入的值是4的节点

name,  type ,  order, and color

使用将输入这4作为 INSERT corn oil 3 yellow . 它创建一个名为corn的新节点和3个子节点作为类型，顺序和颜色 .

如果再次用户输入相同的内容但更改除 INSERT corn oil 4 red 之类的名称之外的任何其他内容，因为 corn name存在，这将更新节点

preorder和postorder遍历，删除并找到任何节点

我要怎么样？

struct TreeNode {
          string itemname;  // The data in this node.
          TreeNode *left;   // Pointer to the left subtree.
          TreeNode *right;  // Pointer to the right subtree.
       };

1-名称节点将在左侧有2个值，其中第4个将放置

2-树的层次结构就像root只有2个左右节点的名称所以root有很多节点，名称只有2个节点但是没有更多的节点会被添加到名称的子节点它真的是树

1 回答

由于您使用的是二叉树，我不确定您是否可以使用字符串作为 TreeNode 的键（我总是使用intigers） . 所以我建议你有这样的结构：

// I am not sure about types, but I assumed them by name
struct Element {
    char* name;
    int type;
    int order;
    char* color;
};

struct TreeNode {
    int key;
    Element *element;
    TreeNode *left, *right;
};

然后你会以某种方式计算 Element::name 的散列来获得一个数值，这是一个关键 . 现在，您将根据键从根向左或向右遍历树 . 您将在每个节点上检查您插入的密钥是否与当前节点中的密钥相同，如果答案为是，则您将交换该节点中的值，否则继续向左或向右遍历树 . 如果您到达底部，则表示您没有找到具有该键的节点，因此您创建一个新节点并将其作为叶子附加 .

您可以查看此link以生成哈希 . 但是，请记住，对于某些字符串，您可以获得相同的哈希值，因此您可能需要在当前树节点上保留多个元素 .

UPDATE

这是代码，但您可以使用指针进行更多优化 . 但正如评论中所提到的，如果您没有严格限制使用二叉树，则应使用HashTable或std::map .

std::map<std::string, struct Element*> elements

并用于检索元素：

Element *e = elements["corn"]

二叉树实现：

#include <iostream>
#include <vector>

#define A 54059 /* a prime */
#define B 76963 /* another prime */
#define C 86969 /* yet another prime */
#define FIRSTH 37 /* also prime */



struct Element {
    std::string name;
    std::string type;
    int order;
    std::string color;
};

struct TreeNode {
    int key;
    std::vector<Element> values;
    struct TreeNode *left;
    struct TreeNode *right;
};

/**
 * see: https://stackoverflow.com/questions/8317508/hash-function-for-a-string
 */
int calculateHash(const char *s)
{
    int h = FIRSTH;
    while (*s) {
        h = (h * A) ^ (s[0] * B);
        s++;
    }
    return h; // or return h % C;
}

void printElement(Element element)
{
    std::cout
            << element.name
            << " "
            << element.type
            << " "
            << element.order
            << " "
            << element.color
            << std::endl;
}

void preOrder(TreeNode* node)
{
    if( node == NULL )
        return;

    for(size_t i=0; i<node->values.size(); i++) {
        printElement(node->values[i]);
    }

    preOrder(node->left);
    preOrder(node->right);
}

void insert(TreeNode** root, Element element, int key)
{
    if( *root == NULL ) {
        TreeNode* node = new TreeNode();
        node->key = key;
        node->values.push_back(element);
        *root = node;
        return;
    };

    if( key == (*root)->key ) {
        for(size_t i=0; i<(*root)->values.size(); i++) {
            if( (*root)->values[i].name == element.name ) {
                (*root)->values[i].type = element.type;
                (*root)->values[i].order = element.order;
                (*root)->values[i].color = element.color;
                break;
            }
        }
    }

    else if( key < (*root)->key ) {
        insert( &((*root)->left), element, key );
    }

    else {
        insert( &((*root)->right), element, key );
    }
}

int main()
{
    TreeNode *node = NULL;
    insert(&node, {"corn1", "oil", 3, "yellow"}, calculateHash("corn1"));
    insert(&node, {"corn2", "oil", 3, "yellow"}, calculateHash("corn2"));
    insert(&node, {"corn3", "oil", 3, "yellow"}, calculateHash("corn3"));

    insert(&node, {"corn2", "aaa", 32, "blue"}, calculateHash("corn2"));

    preOrder(node);
    return 0;
}

回复于 2024-05-05T06:40:11+08:00

二叉树c插入和更新？

1 回答

相关问题