c++ - 在 C++ 中搜索树中节点的最快方法

Question

#ifndef __TREE_H
#define __TREE_H
#include <cstdlib>
#include<string>

// structure of a tree node

struct TreeNode{
        string str;
        TreeNode *parent;
        TreeNode *leftChild;
        TreeNode *nextSibling;

        TreeNode(string str1){
                this->str = str1;
                this->parent = NULL;
                this->leftChild = NULL;
                this->nextSibling = NULL;
        }

};

class Tree{

        TreeNode* root;
        int size;

public:

        Tree();         //constructor

        void insert(string str1);       //insert a node

        string locate(string str1);     //locate a node

        TreeNode *ancestor(string str1, string str2);   //get lowest common ancestor
};


#endif

这是一类通用树（不是二叉树）。实现定位功能的最快方法是什么？我应该先检查所有孩子，然后检查兄弟姐妹还是什么？

score 1 · Accepted Answer

如果树是无序的，则除了对所有节点进行蛮力测试并在找到元素时（如果找到）突破之外没有其他算法。在处理树时，递归通常是最简单的方法。伪算法可能类似于：

find(current_node,value):

if current_node.value == value
   return found
else 
   if find(current_node.left,value) == found
      return found
   else if find(current_node.right,value) == found
      return found
   else
      return not_found

当然，当真正实现这一点时，您将需要测试空指针，等等。如果对树没有任何其他约束，则不能降低渐近复杂度。您可能会采用非递归方法或尾递归算法（基于上述），这可能会改善常数因子，但不要指望那里会有巨大的改进。

score 0 · Accepted Answer

如果节点是有序的，即子节点小于该节点而兄弟节点大于该节点，则进行比较，str并根据结果将该节点作为结果，或者向下搜索子节点或与兄弟节点进行比较

const TreeNode *TreeNode::locate(const string &str1) const
{
    int c = str.compare(str1);
    if (c == 0)
        return this;

    if (c > 0) {
        if (leftChild)
            return leftChild->locate(str1);

        return 0;
    }

    if (nextSibling)
        return nextSibling->locate(str1);

    return 0;
}

在树中

const TreeNode *Tree::locate(const string &str1) const
{
    return root->locate(str1);
}

score 0 · Accepted Answer

您可以尝试几种树遍历算法，具体取决于您的信息在树节点之间的分布方式。

BFS、DFS 就是一些例子。

c++ - 在 C++ 中搜索树中节点的最快方法

3 回答 3

Related

Reference