我如何在 C++ 中缩短这个简单的数据树算法？

Question

它创建了一个数据树和一个“随机”/伪随机数。然后它寻找“随机”生成的数字的路径，以及是否找到了整个数字。当然有更好的方法，但我想不出一个。另外，我看到了一个错误，但它甚至不值得修复它，因为无论如何必须有更好的方法（我的意思是如果整数“in”出于某种原因高于或低于 10 或 0）。

我就是找不到任何相关信息。根本不可能吗？

struct Node {
    int data;
    struct Node* left;
    struct Node* right;

    Node(int val)
    {
        data = val;
        left = NULL;
        right = NULL;
    }
};

Node* build()   {
    struct Node* root = new Node(5);

    root->right = new Node(3);
    root->left = new Node(7);

    root->right->right = new Node(1);
    root->right->left = new Node(4);
    root->right->right->right = new Node(0);
    root->right->right->left = new Node(2);

    root->left->right = new Node(6);
    root->left->left = new Node(9);
    root->left->left->right = new Node(8);
    root->left->left->left = new Node(10);

    return root;
}

void worker(int in, Node* root) {
    bool found = false;
    string path = "";
    int val = 0;

    if (in > root->data)    {
            if (in > root->left->data)  {
                if (in > root->left->left->data)    {
                    found = true;
                    path = "root->left->left->left";
                    val = root->left->left->left->data;
                }
                else if (in < root->left->left->data)   {
                    found = true;
                    path = "root->left->left->right";
                    val = root->left->left->right->data;
                }
                else {
                    found = true;
                    path = "root->left->left";
                    val = root->left->left->data;
    }
            }
            else if (in < root->left->data) {
                found = true;
                path = "root->left->right";
                val = root->left->right->data;
            }
            else {
                found = true;
                path = "root->left";
                val = root->left->data;
    }
    }

    else if (in < root->data)   {
        if (in > root->right->data) {
            found = true;
            path = "root->right->left";
            val = root->right->left->data;
        }
        else if (in < root->right->data)    {
                if (in > root->right->right->data)  {
                    found = true;
                    path = "root->right->right->left";
                    val = root->right->right->left->data;
                }
                else if (in < root->right->right->data) {
                    found = true;
                    path = "root->right->right->right";
                    val = root->right->right->right->data;
                }
                else {
                    found = true;
                    path = "root->right->right";
                    val = root->right->right->data;
    }
        }
        else {
            found = true;
            path = "root->right";
            val = root->right->data;
        }
    }
    else {
    found = true;
    path = "root";
    val = root->data;
    }
    ```

Answer 1

老实说，您的“worker”函数使用了很多“if...else if...else”样式，这可能会使您的算法难以实现extend.Maybe您可以试试这段代码

Node * prt = root;
string val,path="root"; 
while(prt){ 
 if(prt.data>in){
  path+="->right";
  prt=prt->right;} 
 else if(prt.date<in){
  path+="->left";
  prt=prt->left;} 
 else{
  break;} 
}
val=root+"->data";

Answer 2

因此，如果您必须编写自己的二叉树而不是使用 std::set，那么您不想对通过树的所有路径进行硬编码 - 可能有数千个节点，您看到了只处理 11 个就很痛苦。

有两种方法可以解决此问题：可以使用迭代（while 循环）遍历二叉树，也可以使用递归。有些问题用迭代更简单，有些用递归更容易。所以我两种方式都做了，所以你可以比较。

使用 while 循环：

#include <iostream>
#include <string>

struct Node {
    int data;
    Node* left;
    Node* right;

    Node(int data) : data(data), left(NULL), right(NULL) {}
};

struct AddResult
{
    Node *node;
    bool inserted;
    std::string path;
    
    AddResult(Node *node, bool inserted, std::string path) : node(node), inserted(inserted), path(path) {}
};

AddResult add(Node* node, int value)
{
    bool inserted = false;
    std::string path = "root";

    while (node != NULL && value != node->data)
    {
        if (value > node->data)
        {
            // add to the right
            if (node->right == NULL)
            {
                node->right = new Node(value);
                inserted = true;
            }
            path = path + "->right";
            node = node->right;
        }
        else
        {
            // add to the left
            if (node->left == NULL)
            {
                node->left = new Node(value);
                inserted = true;
            }
            path = path + "->left";
            node = node->left;
        }
    }
    return AddResult(node, inserted, path);
}

struct FindResult
{
    Node *node;
    bool found;
    std::string path;
    
    FindResult(Node *node, bool found, std::string path) : node(node), found(found), path(path) {}
};

FindResult find(Node* node, int value)
{
    bool found = true;
    std::string path = "root";

    while (node != NULL && value != node->data)
    {
        if (value > node->data)
        {
            // add to the right
            if (node->right == NULL)
                found = false;

            path = path + "->right";
            node = node->right;
        }
        else
        {
            // add to the left
            if (node->left == NULL)
                found = false;
                
            path = path + "->left";
            node = node->left;
        }
    }
    return FindResult(node, found, path);
}

int main()
{
    Node *root = new Node(5);
    printf("%d was made the root of the tree\n", 5);

    // add all the odd values from 1 to 10 inclusive
    for(int i=1; i<=10; i+=2)
    {
        AddResult result = add(root,i);
        if (result.inserted == false)
            printf("%d was already in the tree at: %s\n", i, result.path.c_str());
        else
            printf("%d was added to the tree at: %s\n", i, result.path.c_str());
    }
    // add all the even values from 1 to 10 inclusive
    for(int i=0; i<=10; i+=2)
    {
        AddResult result = add(root,i);
        if (result.inserted == false)
            printf("%d was already in the tree at: %s\n", i, result.path.c_str());
        else
            printf("%d was added to the tree at: %s\n", i, result.path.c_str());
    }

    puts("");

    // find all the values from -1 to 12 inclusive
    for(int i=-1; i<=12; i++)
    {
        FindResult result = find(root,i);
        if (result.found == false)
            printf("%d was not found in the tree\n", i);
        else
            printf("%d was Found in the tree at %s\n", i, result.path.c_str());
    }


    return 0;
}

在 https://onlinegdb.com/BJeL1A6Gu

试试

使用递归：add 或 find 函数应检查当前节点，如果该节点不是正确的节点，则应再次调用左侧或右侧的函数：

#include <iostream>
#include <string>

struct Node {
    int data;
    Node* left;
    Node* right;

    Node(int data) : data(data), left(NULL), right(NULL) {}
};

struct AddResult
{
    Node *node;
    bool inserted;
    std::string path;
    
    AddResult(Node *node, bool inserted, std::string path) : node(node), inserted(inserted), path(path) {}
};

AddResult add(Node* node, int value, std::string path = "root")
{
    if (value == node->data)
        return AddResult(node, false, path); // already in tree

    if (value > node->data)
    {
        // add to the right
        if (node->right != NULL)
            return add(node->right, value, path + "->right");
        else
        {
            node->right = new Node(value);
            return AddResult(node->right, true, path + "->right");
        }
    }
    else
    {
        // add to the left
        if (node->left != NULL)
            return add(node->left, value, path + "->left");
        else
        {
            node->left = new Node(value);
            return AddResult(node->left, true, path + "->left");
        }
    }
}

struct FindResult
{
    Node *node;
    bool found;
    std::string path;
    
    FindResult(Node *node, bool found, std::string path) : node(node), found(found), path(path) {}
};

FindResult find(Node* node, int value, std::string path = "root")
{
    if (value == node->data)
        return FindResult(node,true,path);
    
    if (value > node->data)
    {
        // add to the right
        if (node->right != NULL)
            return find(node->right, value, path + "->right");
        else
            return FindResult(NULL,false,path);
    }
    else
    {
        // add to the left
        if (node->left != NULL)
            return find(node->left, value, path + "->left");
        else
            return FindResult(NULL,false,path);
    }
}

int main()
{
    Node *root = new Node(5);
    printf("%d was made the root of the tree\n", 5);

    // add all the odd values from 1 to 10 inclusive
    for(int i=1; i<=10; i+=2)
    {
        AddResult result = add(root,i);
        if (result.inserted == false)
            printf("%d was already in the tree at: %s\n", i, result.path.c_str());
        else
            printf("%d was added to the tree at: %s\n", i, result.path.c_str());
    }
    // add all the even values from 1 to 10 inclusive
    for(int i=0; i<=10; i+=2)
    {
        AddResult result = add(root,i);
        if (result.inserted == false)
            printf("%d was already in the tree at: %s\n", i, result.path.c_str());
        else
            printf("%d was added to the tree at: %s\n", i, result.path.c_str());
    }

    puts("");

    // find all the values from -1 to 12 inclusive
    for(int i=-1; i<=12; i++)
    {
        FindResult result = find(root,i);
        if (result.found == false)
            printf("%d was not found in the tree\n", i);
        else
            printf("%d was Found in the tree at %s\n", i, result.path.c_str());
    }


    return 0;
}

在 https://onlinegdb.com/BJi6F66zO

试试

这个程序的主要问题是你需要选择树的根或者写一大堆代码来平衡树。使用 std::set 将为您完成所有这些工作。如果你使用 std::set 整个程序看起来像：

#include <stdio.h>
#include <set>

int main()
{
    std::set<int> tree;

    // let's add an item now so we can see what happens if we add it again later    
    auto result = tree.insert(5);
    printf("%d was added to the tree: %d\n", 5, *result.first);

    // add all the values from 0 to 10 inclusive
    for(int i=0; i<=10; i++)
    {
        auto result = tree.insert(i);
        if (result.second == false)
            printf("%d was already in the tree: %d\n", i, *result.first);
        else
            printf("%d was added to the tree: %d\n", i, *result.first);
    }

    puts("");

    // find all the values from -1 to 12 inclusive
    for(int i=-1; i<=12; i++)
    {
        auto result = tree.find(i);
        if (result == tree.end())
            printf("%d was not found in the tree\n", i);
        else
            printf("%d was Found in the tree: %d\n", i, *result);
    }


    return 0;
}

在 https://onlinegdb.com/Hk8FHpTMu

试试

我如何在 C++ 中缩短这个简单的数据树算法？

How could I shorten this trivial data tree algorithm in C++?

c++

binary-search-tree