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

这是一类泛型树(不是二叉树)。实现定位功能最快的方法是什么？我应该先检查所有 child ，然后再检查 sibling 还是什么？

Answer 1

如果树是无序的，除了对所有节点进行强力测试并在找到元素(如果找到)时中断外，没有其他算法。在处理树时，递归通常是最简单的方法。伪算法可能是这样的:

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

当然，在真正实现它时，您将需要测试空指针等。如果没有对树的任何其他约束，则无法降低渐近复杂度。您也许可以使用非递归方法或尾递归算法(基于上述)来改进常数因子，但不要期望那里有很大的改进。